¹Korea Advanced Institute of Science and Technology, Yuseong-gu, Daejeon, Korea

Correspondence: Y-D Kim, Department of Industrial Engineering, Korea Advanced Institute of Science and Technology, Yuseong-gu, Daejeon 305-701, Korea. E-mail: ydkim@kaist.ac.kr

Received April 2006; Accepted January 2008; Published online 23 April 2008.

Abstract

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.