A branch-and-bound algorithm for a two-machine flowshop scheduling problem with limited waiting time constraints

作者：Joo B J; Kim Y D^*

来源：Journal of the Operational Research Society, 2009, 60(4): 572-582.

DOI：10.1057/palgrave.jors.2602598

• scheduling
• two-machine flowshop
• limited waiting time
• makespan

In this paper, we consider a two-machine flowshop scheduling problem in which the waiting time of each job between the two machines cannot be greater than a certain time period. For the problem with the objective of minimizing makespan, we identify several dominance properties of the problem and develop a branch-and-bound (B&B) algorithm using the dominance properties. Computational tests are performed on randomly generated test problems for evaluation of performance of the B&B algorithm, and results show that the algorithm can solve problems with up to 150 jobs in a reasonable amount of CPU time.

• 出版日期2009-4