Some local search algorithms for no-wait flow-shop problem with makespan criterion. (English) Zbl 1068.90058
Summary: This paper develops and compares different local search algorithms for the no-wait flow-shop problem with makespan criterion (C\(_{\max}\)). We present several variants of descending search and tabu search algorithms. In the algorithms the multimoves are used that consist in performing several moves simultaneously in a single iteration of algorithm and allow us to accelerate the convergence to good solutions. Besides, in the tabu search algorithms a dynamic tabu list is proposed that assists additionally to avoid trapped at a local optimum. The proposed algorithms are empirically evaluated and found to be relatively more effective in finding better quality solutions than existing algorithms. The presented ideas can be applied in any local search procedures.
References:
| [1] | Wismer, D. A., Solution of the flowshop-scheduling with no intermediate queues, Operations Research, 20, 689-697 (1972) · Zbl 0241.90031 |
| [2] | 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 |
| [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] | 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 |
| [5] | Grabowski, J.; Pempera, J., Sequencing of jobs in some production system, European Journal of Operational Research, 125, 535-550 (2000) · Zbl 0967.90045 |
| [6] | Reddi, S. S.; Ramamoorthy, C. V., On the flowshop sequencing problem with no-wait in process, Operational Research Quarterly, 23, 323-331 (1972) · Zbl 0238.90080 |
| [7] | Grabowski, J.; Syslo, M., On some machine Sequencing problems (I), Applications of Mathematicae, 13, 340-345 (1973) · Zbl 0259.90028 |
| [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] | Glass, C. A.; Gupta, J. N.D.; Potts, C. N., Two-machine no-wait flow shop scheduling with missing operations, Mathematics of Operations Research, 24, 4, 911-924 (1999) · Zbl 0977.90014 |
| [12] | Sidney, J. B.; Potts, C. N.; Sriskandarayah, C., Heuristic for scheduling two-machine no-wait flow shops with anticipatory setups, Operations Research Letters, 26, 4, 165-173 (2000) · Zbl 0971.90032 |
| [13] | Svirenko, M., Makespan minimization in no-wait flow shopsA polynomial time approximation scheme, SIAM Journal on Discrete Mathematics, 16, 2, 313-322 (2003) · Zbl 1045.90034 |
| [14] | Aldowaisan, T.; Allahverdi, A., New heuristics for no-wait flowshops to minimize makespan, Computers and Operations Research, 30, 1219-1231 (2003) · Zbl 1047.90053 |
| [15] | Schuster, C. J.; Framinan, J. M., Approximative procedures for no-wait job shop scheduling, Operations Research Letters, 31, 308-318 (2003) · Zbl 1041.90019 |
| [16] | Gilmore, P. C.; Lawler, E. L.; Shmoys, D. B., Well-solved special cases, (Lawler, E. L.; Lenstra, J. K.; Rinnooy Kan, A. H.G.; Shmoys, D. B., The traveling salesman problem: a guided tour of combinatorial optimization (1985), Wiley: Wiley Chichester), 87-143 · Zbl 0631.90081 |
| [17] | Gilmore, P. C.; Gomory, R. E., Sequencing a one-state variable machinea solvable case of the traveling salesman problem, Operations Research, 12, 655-679 (1964) · Zbl 0126.36006 |
| [18] | Grabowski, J.; Pempera, J., New block properties for the permutation flow-shop problem with application in TS, Journal of the Operational Research Society, 52, 210-220 (2001) · Zbl 1131.90359 |
| [19] | Glover, F., Tabu search. Part I, ORSA Journal of Computing, 1, 190-206 (1989) · Zbl 0753.90054 |
| [20] | Glover, F., Tabu search. Part II, ORSA Journal of Computing, 2, 4-32 (1990) · Zbl 0771.90084 |
| [21] | Grabowski J, Wodecki M. A very fast tabu search algorithm for the job shop problem. In: Rego C, Alidaee B, editors. Adaptive memory and evolution; tabu search and scatter search. Dordrecht: Kluwer Academic Publishers, 2004; in print.; Grabowski J, Wodecki M. A very fast tabu search algorithm for the job shop problem. In: Rego C, Alidaee B, editors. Adaptive memory and evolution; tabu search and scatter search. Dordrecht: Kluwer Academic Publishers, 2004; in print. · Zbl 1068.68143 |
| [22] | Grabowski, J.; Wodecki, M., A very fast tabu search algorithm for the flow shop problem with makespan criterion, Computers and Operations Research, 11, 1891-1909 (2004) · Zbl 1068.68143 |
| [23] | Nawaz, M.; Enscore, E.; Ham, I., A Heuristic algorithm for the \(m\)-machine, \(n\)-job flow-shop sequencing problem, OMEGA The International Journal of Management Science, 11, 91-95 (1983) |
| [24] | Carlier, J., Ordonnancements a Contraintes Disjonctives, RAIRO Recherche Operationnelle, 12, 333-351 (1978) · Zbl 0401.90052 |
| [25] | 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 |
| [26] | Reeves, C. R., A Genetic algorithm for flow shop sequencing, Computers and Operations Research, 22, 5-13 (1995) · Zbl 0815.90097 |
| [27] | Dongarra JJ. Performance of various computers using standard linear equations software. Working paper. Computer Science Department, University of Tennessee, USA, 2001. http://www.netlib.org/benchmark/performance.ps.; Dongarra JJ. Performance of various computers using standard linear equations software. Working paper. Computer Science Department, University of Tennessee, USA, 2001. http://www.netlib.org/benchmark/performance.ps. |
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
