×

Local search heuristics for two-stage flow shop problems with secondary criterion. (English) Zbl 1026.90103

Summary: This paper develops and compares different local search heuristics for the two-stage flow shop problem with makespan minimization as the primary criterion and the minimization of either the total flow time, total weighted flow time, or total weighted tardiness as the secondary criterion. We investigate several variants of simulated annealing, threshold accepting, tabu search, and multi-level search algorithms. The influence of the parameters of these heuristics and the starting solution are empirically analyzed. The proposed heuristic algorithms are empirically evaluated and found to be relatively more effective in finding better quality solutions than the existing algorithms.

MSC:

90C59 Approximation methods and heuristics in mathematical programming
90B35 Deterministic scheduling theory in operations research
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Dileepan, P.; Sen, T., Bicriterion static scheduling research for a single machine, OMEGA, 16, 1, 53-59 (1988)
[2] Fry, T. D.; Armstrong, R. D.; Lewis, H., A framework for single machine multiple objective sequencing research, OMEGA, 17, 6, 595-607 (1989)
[3] Hoogeveen H. Single-machine bicriteria scheduling. Ph.D. dissertation, Center for Mathematics and Computer Science, Amsterdam, The Netherlands, 1992.; Hoogeveen H. Single-machine bicriteria scheduling. Ph.D. dissertation, Center for Mathematics and Computer Science, Amsterdam, The Netherlands, 1992. · Zbl 0749.90042
[4] Lee C-Y, Vairaktarakis GL. Complexity of single machine hierarchical scheduling: a survey. Research Report No. 93-10, Department of Industrial and Systems Engineering, University of Florida, Gainesville, FL, USA, 1993.; Lee C-Y, Vairaktarakis GL. Complexity of single machine hierarchical scheduling: a survey. Research Report No. 93-10, Department of Industrial and Systems Engineering, University of Florida, Gainesville, FL, USA, 1993.
[5] Nagar, A.; Haddock, J.; Heragu, S., Multiple and bicriteria scheduling: a literature survey, Eur. J. Opl. Res., 81, 88-104 (1995) · Zbl 0913.90178
[6] Lawler EL, Lenstra JK, Rinnooy Kan AHG, Shmoys DB. Sequencing and scheduling: algorithms and complexity. In: Graves SC, Rinnooy Kan AHG, Zipkin PH, editors. Logistics of Production and Inventory. Amsterdam, The Netherlands: North-Holland, 1995. p. 445-522.; Lawler EL, Lenstra JK, Rinnooy Kan AHG, Shmoys DB. Sequencing and scheduling: algorithms and complexity. In: Graves SC, Rinnooy Kan AHG, Zipkin PH, editors. Logistics of Production and Inventory. Amsterdam, The Netherlands: North-Holland, 1995. p. 445-522.
[7] Johnson, S. M., Optimal two- and three-stage production schedules with set-up times included, Naval Research Logistic Quarterly, 1, 61-68 (1954) · Zbl 1349.90359
[8] Garey, M. R.; Johnson, D. S.; Sethi, R., The complexity of flow shop and job shop scheduling, Maths. Ops. Res., 1, 117-129 (1976) · Zbl 0396.90041
[9] Chen CL, Bulfin RL. Complexity results for multi-machine multi-criteria scheduling problems. Proceedings of the Third Industrial Engineering Research Conference, 1994; p. 662-5.; Chen CL, Bulfin RL. Complexity results for multi-machine multi-criteria scheduling problems. Proceedings of the Third Industrial Engineering Research Conference, 1994; p. 662-5.
[10] Rajendran, C., Two-stage flow shop scheduling problem with bicriteria, J. Ops. Res. Soc., 43, 9, 871-884 (1992) · Zbl 0757.90037
[11] Neppalli, V. R.; Chen, C.-. L.; Gupta, J. N.D., Genetic algorithms for the two-stage bicriteria flow shop problem, European Journal of Operational Research, 95, 356-373 (1996) · Zbl 0943.90584
[12] Gupta, J. N.D.; Palanimuthu, N.; Chen, C. L., Designing a tabu search algorithm for the two-stage flow shop problem with secondary criterion, Production Planning and Control: An International Journal, 10, 251-265 (1999)
[13] Gupta, J. N.D.; Neppalli, V. R.; Werner, F., Minimizing total flow time in a 2-machine flow shop problem with minimum makespan, International Journal of production Economics, 69, 323-338 (2001)
[14] Danneberg, D.; Tautenhahn, T.; Werner, F., A comparison of heuristic algorithms for flow shop scheduling problems with setup times and limited batch size, Math. Comput. Modell., 29, 101-126 (1999) · Zbl 0987.90032
[15] Sotskov, Y. N.; Tautenhahn, T.; Werner, F., Heuristics for permutation flow shop scheduling with batch setup times, OR Spektrum, 18, 67-80 (1996) · Zbl 0858.90079
[16] Metropolis, M.; Rosenbluth, A.; Rosenbluth, M.; Teller, A.; Teller, M., Equation of state calculations by fast computing machines, Journal of Chemical Physics, 21, 1087-1092 (1953) · Zbl 1431.65006
[17] Kirkpatrick, S.; Gelatt, C. D.; Vecchi, M. P., Optimization by simulated annealing, Science, 220, 671-680 (1983) · Zbl 1225.90162
[18] Cerny, V., Thermodynamical approach to the traveling salesman problem, Journal of Optimization Theory and Applications, 45, 41-51 (1985) · Zbl 0534.90091
[19] Lundy, M.; Mees, A., Convergence of an annealing algorithm, Mathematical Programming, 34, 111-124 (1986) · Zbl 0581.90061
[20] Dueck, G.; Scheuer, T., Threshold accepting: a general purpose optimization algorithm appearing superior to simulated annealing, Journal of Computational Physics, 90, 161-175 (1990) · Zbl 0707.65039
[21] Glass, C. A.; Potts, C. N., A comparison of local search methods for flow shop scheduling, Annals of Operations Research, 63, 489-509 (1996) · Zbl 0851.90064
[22] Glover, F., Tabu search, Part I, ORSA Journal of Computing, 1, 190-206 (1989) · Zbl 0753.90054
[23] Reeves, C. R., Modern heuristic techniques for combinatorial problems (1993), Blackwell Scientific: Blackwell Scientific Oxford · Zbl 0942.90500
[24] Martin, O.; Otto, S. W.; Felten, E. W., Large-step Markov chain for the TSP incorporating local search heuristics, Operations Research Letters, 11, 219-224 (1992) · Zbl 0760.90090
[25] Brucker, P.; Hurink, J.; Werner, F., Improving local search heuristics for some scheduling problems, Discrete Applied Mathematics, 65, 87-107 (1996)
[26] Brucker, P.; Hurink, J.; Werner, F., Improving local search heuristics for some scheduling problems. Part II, Discrete Applied Mathematics, 72, 47-69 (1997) · Zbl 0872.90045
[27] Lourenço, H. R., Job-shop scheduling: computational study of large-step optimization methods, Eur. J. Opl. Res., 83, 347-364 (1995) · Zbl 0904.90089
[28] Adams, J.; Balas, E.; Zawack, D., The shifting bottleneck procedure for job shop scheduling, Management Science, 34, 391-401 (1988) · Zbl 0637.90051
[29] Gupta JND, Lauff V, Werner F. An enumerative algorithm for two-machine flow shop problems with earliness and tardiness penalties. Preprint 33/99, Otto-von-Guericke-Universität, FMA, Magdeburg, 1999.; Gupta JND, Lauff V, Werner F. An enumerative algorithm for two-machine flow shop problems with earliness and tardiness penalties. Preprint 33/99, Otto-von-Guericke-Universität, FMA, Magdeburg, 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. 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.