Revision as of 20:16, 28 February 2022

ABSTRACT

The majority of the flowshop scheduling literature focuses on regular performance measures like makespan, flowtime etc. In this paper a flowshop scheduling problem is addressed where the objective is to minimize completion time variance (CTV). CTV is a non-regular performance measure that is closely related to just-in-time philosophy. A Microsoft Excel spreadsheet-based genetic algorithm (GA) is proposed to solve the problem. The proposed GA methodology is domain-independent and general purpose. The flowshop model is developed in the spreadsheet environment using the built-in formulae and function. Addition of jobs and machines can be catered for without the change in the basic GA routine and minimal change to the spreadsheet model. The proposed methodology offers an easy to handle framework whereby the practitioners can implement a heuristic-based optimization tool with the need for advanced programming tools. The performance of the proposed methodology is compared to previous studies for benchmark problems taken from the literature. Simulation experiments demonstrate that the proposed methodology solves the benchmark problems efficiently and effectively with a reasonable accuracy. The solutions are comparable to previous studies both in terms of computational time and solution quality.

Keywords: Completion time variance (CTV), Flow shop, genetic algorithms, scheduling, spreadsheet.

1. Introduction

Manufacturing plays a vital role in developing the economy as well as the human resources. In today’s competitive world efficent use of materials and resources has become imperative to generate improved revenues. Scheduling research primarily focuses on regular performance measures where the objective function increases as a function of job completion times. Commonly used regular performance measures are: makespan, mean flowtime, tardiness, etc. For regular performance measures, the determination of an optimal solution is relatively simple. Most manufacturing compnaies nowadays prefer just-in-time (JIT) service or production systems. Earliness and tardiness are both undesirable in a JIT environment. CTV is one such non-regular perfomance measure that penalizes earliness as well as tardiness. It is also closely related to quality of service provided to each customer. CTV minimization is especially important when all jobs must spend the same time in the system, i.e., each job requires the same treatment. Smaller CTV ensures more stable service. CTV applications are found in many real-world applications such as production planning and internet data packet dispatching.

The first reported instance of the application of CTV minimization was proposed by Merten and Muller [1] in computer systems for solving the file organization problem where uniform response time was desired to be provided to users’ requests to retrieve data files. Research has shown that an optimal CTV solution has a V-shape property [2]. In a V-shaped optimal solution, the jobs before the smallest job are scheduled in decreasing order of the processing times, while the jobs after the smallest job are scheduled in an ascending order of the processing times.

Since the first application of CTV by Merten and Muller [1], most of the scheduling literature addressed CTV minimization in a single machine environment, e.g., Nasini and Nessah [3], Wang and Lu [4], Viswanathkumar and Srinivasan [5], Sharma [6], Gupta, Gupta [7], etc. Minimization of CTV is considered NP-hard even for a single machine case [8]. However, very little work has been reported for CTV minimization in a flowshop environment.

Flowshop scheduling research has attracted wide attention among researchers due to its many industrial as well as economic applications. Some of the recent reviews highlighting the importance of flowshop scheduling has been presented by Çolak and Keskin [9], Lee and Loong [10] and González-Neira, Montoya-Torres [11]. In a regular flowshop, a set of n-jobs are required to be processed on m-groups of machines. Each of the n jobs follows the same process sequence. Minimization of CTV in a flowshop ensures uniform turnover of jobs and delivery to customer.

2. Literature Review

The first instance of CTV minimization was reported by Marangos, Govande [12]. They applied a simulated annealing algorithm (SA) to minimize CTV in a two-machine flowshop. The authors reported that the proposed approach obtains a solution in the range of 5-10% of the lower bounds. Additionally, the SA algorithm can guarantee an optimal solution for problems having up to 10 jobs. Gowrishankar, Rajendran [13] addressed CTV minimization in an n-jobs m-machine flowshop. The authors state that this is the first attempt to minimize CTV in an n-jobs m-machine flowshop. A breadth first branch & bound procedure as developed to solve the problem. Experimental analysis showed that the proposed method can effectively solve flowshop problems with CTV objective function.

Chandrasekaran, Ponnambalam [14] applied a particle swarm optimization (PSO) algotithm to minimize CTV. Benchmark flowshop problems proposed by Taillard [15] are used to check the performance and efficiency of the proposed PSO. The authors reported that the results obtained are better when compared with the previously published results. Gajpal and Rajendran [16] applied an ant colony optimization (ACO) algorithm to minimize CTV. The authors developed a new ACO algorithm (NACO) for the problem. The performance of the proposed NACO is compared with exisiting ACO algorithms. Experimental analysis showed that, on average, the proposed ACO finds better results as compared to exisiting ACO algorithms.

Chandrasekaran, Ponnambalam [17] proposed a PSO algorithm for multi-objective flowshop scheduling problems where the objective is simultaneous minimization of flowtime, makespan and CTV. The performance of the proposed PSO is enhanced by a local search mechanism. Experimental analysis showed that the proposed PSO yields more non-dominated solutions as compared to other approaches. Chen, Li [18] considered CTV minimization in an unrestricted parallel machine scheduling problem. A heuristic algorithm is proposed to solve the problem. The proposed heuristic algorithm can generate almost optimal schedules for small-sized problems. Ponnambalam, Jawahar [19] proposed a discrete PSO to solve a multi-objective flowshop scheduling problem where the objective is simultaneous minimization of flowtime, makespan and CTV. Computational analysis showed that the proposed discrete PSO performs better in terms of quality of solution as compared to previous studies. Srirangacharyulu and Srinivasan [20] proposed a GA and a heuristic algorithm to minimize CTV in multi and single machine systems. Comparative analysis demonstrated that the propsed algorithms can provide better results as compared to the exisiting algorithms.

Li, Chen [21] considerd minimization of CTV in an unrestricted parallel machine environment and proposed an efficient heuristic Wavy Assignment, Verified Schedule (WAVS). The proposed algorithm produces near optimal solutions for small sized problems while outperforming existing algorithms for large sized instances. Rameshkumar, Rajendran [22] proposed two PSO algorithms: an ACO-inspired PSO and a discrete PSO. Extensive computational analysis was carried out to compare the performance of the two proposed algortithms with previous studies for Taillard [15] benchmark problems. On average, the proposed algorithm provides good and promising solutions. Krishnaraj, Pugazhendhi [23] proposed an adaptation of ACO to minimize CTV in n-jobs m-machines flowshop scheduling problem. Although the proposed algorithm does not provide best schedules for Taillard [15] benchmark problems, it does provide good and promising solutions for most of the instances. Mehta, Pandit [24] proposed a two-phase local search algorithm to minimise CTV in a permutation flowshop. In the first phase, an initial V-shaped solution is constructed using a local search method and then improved it to obtain a locally optimal V-shaped solution. In the second phase, any possible sequences are traversed that may improve the solution.

Eren [25] considerd minimization of CTV for a two-machine flowshop. A non-linear programming (NLP) method is proposed to solve the problem. The proposed algorithm can effectively solve problems up to 30 jobs. Problems up to 500 jobs are solved using a heuristic method. The author demonstrated that the proposed algorithm is very practical in solving real-world problems more effectively than the NLP models. Lee, Wang [26] considered minimization of total weighted completion time (TWCT) for identical parallel machine scheduling. A two-agent based solution method is used to solve the problem. For fewer number of jobs, a branch & bound procedure is also developed. Rajkanth, Rajendran [27] considerd minimization of CTV for single and identical parallel machines. A heuristic method is proposed to solve the problem. The proposed heuristic method produces results better than the exisiting heuristics. It can also be modified and adapted to handle other non-regular performance measures like flow time variance and mean squared deviation as well as solve non-identical parallel machine problems.

Krishnaraj, Pugazhendhi [28] proposed a simulated annealing (SA) algorithm to minimize CTV in n-job m-machine flowshop shceduling problem. The proposed algorithm works in three phases. In the first phase, the algorithm minimizes CTV of jobs without right shifting of completion time (RSCT) of jobs. In phase two, the algorithm minimizes CTV of jobs with RSCT of jobs, except the last job. In phase three, sequences are converted to follow a V-shaped property with respect to processing time of jobs on the last machine, followed by RSCT except that of the last job so that the makespan and the machine utilization in the shop floor remain the same. Extensive computational analysis was carried out with the existing heuristic algorithms. The proposed algorithm is able to find good results. Krishnaraj and Thiagarajan [29] also proposed a two-phase SA algorithm to minimize CTV in a flowshop environment. The performance of the proposed SA algorithm is tested on 90 benchmark flowshop problems from Taillard [15]. The proposed algorithm performs well in minimizing CTV especially in medium- and large-sized problems.

In this paper, we address the minimization of CTV in a flowshop environment using a general-purpose domain-independent GA embedded in a Microsoft Excel spreadsheet environment. The performance of the proposed methodology is compared with existing heuristics for a wide range of benchmark problems taken from the literature. Comparison is made with single machine, paralel machine and flowshop environments.

3. Problem Definition & Formulation of Permutation Flowshop Scheduling Problem

In a permutation flowshop shceduling problem, where the objective is to minimize completion time variance, n jobs from a set of j = 1, 2, 3,…, n are to be processed on m machines k = 1, 2, 3,…, n. Each job j has a set of operations o_j1, o_j2, o_j3,…, o_jk that are required to be processed through m machines requiring p_jk processing time.

Other assumptions used in the modeling of flowshop in this research application are as folows:

1) The number of n jobs and m machines are known before the planning horizon, i.e., t = 0.

2) All n jobs follow the same routing through the machines

3) There is an umlimited buffer between the machines.

4) A different machine is required for the processing of each of the o_jk operations and there is only one machine of its kind in the flowshop.

5) A particular machine can process only one job at any given time and similarly, every job can only be processed by only one machine.

6) All processing times p_jk are known and deterministic.

7) Setup times for any operation, if any, are included in the processing time p_jk.

8) All machines are continuously available and there is no breakdown of machines.

9) Once started, an operation cannot be stopped, i.e., no pre-emption is allowed.

The problem then is to efficiently schedule the job to minimize the completion time variance (CTV). CTV for n jobs in a schedule is given by:

where

${\textstyle {C}_{i}=}$ completion time of job i

n = total number of jobs

In the proposed methodology, a proprietry genetic algorithm Evolver 4.8 [30] is used for the optimization. Evolver works as an add-in to the Microsoft Excel spreadsheet. The flowshop model for minimization of CTV is developed within the spreadsheet using the buil-in functions and formulae.

Research shows that, in the past few decades, spreadsheets have been extensivly used in various fields of engineering. Spreadsheets are popular among the practitioners because they eliminate tedious and repetitive calculations. Some of the recent spreadsheet applications in engineering are: project scheduling [31], process planning and scheduling [32], airport ground crew scheduling [33], supply chain management (Amaral and Kuettner [34] and Othman, Mustaffa [35].

Evolver has also been used by many researchers for optimization problems of various applications. Some of the recent applications of using Evolver are: risk analysis of reservoir operation [36], choosing materials for eco-friendly buildings [37], energy efficient operation of submersible pumps [38], operational optimization of a heat pump system [39], optimization of repetitive scheduling [40], optimum crew selection for repetitive projects [41].

The use of Microsoft Excel and Evolver optimization software offers an easy-to-handle framework for the practitioner. This framework allows practitioners to implement a heuristic-based optimization tool without the need for advanced progamming skills. Furthermore, Microsoft Excel and Evolver offer a user-friendly interface and facilitates user specification of the optimization parameters without the need for any programming skills.

4.1 Chromosome Representation

Permutation representation for chromosome (solution) is required to be used for the minimization of CTV in a flowshop environment. To address a particular problem situation, Evolver has various solving methods. The Order Solving method of Evolver is used to handle permutation representation. Permutation representation is described by considering six jobs D-C-A-B-E-F. In a permutation representation, the order of the genes are changed to formulate new solution strings. Chromosome F-C-B-A-E-D would be one of the possible chromosome representing permutation representation while another could be B-F-A-C-E-D.

4.2 Reproduction and Selection

Steady state reproduction method [42] is used in Evolver. Unlike other reproduction techniques used in GA, steady state reproduction method produces only one child in each generation. The fitness of the child solution is compared to the fitness of other chromosomes in the population. In case the child solution is fitter, it replaces the worst performing member of the population, else it is discarded. For selection, Evolver uses rank-based selection method.

4.3 Crossover Operator

Crossover operator combines genes from two parents to formulate new solutions. Order crossover [43] is used in the Order solving method. Order crossover randomy selects genes from one parent, then finds their place in the second parent. The remaining genes are copied in the second parent in the same order as they appear in the first parent. This ensures that the sub-ordering in the original parents are preserved while creating some new sub-orderings. Consider the two representing solutions in Fig. 1.

The two cut points for each of the parents are indicated by green colour. The genes between the two cut points are copied in the child solution as they are in both parents, as shown in Fig. 2.

Next, for child 1, starting from the second cut point of parent 1, the jobs from the second parent are copied, except those which are already in child 1, we get H-A-B- I-G. This sequence is placed in the first child. Similalry, the procedure is applied for child 2, where the genes are now copied from parent 1. The resulting child solutions would be as in Fig. 3.

4.4 Mutation Operator

With successive iterations, the population loses diversity and gets stuck in local optima. Mutation operator ensures that diversity is maintained in the population. The order solving method performs order-based mutation [43]. In an order-based mutation, two positions are selected randomly, and then the genes in these position are swapped. For example, at position 3 and 6 in child 1 in Fig. 3, we have genes C and F. By swapping these two genes, the resulting chromosome would be as shown in Fig. 4.

5. Computation Analysis

Simulation experiments were carried out to check the performance of the proposed methodology. Benchmark problems were taken from already published literature to validate the usefulness and performance of the proposed methodology. Evolver version 4.8 was used for the GA while Excel version 2003 was used to develop the flowshop models. The following GA parameters were used for the simulation experiments: crossover rate = 0.65, mutation rate = 0.07 and population size = 70. Each of the benchmark problems was run for 30 replications. The simulation experiments were conducted on a 2^nd generation i7 laptop computer with 8GB RAM.

Comparison is made with various heuristics developed in previous studies based on relative percentage deviation (RPD) from the best found solution among all heuristics. The RPD is calculated as follows:

where

${\textstyle {CTV}_{propsed}}$ = completion time variance result found by the proposed methodology

${\textstyle {CTV}_{best}}$ = best completion time variance found among all previous heuristics

A positive RPD means that the CTV result found by the given heuristic is worse than the best CTV result among all heuristics, while a negative RPD means that the result found by a given heuristics is worse than the best CTV result.

5.1. Problem Set 1

The first problem set is taken from Gupta, Gupta [7]. The data set is a single machine scenario with jobs ranging from 10 to 20. The data set consists of 15 instances. Data for problem set 1 is presented in Table A 1.

The perfomance of the proposed methodology is compared with results from GGA (GA by Gupta, Gupta [7]), HAS (hybrid simulated annealing algorithm by Mittenthal, Raghavachari [44]) and TSA (tabu search algorith by Al-Turki, Fedjki [45]). The comparative analysis with three approaches is presented in Table 1.

Table 1Comparative Analysis of Proposed Methodology with Previous Studies for Data Set 1

From Table 1, we can see that the average RPD for CGA, HAS, TSA and the proposed GA are 0.0402%, 0.0022%, 0.0001% and 0%, respectively. It is clear that, compared to CGA, HAS and TSA, the proposed GA methodology was able to find an optimal solution for all problem instances. The computation time required to find the optimum solution was less than 2 secs.

5.2. Problem Set 2

Problem set 2 is taken from Srirangacharyulu and Srinivasan [20]. Problem set 2 is also a sinlge machine scenario with jobs ranging from 15 to 25. The data set consists of nine instances. Data for problem set 2 is presented in Table A 2.

The performance of the proposed methodology is compared with results from EC1.1 and EC1.2 (heuristic methods by Eilon and Chowdhury [2]), JJK (heuristic method by Kanet [46]), GGB (GA by Gupta, Gupta [7], MP (heuristic method by Prasad and Manna [47]), VS (verified spiral heuristic method by Ye, Li [48], HA (hybrid GA algorithm by Srirangacharyulu and Srinivasan [20]), SMH1 (heuristic algorithm by Rajkanth, Rajendran [27]). The comparative analysis with three approaches is presented in Table 2.

Table 2

Comparative Analysis of Proposed Methodology with Previous Studies for Data Set 2

From Table 2, we can see that the average RPD for EC1.1, EC1.2, JJK, MP, GGB, HA, VS, SMH1 and proposed GA are 0.1248%, 0.0915%, 0.0015%, 0.0056%, 0.0065%, 0.0004%, 0.0015%, 0.0005% and 0%, respectively. It is evident from the results in Table 2 that the proposed GA was able to find an optimal solution for all problem instances of data set 2.

5.3. Problem Set 3

Problem set 3 is taken from Li, Chen [21]. The problem set is an unrestricted parallel machine scernario and consists of nine jobs to be scheduled on two parallel machines to minimize CTV. The problem set consists of four subsets with processing times following four kinds of distributions: the uniform distribution of Uniform (1, 59), the normal distribution of Normal (30; 10²), the exponential distribution of Exponential (30), and the Pareto distribution of Pareto (1.0345,1). Each of the subsets has five problem instances. The comparative analysis with WAVS algorithm [21] is given in Table 3 to Table 7.

The comparative results in Table 3 to Table 6 shows the superior performance of the proposed GA methodology with respect to WAVS heuritics. The proposed GA methodology was able to find an optimal solution in all the instances. In all the twenty instances, the best solution was obtained withn 4 secs on a 2^nd generation i7 laptop computer with 8GB RAM.

Table 3

Comparative Analysis of Proposed Methodology for Data Set 3 – processing times from Uniform (1, 59)

Table 4

Comparative Analysis of Proposed Methodology for Data Set 3 – processing times from Normal (30; 10²)

Table 5

Comparative Analysis of Proposed Methodology for Data Set 3 – processing times from Exponential (30)

Table 6

Comparative Analysis of Proposed Methodology for Data Set 3 – processing times from Pareto (1.0345,1)

5.4. Problem Set 4

Problem set 4 consists of flowshop problems proposed by Taillard [15]. The problem set has six different settings of n-jobs and m-machines. The data set consists of 20 Î 5, 20 Î 10, 20 Î 20, 50 Î 5, 50 Î 10 50 Î 20 settings. Each setting has 10 problem instances thus, in total 60 different problems were solved to compare the performance of the proposed GA methodology with previously reported results. The problem instances can be accessed at http://mistic.heig-vd.ch/taillard/problemes.dir/ordonnancement.dir/ordonnancement.html.

The performance is compared with the following heuristics: SA – 2020 (simulated annealing heuristics by Krishnaraj and Thiagarajan [29], SA – 2019 (simulated annealing algorithm by Krishnaraj, Pugazhendhi [28]), ACO (ant colony algorithm by Gajpal and Rajendran [16]), MACO (modified ant colony algorithm by Krishnaraj, Pugazhendhi [23]), DPSO 1 (discrete particle swarm algorithm by Rameshkumar, Rajendran [22]) and DPSO 2 (discrete particle swarm algorithm by Ponnambalam, Jawahar [19]. The comparative analyses for CTV results for all 60 instances are presented in Table 7 to Table 12.

It can be seen from Table 7 to Table 12, that the proposed methodology was able to find a solution very close to previously best known solutions. For 20 Î 5 problem instances, the proposed method provided the same solutions for five instances, and the average RPD was 0.03%. Overall, the proposed GA results were worse than SA – 2020 and DPSO 1.

For 20 Î 10 problem instances, the proposed method provided the same solutions for three instances with an average RPD of 0.23%. The proposed methodology solution was only better than ACO.

For 20 Î 20 problem instances, the proposed method provided the same solutions for two instances with an average RPD of 0.61%. In this case also, the proposed methodology solution was only better than ACO.

For 50 Î 5 problem instances, the proposed method did not find the same solutions for any of the instances. The average RPD was 0.61% for the proposed method. In this case too, the proposed methodology solution was only better than ACO.

Table 7

Comparative Analysis of Proposed Methodology with Previous Studies for Data Set 4 – 20 × 5

Table 8

Comparative Analysis of Proposed Methodology with Previous Studies for Data Set 4 – 20 × 10

Table 9

Comparative Analysis of Proposed Methodology with Previous Studies for Data Set 4 – 20 × 20

Table 10

Comparative Analysis of Proposed Methodology with Previous Studies for Data Set 4 – 50 × 5

Table 11

Comparative Analysis of Proposed Methodology with Previous Studies for Data Set 4 – 50 × 10

Table 12

Comparative Analysis of Proposed Methodology with Previous Studies for Data Set 4 – 50 × 20

For 50 Î 10 problem instances, the proposed method did not find the same solutions for any of the instances. The average RPD was 2.19% for the proposed method. For 50 Î 10 problem instances, the proposed method did not find the same solutions for any of the instances. The average RPD was 4.17% for the proposed method.

From the discussion in the preceding paragraphs, we can see that the proposed GA methodolgy found optimal solutions fo all single machine and unrestricted parallel machine scenarios. For n Î m flowshop problems, the solution quality deteriorated as the problem size increased. However, for small-to-medium-sized problems, the soultion quality of the proposed methodology was comparable with other heuristic techniques.

5. Conclusions

Most of the research on flowshop scheduling addresses the problem with regular performance measures like, makespan, flowtime etc. Very little work has been carried out with non-regular performance measures. Completion time variance (CTV) is one of the non-regular objective functions that penalizes both earliness and tardiness. CTV has direct relevance with JIT where it is desired that a job is completed exactly on time, neither early, as it will incur inventory holding cost, nor late, as it will result in products being delivered late thus, resulting in bad reputation for the company.

In this research, minimization of completion time variance (CTV) in a flowshop was addressed. A general purpose domain-independent GA Evolver that works as an add-in to Microsoft Excel spreadsheet was used for the optimization of the schedules. The shop models for flowshop were made in the spreadsheet using the built-in functions and formulae.

The proposed approach offers an easy-to-handle framework for the practitioners who are used to tools like spreadsheets. The proposed methodology allows practitioners to implement a heuristic-based optimization tool without the need for advanced progamming skills. Furthermore, due to the arrangement of data in linked cells via the spreadsheet, it is very convenient to carry out what-if analysis thus, looking at the effect of change due to various parameters. Additionally, the proposed approach can be used to optimize any objective function without the need to change the spreadsheet model of the basic GA routine. The proposed methodology can also be enhanced with the use of Viusal Basic for Application (VBA) language available within the Excel spreadsheet.

Even though the performance of the proposed methodology was not very promising for large-sized problems, computational experiments demonstrated that the proposed methodolgy can find optimal solutions for small-to-medium-sized problems.

Acknowledgements

This research has been funded by Scientific Research Deanship at University of Ha’il – Saudi Arabia through Project number RG – 20 028.

References

1. Merten, A.G. and M.E. Muller, Variance minimization in single machine sequencing problem. Management Science, 1972. 18(9): p. 518-528.
2. Eilon, S. and I.G. Chowdhury, Minimising Waiting Time Variance in the Single Machine Problem. Management Science, 1977. 23(6): p. 567-575.
3. Nasini, S. and R. Nessah, An almost exact solution to the min completion time variance in a single machine. European Journal of Operational Research, 2021. 294(2): p. 427-441.
4. Wang, S. and Y. Lu, A branch and price algorithm for single-machine completion time variance. Computers & Operations Research, 2019. 109: p. 188-199.
5. Viswanathkumar, G. and G. Srinivasan, A branch and bound algorithm to minimize completion time variance on a single processor. Computers & Operations Research, 2003. 30(8): p. 1135-1150.
6. Sharma, P., Permutation Polyhedra and Minimisation of the Variance of Completion Times on a Single Machine. Journal of Heuristics, 2002. 8(4): p. 467-485.
7. Gupta, M.C., Y.P. Gupta, and A. Kumar, Minimizing flow time variance in a single machine system using genetic algorithms. European Journal of Operational Research, 1993. 70(3): p. 289-303.
8. Kubiak, W., Completion time variance minimization on a single machine is difficult. Operations Research Letters, 1993. 14(1): p. 49–59.
9. Çolak, M. and G.A. Keskin, An extensive and systematic literature review for hybrid flowshop scheduling problems. International Journal of Industrial Engineering Computations, 2022. 13(2): p. 185-222.
10. Lee, T.-S. and Y.-T. Loong, A review of scheduling problem and resolution methods in flexible flow shop. International Journal of Industrial Engineering Computations, 2019. 10(1): p. 67-88.
11. González-Neira, E.M., J.R. Montoya-Torres, and D. Barrera, Flow-shop scheduling problem under uncertainties: Review and trends. International Journal of Industrial Engineering Computations, 2017. 8(4): p. 399-426.
12. Marangos, C.A., et al., Algorithms to minimize completion time variance in a two machine flowshop. Computers & Industrial Engineering, 1998. 35(1): p. 101-104.
13. Gowrishankar, K., C. Rajendran, and G. Srinivasan, Flow shop scheduling algorithms for minimizing the completion time variance and the sum of squares of completion time deviations from a common due date. European Journal of Operational Research, 2001. 132(3): p. 643-665.
14. Chandrasekaran, S., et al. An Application of Particle Swarm Optimization Algorithm to Permutation Flowshop Scheduling Problems to Minimize Makespan, Total Flowtime and Completion Time Variance. in IEEE International Conference on Automation Science and Engineering. 2006.
15. Taillard, E., Benchmarks for basic scheduling problems. European Journal of Operational Research, 1993. 64(2): p. 278-285.
16. Gajpal, Y. and C. Rajendran, An ant-colony optimization algorithm for minimizing the completion-time variance of jobs in flowshops. International Journal of Production Economics, 2006. 101(2): p. 259-272.
17. Chandrasekaran, S., et al. Multi-objective particle swarm optimization algorithm for scheduling in flowshops to minimize makespan, total flowtime and completion time variance. in IEEE Congress on Evolutionary Computation. 2007.
18. Chen, Y., X. Li, and S. Kumanan, Job completion time variance minimization on identical parallel machines, in Proceedings of the 2007 Industrial Engineering Research Conference, G. Bayraksan, et al., Editors. 2007: Pittsburgh, PA.
19. Ponnambalam, S.G., N. Jawahar, and S. Chandrasekaran, Discrete Particle Swarm Optimization Algorithm for Flowshop Scheduling, in Particle Swarm Optimization, A. Lazinica, Editor. 2009, IntechOpen.
20. Srirangacharyulu, B. and G. Srinivasan, Completion time variance minimization in single machine and multi-machine systems. Computers & Operations Research, 2010. 37(1): p. 62-71.
21. Li, X., Y. Chen, and Y. Sun, Minimizing job completion time variance for service stability on identical parallel machines. Computers & Industrial Engineering, 2010. 58(4): p. 729-738.
22. Rameshkumar, K., C. Rajendran, and K.M. Mohanasundaram, Discrete particle swarm optimisation algorithms for minimising the completion-time variance of jobs in flowshops. International Journal of Industrial and Systems Engineering, 2011. 7(3): p. 317-340.
23. Krishnaraj, J., et al., A modified ant-colony optimisation algorithm to minimise the completion time variance of jobs in flowshops. International Journal of Production Research, 2012. 50(20): p. 5698-5706.
24. Mehta, P., et al., An efficient local search for minimizing completion time variance in permutation flow shops. Computers & Operations Research, 2012. 39(5): p. 1000-1009.
25. Eren, T., Minimizing Completion Time Variance in a Flowshop Scheduling Problem with a Learning Effect. Gazi University Journal of Science, 2013. 26(3): p. 389-397.
26. Lee, W.-C., J.-Y. Wang, and M.-C. Lin, A branch-and-bound algorithm for minimizing the total weighted completion time on parallel identical machines with two competing agents. Knowledge-Based Systems, 2016. 105: p. 68-82.
27. Rajkanth, R., C. Rajendran, and H. Ziegler, Heuristics to minimize the completion time variance of jobs on a single machine and on identical parallel machines. The International Journal of Advanced Manufacturing Technology, 2017. 88(5): p. 1923-1936.
28. Krishnaraj, J., et al., Simulated annealing algorithms to minimise the completion time variance of jobs in permutation flowshops. International Journal of Industrial and Systems Engineering, 2019. 31(4): p. 425-451.
29. Krishnaraj, J. and S. Thiagarajan, A two-phase simulated annealing algorithm to minimise the completion time variance of jobs in flowshops. International Journal of Process Management and Benchmarking, 2020. 10(2): p. 261-281.
30. Palisade, Evolver: The genetic algorithm super solver Version 4. 1998, New York, USA: Palisade Corporation.
31. Agrama, F.A.E.-M., Linear projects scheduling using spreadsheets features. Alexandria Engineering Journal, 2011. 50(2): p. 179-185.
32. Chaudhry, I.A. and M. Usman, Integrated process planning and scheduling using genetic algorithms. Technical Gazette, 2017. 24(5): p. 1401-1409.
33. Milutinović, L.Đ., et al., Control Model for Ground Crew Scheduling Problem at Small Airports: Case of Serbia. Transport, 2021. 36(3): p. 235-245.
34. Amaral, J. and D. Kuettner, Analyzing Supply Chains at HP Using Spreadsheet Models. INFORMS Journal on Applied Analytics, 2008. 38(4): p. 228-240.
35. Othman, S.N., N.H. Mustaffa, and R. Sallehuddin. Supply Chain Spreadsheet Simulation Optimization. in 2012 Fourth International Conference on Computational Intelligence, Modelling and Simulation. 2012.
36. Li, J., et al., Fuzzy Representation of Environmental Flow in Multi-Objective Risk Analysis of Reservoir Operation. Water Resources Management, 2021. 35(9): p. 2845-2861.
37. Jeon, B.-J. and B.-S. Kim, Development of Material Combination Model Considering Economics and Construction Efficiency for G-SEED Certification. Sustainability, 2021. 13(6): p. 3535.
38. Sperlich, A., et al., Energy Efficient Operation of Variable Speed Submersible Pumps: Simulation of a Ground Water Well Field. Water, 2018. 10(9): p. 1255.
39. Schellenberg, C., J. Lohan, and L. Dimache, Operational Optimisation of a Heat Pump System With Sensible Thermal Energy Storage Using Genetic Algorithm. Thermal Science, 2018. 22(5): p. 2189-2202.
40. Salama, T. and O. Moselhi, Multi-objective optimization for repetitive scheduling under uncertainty. Engineering, Construction and Architectural Management, 2019. 26(7): p. 1294-1320.
41. Arabpour Roghabadi, M. and O. Moselhi, Optimized crew selection for scheduling of repetitive projects. Engineering, Construction and Architectural Management, 2021. 28(6): p. 1517-1540.
42. Whitley, D. and K. Kauth. GENITOR: A different genetic algorithm. in Proceedings of the 1988 Rocky Mountain Conference on Artificial Intelligence. 1988.
43. Davis, L., Handbook of Genetic Algorithms. 1991, New York, USA: Van Nostrand Reinhold.
44. Mittenthal, J., M. Raghavachari, and A.I. Rana, A hybrid simulated annealing approach for single machine scheduling problems with non-regular penalty functions. Computers & Operations Research, 1993. 20(2): p. 103-111.
45. Al-Turki, U., C. Fedjki, and A. Andijani, Tabu search for a class of single-machine scheduling problems. Computers & Operations Research, 2001. 28(12): p. 1223-1230.
46. Kanet, J.J., Minimizing Variation of Flow Time in Single Machine Systems. Management Science, 1981. 27(12): p. 1453-1459.
47. Prasad, V.R. and D.K. Manna, Minimization of expected variance of completion times on single machine for stochastic jobs. Naval Research Logistics (NRL), 1997. 44(1): p. 97-108.
48. Ye, N., et al., Job scheduling methods for reducing waiting time variance. Computers & Operations Research, 2007. 34(10): p. 3069-3083.

Appendix A

Table A 1

Problem Set 1 Data

Table A 2

Problem Set 2 Data

Table A 3

Problem Set 3 Data – processing times from Uniform (1, 59)

Table A 4

Problem Set 3 Data – processing times from Normal (30; 10²)

Table A 5

Problem Set 3 Data – processing times from Exponential (30)

Table A 6

Problem Set 3 Data – processing times from Pareto (1.0345,1)

(¹) Corresponding Author

E-mail: i.chaudhry@uoh.edu.sa (Imran Ali Chaudhry)