An empirical analysis of the optimality rate of flow shop heuristics

Agarval, 2006, Improvement heuristic for the flow-shop scheduling problem: An adaptive-learning approach, European Journal of Operational Research, 169, 801, 10.1016/j.ejor.2004.06.039 Aldowaisan, 2003, New heuristics for no-wait flowshops to minimize makespan, Computers & Operations Research, 30, 1219, 10.1016/S0305-0548(02)00068-0 Campbell, 1970, A heuristic algorithm for the n job m machine sequencing problem, Management Science, 16, 630, 10.1287/mnsc.16.10.B630 Chakraborty, 2007, An improved heuristic for permutation flowshop scheduling, International Journal of Information and Communication Technology, 1, 89, 10.1504/IJICT.2007.013279 Chen, 1998, A review of machine scheduling: Complexity, algorithms and approximability, 21 Companys, 2007, Different behaviour of a double branch-and-bound-algorithm on Fm∣prmu∣Cmax and Fm∣block∣Cmax problems, Computers & Operations Research, 34, 938, 10.1016/j.cor.2005.05.018 Dannenbring, 1977, An evaluation of flow-shop sequencing heuristics, Management Science, 23, 1174, 10.1287/mnsc.23.11.1174 Dong, 2008, An improved NEH-based heuristic for the permutation flowshop problem, Computers and Operations Research, 35, 3962, 10.1016/j.cor.2007.05.005 Ekşioğlu, 2008, A tabu search algorithm for the flowshop scheduling problem with changing neighbourhoods, Computers and Industrial Engineering, 54, 1, 10.1016/j.cie.2007.04.004 Etiler, 2004, A genetic algorithm for flow shop scheduling problem, Journal of the Operational Research Society, 55, 830, 10.1057/palgrave.jors.2601766 Framinan, 2003, Different initial sequences for the heuristic of Nawaz, Enscore and Ham to minimize makespan, idle time or flowtime in the static permutation flowshop problem, International Journal of Production Research, 41, 121, 10.1080/00207540210161650 Framinan, 2004, A review and classification of heuristics for permutation flow-shop scheduling with makespan objective, Journal of the Operational Research Society, 55, 1243, 10.1057/palgrave.jors.2601784 Gao, 2007, Enhanced NEH method in solving permutation flow shop problem, Journal of Shanghai Jiaotong University (Science), 12, 47 Garey, 1976, The complexity of flow shop and job shop scheduling, Mathematics of Operations Research, 1, 117, 10.1287/moor.1.2.117 Gilmore, 1964, Sequencing a one state variable machine: A solvable case of the traveling salesman problem, Operations Research, 12, 655, 10.1287/opre.12.5.655 Glynn, 1991, Departures from many queues in series, Annals of Applied Probability, 1, 546, 10.1214/aoap/1177005838 Grabowski, 2005, Some local search algorithms for no-wait flow-shop problem with makespan criterion, Computers & Operations Research, 32, 2197, 10.1016/j.cor.2004.02.009 Grabowski, 2007, The permutation flowshop problem with blocking. A tabu search approach, Omega, the International Journal of Management Science, 35, 302, 10.1016/j.omega.2005.07.004 Grabowski, 2004, A very fast tabu search algorithm for the permutation flow shop problem with makespan criterion, Computers & Operations Research, 31, 1891, 10.1016/S0305-0548(03)00145-X Gupta, 2006, Performance guarantees for flowshop heuristics to minimize makespan, European Journal of Operational Research, 169, 865, 10.1016/j.ejor.2004.05.034 Hall, 1998, Approximability of flow shop scheduling, Mathematical Programming, 82, 175, 10.1007/BF01585870 Haq, 2007, A scatter search approach for general flow shop scheduling problem, International Journal of Advanced Manufacturing Technology, 31, 751 Iyer, 2004, Improved genetic algorithm for the permutation flowshop scheduling problem, Computers and Operations Research, 31, 593, 10.1016/S0305-0548(03)00016-9 James, 1996, RANLUX: A Fortran implementation of the high-quality pseudorandom number generator of Luscher, Computer Physics Communications, 97, 357, 10.1016/0010-4655(96)00065-3 Jarboui, 2008, A combinatorial particle swarm optimisation for solving permutation flowshop problems, Computers & Industrial Engineering, 54, 526, 10.1016/j.cie.2007.09.006 Jin, 2007, An improved version of the NEH algorithm and its application to large-scale flow-shop scheduling problems, IIE Transactions, 39, 229, 10.1080/07408170600735553 Johnson, 1954, Optimal two- and three-stage production schedules with setup times included, Naval Research Logistics Quarterly, 1, 61, 10.1002/nav.3800010110 Johnson, 1959, Discussion: Sequencing n jobs on two machines with arbitrary time lags, Management Science, 5, 299, 10.1287/mnsc.5.3.299 Kalczynski, 2007, On the NEH heuristic for minimizing the makespan in permutation flowshops, Omega, The International Journal of Management Science, 35, 53, 10.1016/j.omega.2005.03.003 Kalczynski, 2008, An improved NEH heuristic to minimize makespan in permutation flow shops, Computers & Operations Research, 35, 3001, 10.1016/j.cor.2007.01.020 Koryakin, 2004, On asymptotic optimality of permutation schedules in stochastic flow shops and assembly lines, Operations Research Proceedings, Part 6, 200 Ladhari, 2005, A computational study of the permutation flow shop problem based on a tight lower bound, Computers & Operations Research, 32, 1831, 10.1016/j.cor.2003.12.001 Laha, 2007, Improved heuristically guided genetic algorithm for the flow shop scheduling problem, International Journal of Services and Operations Management, 3, 313, 10.1504/IJSOM.2007.013095 Lenstra, 1977, Complexity of machine scheduling problems, Annals of Discrete Mathematics, 1, 343, 10.1016/S0167-5060(08)70743-X Liao, 2007, A discrete version of particle swarm optimization for flowshop scheduling problems, Computers & Operations Research, 34, 3099, 10.1016/j.cor.2005.11.017 Liu, 2007, An effective hybrid particle swarm optimization for no-wait flow shop scheduling, International Journal of Advanced Manufacturing Technology, 31, 1001, 10.1007/s00170-005-0277-5 Liu, 2007, An effective PSO-based memetic algorithm for flow shop scheduling, IEEE Transactions on Systems, Man and Cybernetics – Part B. Cybernetics, 37, 18, 10.1109/TSMCB.2006.883272 Lourenço, 1996, Sevast’janov’s algorithm for the flow-shop scheduling problem, European Journal of Operational Research, 91, 176, 10.1016/0377-2217(94)00356-4 McMahon, 1971 Nawaz, 1983, A heuristic algorithm for the m-machine, n-job flow-shop sequencing problem, Omega, The International Journal of Management Science, 11, 91, 10.1016/0305-0483(83)90088-9 Nowicki, 1999, The permutation flow shop with buffers: A tabu search approach, European Journal of Operational Research, 116, 205, 10.1016/S0377-2217(98)00017-4 Nowicki, 1993, New results in the worst-case analysis for flow-shop scheduling, Discrete Applied Mathematics, 46, 21, 10.1016/0166-218X(93)90156-I Nowicki, 1994, A note on worst-case analysis of approximation algorithms for a scheduling problem, European Journal of Operational Research, 74, 128, 10.1016/0377-2217(94)90210-0 Nowicki, 2006, Some aspects of scatter search in the flow-shop problem, European Journal of Operational Research, 169, 654, 10.1016/j.ejor.2004.08.021 Onwubolu, 2006, Scheduling flow shops using differential evolution algorithm, European Journal of Operational Research, 171, 674, 10.1016/j.ejor.2004.08.043 Pan, Q.-K, Tasgetiren, M.F., Liang, Y.-C., 2007. A discrete differential evolution algorithm for the permutation flowshop scheduling problem. In: Ninth Annual Conference o Genetic and Evolutionary Computation, GECCO ‘07. London, UK. Pinedo, 2002 Portougal, 1993, Asymptotic behaviour of some scheduling algorithms, Asia-Pacific Journal of Operational Research, 10, 79 Portougal, 2001, The asymptotic convergence of some flow-shop scheduling heuristics, Asia-Pacific Journal of Operational Research, 18, 243 Prabhaharan, 2006, Implementation of grasp in flow shop scheduling, International Journal of Advanced Manufacturing Technology, 30, 1126, 10.1007/s00170-005-0134-6 Psaraftis, 1984, On the practical importance of asymptotic optimality in certain heuristic algorithms, Networks, 14, 587, 10.1002/net.3230140409 Rad, 2009, New high performing heuristics for minimizing makespan in permutation flowshops, Omega, The International Journal of Operational Research, 37, 331, 10.1016/j.omega.2007.02.002 Rajendran, 2004, Ant-colony algorithms for permutation flowshop scheduling to minimize makespan/total flowtime of jobs, European Journal of Operational Research, 155, 426, 10.1016/S0377-2217(02)00908-6 Ramudhin, 1996, A probabilistic analysis of two-machine flowshops, Operations Research, 44, 899, 10.1287/opre.44.6.899 Reza Hejazi, 2005, Flowshop-scheduling with makespan criterion: a review, International Journal of Production Research, 43, 2895, 10.1080/0020754050056417 Ruiz, 2005, A comprehensive review and evaluation of permutation flowshop heuristics, European Journal of Operational Research, 165, 479, 10.1016/j.ejor.2004.04.017 Ruiz, 2007, A simple and effective iterated greedy algorithm for the permutation flowshop scheduling problem, European Journal of Operational Research, 177, 2033, 10.1016/j.ejor.2005.12.009 Ruiz, 2006, Two new robust genetic algorithms for the flowshop scheduling problem, Omega, The International Journal of Management Science, 34, 461, 10.1016/j.omega.2004.12.006 Schuurman, P., Woeginger, G.J., 2007. Approximation schemes – a tutorial. In: Moehring, R.H., Potts, C.N., Schulz, A.S., Woeginger, G.J., Wolsey, L.A. (Eds), Lectures on Scheduling. (available online). Sevast’janov, 1995, Vector summation in Banach space and polynomial algorithms for flow shops and open shops, Mathematics of Operations Research, 20, 90, 10.1287/moor.20.1.90 Shmoys, 1994, Improved approximation algorithms for shop scheduling problems, SIAM Journal on Computing, 23, 617, 10.1137/S009753979222676X Smutnicki, 1998, Some results of the worst-case analysis for flow shop scheduling, European Journal of Operational Research, 109, 66, 10.1016/S0377-2217(97)00139-2 Suliman, 2000, A two-phase heuristic approach to the permutation flow-shop scheduling problem, International Journal of Production Economics, 64, 143, 10.1016/S0925-5273(99)00053-5 Sviridenko, 2004, A note on the permutation flow shop problem, Annals of Operations Research, 129, 247, 10.1023/B:ANOR.0000030691.65576.28 Taillard, 1990, Some efficient heuristic methods for the flow shop sequencing problem, European Journal of Operational Research, 47, 65, 10.1016/0377-2217(90)90090-X Taillard, 1993, Benchmarks for basic scheduling problems, European Journal of Operational Research, 64, 278, 10.1016/0377-2217(93)90182-M Tasgetiren, 2007, A particle swarm optimization algorithm for makespan and total flowtime minimization in the permutation flowshop sequencing problem, European Journal of Operational Research, 177, 1930, 10.1016/j.ejor.2005.12.024 Ying, 2004, An ant colony system for permutation flow-shop sequencing, Computers & Operations Research, 31, 791, 10.1016/S0305-0548(03)00038-8