×

A novel differential evolution algorithm for bi-criteria no-wait flow shop scheduling problems. (English) Zbl 1157.90423

Summary: This paper presents a novel discrete differential evolution (DDE) algorithm for solving the no-wait flow shop scheduling problems with makespan and maximum tardiness criteria. First, the individuals in the DDE algorithm are represented as discrete job permutations, and new mutation and crossover operators are developed based on this representation. Second, an elaborate one-to-one selection operator is designed by taking into account the domination status of a trial individual with its counterpart target individual as well as an archive set of the non-dominated solutions found so far. Third, a simple but effective local search algorithm is developed to incorporate into the DDE algorithm to stress the balance between global exploration and local exploitation. In addition, to improve the efficiency of the scheduling algorithm, several speed-up methods are devised to evaluate a job permutation and its whole insert neighborhood as well as to decide the domination status of a solution with the archive set. Computational simulation results based on the well-known benchmarks and statistical performance comparisons are provided. It is shown that the proposed DDE algorithm is superior to a recently published hybrid differential evolution (HDE) algorithm [B. Qian et al., Comput. Oper. Res. 36, No. 1, 209–233 (2009; Zbl 1163.90507)] and the well-known multi-objective genetic local search algorithm (IMMOGLS2) [H. Ishibuchi, Balance between genetic search and local search in memetic algorithms for multiobjective permutation flowshop scheduling. IEEE Trans. Evolutionary Comput. 7, No. 2, 204–223 (2003)] in terms of searching quality, diversity level, robustness and efficiency. Moreover, the effectiveness of incorporating the local search into the DDE algorithm is also investigated.

MSC:

90B35 Deterministic scheduling theory in operations research
90B50 Management decision making, including multiple objectives

Citations:

Zbl 1163.90507
PDF BibTeX XML Cite
Full Text: DOI

References:

[1] Qian, B.; Wang, L.; Huang, D.X.; Wang, W.L.; Wang, X., An effective hybrid DE-based algorithm for multi-objective flow shop scheduling with limited buffers, Computers & operations research, 36, 1, 209-233, (2009) · Zbl 1163.90507
[2] Ishibuchi, H.; Yoshida, I.; Murata, T., Balance between genetic search and local search in memetic algorithms for multiobjective permutation flowshop scheduling, IEEE transactions on evolutionary computation, 7, 2, 204-223, (2003)
[3] Rajendran, C., A no-wait flowshop scheduling heuristic to minimize makespan, Journal of the operational research society, 45, 472-478, (1994) · Zbl 0799.90060
[4] Hall, N.G.; Sriskandarayah, C., A survey of machine scheduling problems with blocking and no-wait in process, Operations research, 44, 510-525, (1996) · Zbl 0864.90060
[5] Grabowski, J.; Pempera, J., Sequencing of jobs in some production system, European journal of operational research, 125, 535-550, (2003) · Zbl 0967.90045
[6] Raaymakers, W.; Hoogeveen, J., Scheduling multipurpose batch process industries with no-wait restrictions by simulated annealing, European journal of operational research, 126, 131-151, (2000) · Zbl 0970.90034
[7] Rock, H., The three-machine no-wait flowshop problem is NP-complete, Journal of associate computer machinery, 31, 336-345, (1984) · Zbl 0632.68038
[8] Bonney, M.C.; Gundry, S.W., Solutions to the constrained flowshop sequencing problem, Operational research quarterly, 24, 869-883, (1976) · Zbl 0345.90020
[9] King, J.R.; Spachis, A.S., Heuristics for flowshop scheduling, International journal of production research, 18, 343-357, (1980)
[10] Gangadharan, R.; Rajedran, C., Heuristic algorithms for scheduling in no-wait flowshop, International journal of production economics, 32, 285-290, (1993)
[11] Rajendran, C., A no-wait flowshop scheduling heuristic to minimize makespan, Journal of the operational research society, 45, 472-478, (1994) · Zbl 0799.90060
[12] Rajendran, C.; Chaudhuri, D., Heuristic algorithms for continuous flow-shop problem, Naval research logistics, 37, 695-705, (1990) · Zbl 0707.90052
[13] Aldowaisan, T.; Allahverdi, A., A new heuristics for no-wait flowshops to minimize makespan, Computers & operations research, 30, 1219-1231, (2003) · Zbl 1047.90053
[14] Fink, A.; Voß, S., Solving the continuous flow-shop scheduling problem by metaheuristics, European journal of operational research, 151, 400-414, (2003) · Zbl 1052.90030
[15] Schuster, C.J.; Framinan, J.M., Approximate procedure for no-wait job shop scheduling, Operations research letters, 31, 308-318, (2003) · Zbl 1041.90019
[16] Grabowski, J.; Pempera, J., Some local search algorithms for no-wait flow-shop problem with makespan criterion, Computers & operations research, 32, 2197-2212, (2005) · Zbl 1068.90058
[17] Pan, Q.K.; Wang, L.; Zhao, B.H., An improved iterated greedy algorithm for the no-wait flow shop scheduling problem with makespan criterion, International journal of advanced manufacturing technology, 38, 7-8, 778-786, (2008)
[18] Liu, B.; Wang, L.; Jin, Y.H., An effective hybrid particle swarm optimization for no-wait flow shop scheduling, International journal of advanced manufacturing technology, 31, 1001-1011, (2007)
[19] Pan, Q.K.; Tasgetiren, M.F.; Liang, Y.C., A discrete particle swarm optimization algorithm for the no-wait flowshop scheduling problem, Computers & operations research, 35, 2807-2839, (2008) · Zbl 1144.90393
[20] Pan, Q.K.; Wang, L.; Tasgetirend, M.F.; Zhao, B.H., A hybrid discrete particle swarm optimization algorithm for the no-wait flow shop scheduling problem with makespan criterion, International journal of advanced manufacturing technology, 38, 337-347, (2008)
[21] Daniels, R.L.; Chambers, R.J., Multiobjective flow-shop scheduling, Naval research logistics, 37, 981-995, (1990) · Zbl 0825.90551
[22] Ravindran, D.; Noorul Haq, A.; Selvakuar, S.J.; Sivaraman, R., Flow shop scheduling with multiple objective of minimizing makespan and total flow time, International journal of advanced manufacturing technology, 25, 1007-1012, (2005)
[23] T’Kindt, V.; Monmarche, N.; Tercinet, F.; Laugt, D., An ant colony optimization algorithm to solve a 2-machine bicriteria flowshop scheduling problem, European journal of operational research, 142, 250-257, (2002) · Zbl 1082.90592
[24] Loukil, T.; Teghem, J.; Tuyttens, D., Solving multi-objective production scheduling problems using metaheuristics, European journal of operational research, 161, 42-61, (2005) · Zbl 1065.90040
[25] Deb, K.; Pratap, A.; Agarwal, S.; Meyarivan, T., A fast and elitist multiobjective genetic algorithm: NSGA-II, IEEE transactions on evolutionary computation, 6, 2, 182-197, (2002)
[26] Arroyo, J.E.C.; Armentano, V.A., Genetic local search for multi-objective flowshop scheduling problems, European journal of operational research, 167, 717-738, (2005) · Zbl 1077.90023
[27] Li, B.B.; Wang, L., A hybrid quantum-inspired genetic algorithm for multiobjective flow shop scheduling, IEEE transactions on systems, man and cybernetics part B, 37, 576-591, (2007)
[28] Pasupathy, T.; Rajendran, C.; Suresh, R.K., A multi-objective genetic algorithm for scheduling in flow shops to minimize the makespan and total flow time of jobs, International journal of advanced manufacturing technology, 27, 804-815, (2006)
[29] Varadharajan, T.K.; Rajendran, C., A multi-objective simulated-annealing algorithm for scheduling in flowshops to minimize the makespan and total flowtime of jobs, European journal of operational research, 167, 722-795, (2005) · Zbl 1154.90499
[30] Suresh, R.K.; Mohanasundaram, K.M., Pareto archived simulated annealing for job shop scheduling with multiple objectives, International journal of advanced manufacturing technology, 29, 184-196, (2006)
[31] Aliahverdi, A.; Aldowaisan, T., No-wait flowshops with bicriteria of makespan and maximum lateness, European journal of operational research, 152, 132-147, (2004) · Zbl 1044.90040
[32] Tavakkoli-Moghaddam, R.; Rahimi-Vahed, A.; Mirzaei, A.H., A hybrid multi-objective immune algorithm for a flow shop scheduling problem with bi-objectives: weighted mean completion time and weighted Mean tardiness, Information sciences, 177, 22, 5072-5090, (2007) · Zbl 1121.90340
[33] Chen P, Bulfin R. Complexity of multiple machine multicriteria scheduling problems. In: Proceedings of the third IERC, Atlanta, GA; 1994.
[34] T’Kindt V, Billaut JC. Multicriteria optimisation theory. In: Multicriteria scheduling: theory, models and algorithms. Berlin, Germany: Springer; 2002.
[35] Storn, R.; Price, K., Differential evolution—a simple and efficient adaptive scheme for global optimization over continuous spaces, Journal of global optimization, 11, 341-359, (1997) · Zbl 0888.90135
[36] Ilonen, J.; Kamarainen, J.K.; Lampinen, J., Differential evolution training algorithm for feed-forward neural networks, Neural process letters, 17, 93-105, (2003)
[37] Ruzek, B.; Kvasnicka, M., Differential evolution in the earthquake hypocenter location, Pure and applied geophysics, 158, 667-693, (2001)
[38] Qian, B.; Wang, L.; Hu, R., A hybrid differential evolution for permutation flow-shop scheduling, International journal of advanced manufacturing technology, 38, 7-8, 757-777, (2008)
[39] Onwubolu, G.C.; Davendra, D., Scheduling flow shops using differential evolution algorithm, European journal of operational research, 171, 2, 674-692, (2006) · Zbl 1090.90090
[40] Tasgetiren MF, Pan QK, Suganthan PN, Liang YC. A discrete differential evolution algorithm for the no-wait flowshop problem with total flowtime criterion. In: Proceedings of the 2007 IEEE symposium on computational intelligence in scheduling; 2007. p. 251-8.
[41] Tasgetiren, M.F.; Sevkli, M.; Liang, Y.C., A particle swarm optimization and differential algorithm for job shop scheduling problem, International journal of operations research, 3, 120-135, (2006) · Zbl 1175.90194
[42] Nawaz, M.; Enscore, E.E.J.; Ham, I., A heuristic algorithm for the m-machine, n-job flow shop sequencing problem, OMEGA—international journal of management science, 11, 91-95, (1983)
[43] Wang, L., Shop scheduling with genetic algorithms, (2003), Tsinghua University Press, Springer Beijing
[44] Schiavinotto, T.; Stuzle, T., A review of metrics on permutations for search landscape analysis, Computers & operations research, 34, 10, 3143-3153, (2007) · Zbl 1185.90115
[45] Silva JDL, Burke EK, Petrovic S. An introduction to multiobjective metaheuristics for scheduling and timetabling. In: Lecture notes in economics and mathematical systems, vol. 535; 2004. p. 91-129. · Zbl 1139.90420
[46] Czyzak, P.; Jaszkiewicz, A., Pareto-simulated annealing—a meta-heuristic techniques for multi-objective combinatorial optimization, Journal of multi-criteria decision analysis, 7, 1, 34-47, (1998) · Zbl 0904.90146
[47] Knowles JD, Corne DW. On metrics for comparing nondominated sets. In: Proceedings of 2002 congress on evolutionary computation, Honolulu, HI, 12-17 May 2002. p. 711-6.
[48] Carlier, J., Ordonnancements a contraintes disjonctives, RAIRO—recherche operationnelle, 12, 333-351, (1978) · Zbl 0401.90052
[49] Reeves, C., A genetic algorithm for flowshop sequencing, Computers & operations research, 22, 5-13, (1995) · Zbl 0815.90097
[50] Heller, J., Some numerical experiments for an M×J flow shop and its decision-theoretical aspects, Operations research, 8, 178-184, (1960) · Zbl 0092.27910
[51] Zitzler, E.; Thiele, L., Multiobjective evolutionary algorithms: a comparison case study and the strength Pareto approach, IEEE transactions on evolutionary computation, 3, 4, 257-271, (1999)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.