A branch-and-bound algorithm for permutation flow shops with sequence-dependent setup times
- 1 August 1999
- journal article
- research article
- Published by Taylor & Francis in IIE Transactions
- Vol. 31 (8) , 721-731
- https://doi.org/10.1080/07408179908969871
Abstract
This paper presents a branch-and-bound enumeration scheme for the makespan minimization of the permutation flow shop scheduling problem with sequence-dependent setup times. The algorithm includes the implementation of both lower and upper bounding procedures, a dominance elimination criterion, and special features such as a partial enumeration strategy. A computational evaluation of the overall scheme demonstrates the effectiveness of each component. Test results are provided for a wide range of problem instances.Keywords
This publication has 18 references indexed in Scilit:
- A review of scheduling research involving setup considerationsOmega, 1999
- Heuristics for the flow line problem with setup costsEuropean Journal of Operational Research, 1998
- A fast tabu search algorithm for the permutation flow-shop problemEuropean Journal of Operational Research, 1996
- The two-machine total completion time flow shop problemEuropean Journal of Operational Research, 1996
- Two branch and bound algorithms for the permutation flow shop problemEuropean Journal of Operational Research, 1996
- Heuristics in flow shop scheduling with sequence dependent setup timesOmega, 1992
- On the Srikar-Ghosh MILP model for the iVx M SDST flowshop problemInternational Journal of Production Research, 1990
- A MILP model for then-job,M-stage flowshop with sequence dependent set-up timesInternational Journal of Production Research, 1986
- A “Branch-and-Bound” Algorithm for the Exact Solution of the Three-Machine Scheduling ProblemJournal of the Operational Research Society, 1965
- Optimal two‐ and three‐stage production schedules with setup times includedNaval Research Logistics Quarterly, 1954