# zbMATH — the first resource for mathematics

##### Examples
 Geometry Search for the term Geometry in any field. Queries are case-independent. Funct* Wildcard queries are specified by * (e.g. functions, functorial, etc.). Otherwise the search is exact. "Topological group" Phrases (multi-words) should be set in "straight quotation marks". au: Bourbaki & ti: Algebra Search for author and title. The and-operator & is default and can be omitted. Chebyshev | Tschebyscheff The or-operator | allows to search for Chebyshev or Tschebyscheff. "Quasi* map*" py: 1989 The resulting documents have publication year 1989. so: Eur* J* Mat* Soc* cc: 14 Search for publications in a particular source with a Mathematics Subject Classification code (cc) in 14. "Partial diff* eq*" ! elliptic The not-operator ! eliminates all results containing the word elliptic. dt: b & au: Hilbert The document type is set to books; alternatively: j for journal articles, a for book articles. py: 2000-2015 cc: (94A | 11T) Number ranges are accepted. Terms can be grouped within (parentheses). la: chinese Find documents in a given language. ISO 639-1 language codes can also be used.

##### Operators
 a & b logic and a | b logic or !ab logic not abc* right wildcard "ab c" phrase (ab c) parentheses
##### Fields
 any anywhere an internal document identifier au author, editor ai internal author identifier ti title la language so source ab review, abstract py publication year rv reviewer cc MSC code ut uncontrolled term dt document type (j: journal article; b: book; a: book article)
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 Scheduling theory, deterministic 90B50 Management decision making, including multiple objectives
##### 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, No. 1, 209-233 (2009) [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, No. 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 · doi:10.1287/opre.44.3.510 [5] Grabowski, J.; Pempera, J.: Sequencing of jobs in some production system, European journal of operational research 125, 535-550 (2003) · Zbl 0967.90045 · doi:10.1016/S0377-2217(99)00224-6 [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 · doi:10.1016/S0377-2217(99)00285-4 [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 · doi:10.1145/62.65 [8] Bonney, M. C.; Gundry, S. W.: Solutions to the constrained flowshop sequencing problem, Operational research quarterly 24, 869-883 (1976) · Zbl 0345.90020 · doi:10.1057/jors.1976.176 [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 · doi:10.1002/1520-6750(199010)37:5<695::AID-NAV3220370508>3.0.CO;2-L [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 · doi:10.1016/S0305-0548(02)00068-0 [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 · doi:10.1016/S0377-2217(02)00834-2 [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 · doi:10.1016/S0167-6377(03)00005-1 [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 · doi:10.1016/j.cor.2004.02.009 [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, No. 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 · doi:10.1016/j.cor.2006.12.030 [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 · doi:10.1002/1520-6750(199012)37:6<981::AID-NAV3220370617>3.0.CO;2-H [22] Ravindran, D.; Haq, A. Noorul; 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 · doi:10.1016/S0377-2217(02)00265-5 [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 · doi:10.1016/j.ejor.2003.08.029 [25] Deb, K.; Pratap, A.; Agarwal, S.; Meyarivan, T.: A fast and elitist multiobjective genetic algorithm: NSGA-II, IEEE transactions on evolutionary computation 6, No. 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 · doi:10.1016/j.ejor.2004.07.017 [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 · doi:10.1016/j.ejor.2004.07.020 [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 · doi:10.1016/S0377-2217(02)00646-X [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, No. 22, 5072-5090 (2007) · Zbl 1121.90340 · doi:10.1016/j.ins.2007.06.001 [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 · doi:10.1023/A:1008202821328 [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, No. 7 – 8, 757-777 (2008) [39] Onwubolu, G. C.; Davendra, D.: Scheduling flow shops using differential evolution algorithm, European journal of operational research 171, No. 2, 674-692 (2006) · Zbl 1090.90090 · doi:10.1016/j.ejor.2004.08.043 [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) [44] Schiavinotto, T.; Stuzle, T.: A review of metrics on permutations for search landscape analysis, Computers & operations research 34, No. 10, 3143-3153 (2007) · Zbl 1185.90115 · doi:10.1016/j.cor.2005.11.022 [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, No. 1, 34-47 (1998) · Zbl 0904.90146 · doi:10.1002/(SICI)1099-1360(199801)7:1<34::AID-MCDA161>3.0.CO;2-6 [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 · doi:10.1016/0305-0548(93)E0014-K [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 · doi:10.1287/opre.8.2.178 [51] Zitzler, E.; Thiele, L.: Multiobjective evolutionary algorithms: a comparison case study and the strength Pareto approach, IEEE transactions on evolutionary computation 3, No. 4, 257-271 (1999)