Skip to main content
Top

Hint

Swipe to navigate through the chapters of this book

2017 | OriginalPaper | Chapter

A New Constructive Heuristic for the No-Wait Flowshop Scheduling Problem

Authors : Lucien Mousin, Marie-Eléonore Kessaci, Clarisse Dhaenens

Published in: Learning and Intelligent Optimization

Publisher: Springer International Publishing

share
SHARE

Abstract

Constructive heuristics have a great interest as they manage to find in a very short time, solutions of relatively good quality. Such solutions may be used as initial solutions for metaheuristics for example. In this work, we propose a new efficient constructive heuristic for the No-Wait Flowshop Scheduling Problem. This proposed heuristic is based on observations on the structure of best solutions of small instances as well as on analyzes of efficient constructive heuristics principles of the literature. Experiments have been conducted and results show the efficiency of the proposed heuristic compared to ones from the literature.
Literature
1.
go back to reference Balas, E., Carrera, M.C.: A dynamic subgradient-based branch-and-bound procedure for set covering. Oper. Res. 44(6), 875–890 (1996) CrossRefMATHMathSciNet Balas, E., Carrera, M.C.: A dynamic subgradient-based branch-and-bound procedure for set covering. Oper. Res. 44(6), 875–890 (1996) CrossRefMATHMathSciNet
2.
go back to reference Bertolissi, E.: Heuristic algorithm for scheduling in the no-wait flow-shop. J. Mater. Process. Technol. 107(1–3), 459–465 (2000) CrossRef Bertolissi, E.: Heuristic algorithm for scheduling in the no-wait flow-shop. J. Mater. Process. Technol. 107(1–3), 459–465 (2000) CrossRef
3.
go back to reference Bianco, L., Dell’Olmo, P., Giordani, S.: Flow shop no-wait scheduling with sequence dependent setup times and release dates. INFOR Inf. Syst. Oper. Res. 37(1), 3–19 (1999) Bianco, L., Dell’Olmo, P., Giordani, S.: Flow shop no-wait scheduling with sequence dependent setup times and release dates. INFOR Inf. Syst. Oper. Res. 37(1), 3–19 (1999)
4.
go back to reference Gilmore, P.C., Gomory, R.E.: Sequencing a one state-variable machine: a solvable case of the traveling salesman problem. Oper. Res. 12(5), 655–679 (1964) CrossRefMATHMathSciNet Gilmore, P.C., Gomory, R.E.: Sequencing a one state-variable machine: a solvable case of the traveling salesman problem. Oper. Res. 12(5), 655–679 (1964) CrossRefMATHMathSciNet
6.
go back to reference Grabowski, J., Pempera, J.: The permutation flow shop problem with blocking. A Tabu Search approach. Omega 35(3), 302–311 (2007) CrossRef Grabowski, J., Pempera, J.: The permutation flow shop problem with blocking. A Tabu Search approach. Omega 35(3), 302–311 (2007) CrossRef
7.
go back to reference Grabowski, J., Wodecki, M.: A very fast Tabu Search algorithm for the permutation flow shop problem with makespan criterion. Comput. Oper. Res. 31(11), 1891–1909 (2004) CrossRefMATHMathSciNet Grabowski, J., Wodecki, M.: A very fast Tabu Search algorithm for the permutation flow shop problem with makespan criterion. Comput. Oper. Res. 31(11), 1891–1909 (2004) CrossRefMATHMathSciNet
8.
go back to reference Kadioglu, S., Malitsky, Y., Sellmann, M.: Non-model-based search guidance for set partitioning problems. In: Hoffmann, J., Selman, B. (eds.) Proceedings of the Twenty-Sixth AAAI Conference on Artificial Intelligence, Toronto, Ontario, Canada, 22–26 July 2012. AAAI Press (2012) Kadioglu, S., Malitsky, Y., Sellmann, M.: Non-model-based search guidance for set partitioning problems. In: Hoffmann, J., Selman, B. (eds.) Proceedings of the Twenty-Sixth AAAI Conference on Artificial Intelligence, Toronto, Ontario, Canada, 22–26 July 2012. AAAI Press (2012)
9.
go back to reference Nagano, M.S., Araújo, D.C.: New heuristics for the no-wait flowshop with sequence-dependent setup times problem. J. Braz. Soc. Mech. Sci. Eng. 36(1), 139–151 (2013) CrossRef Nagano, M.S., Araújo, D.C.: New heuristics for the no-wait flowshop with sequence-dependent setup times problem. J. Braz. Soc. Mech. Sci. Eng. 36(1), 139–151 (2013) CrossRef
10.
go back to reference Nawaz, M., Enscore, E.E., Ham, I.: A heuristic algorithm for the m-machine, n-job flow-shop sequencing problem. Omega 11(1), 91–95 (1983) CrossRef Nawaz, M., Enscore, E.E., Ham, I.: A heuristic algorithm for the m-machine, n-job flow-shop sequencing problem. Omega 11(1), 91–95 (1983) CrossRef
11.
go back to reference Pan, Q.-K., Wang, L., Tasgetiren, M.F., Zhao, B.-H.: A hybrid discrete particle swarm optimization algorithm for the no-wait flow shop scheduling problem with makespan criterion. Int. J. Adv. Manuf. Technol. 38(3–4), 337–347 (2007) Pan, Q.-K., Wang, L., Tasgetiren, M.F., Zhao, B.-H.: A hybrid discrete particle swarm optimization algorithm for the no-wait flow shop scheduling problem with makespan criterion. Int. J. Adv. Manuf. Technol. 38(3–4), 337–347 (2007)
12.
go back to reference Rajendran, C.: A no-wait flowshop scheduling heuristic to minimize makespan. J. Oper. Res. Soc. 45(4), 472–478 (1994) CrossRefMATH Rajendran, C.: A no-wait flowshop scheduling heuristic to minimize makespan. J. Oper. Res. Soc. 45(4), 472–478 (1994) CrossRefMATH
14.
go back to reference Schiavinotto, T., Stützle, T.: A review of metrics on permutations for search landscape analysis. Comput. Oper. Res. 34, 3143–3153 (2007) CrossRefMATH Schiavinotto, T., Stützle, T.: A review of metrics on permutations for search landscape analysis. Comput. Oper. Res. 34, 3143–3153 (2007) CrossRefMATH
15.
go back to reference Taillard, E.: Benchmarks for basic scheduling problems. Eur. J. Oper. Res. 64(2), 278–285 (1993) CrossRefMATH Taillard, E.: Benchmarks for basic scheduling problems. Eur. J. Oper. Res. 64(2), 278–285 (1993) CrossRefMATH
16.
go back to reference Wang, C., Li, X., Wang, Q.: Accelerated tabu search for no-wait flowshop scheduling problem with maximum lateness criterion. Eur. J. Oper. Res. 206(1), 64–72 (2010) CrossRefMATHMathSciNet Wang, C., Li, X., Wang, Q.: Accelerated tabu search for no-wait flowshop scheduling problem with maximum lateness criterion. Eur. J. Oper. Res. 206(1), 64–72 (2010) CrossRefMATHMathSciNet
17.
go back to reference Wismer, D.A.: Solution of the flowshop-scheduling problem with no intermediate queues. Oper. Res. 20(3), 689–697 (1972) CrossRefMATH Wismer, D.A.: Solution of the flowshop-scheduling problem with no intermediate queues. Oper. Res. 20(3), 689–697 (1972) CrossRefMATH
Metadata
Title
A New Constructive Heuristic for the No-Wait Flowshop Scheduling Problem
Authors
Lucien Mousin
Marie-Eléonore Kessaci
Clarisse Dhaenens
Copyright Year
2017
DOI
https://doi.org/10.1007/978-3-319-69404-7_14

Premium Partner