2008-07         2008. 9. 22

Proofs for dominance properties in a two-machine re-entrant flowshop scheduling problem

Seong-Woo Choi1, Yeong-Dae Kim2

1 System LSI Division, Semiconductor Business, Samsung Electronics Company, Yongin-City, Gyeonggi-Do 446-711, KOREA

2 Department of Industrial Engineering, Korea Advanced Institute of Science and Technology, Yusong-gu, Daejon 305-701, KOREA

ABSTRACT: We present proofs for dominance properties that can be used in a branch and bound algorithm for a two-machine re-entrant flowshop scheduling problem with the objective of minimizing total tardiness. In the re-entrant flowshop considered here, all jobs must be processed twice on each machine, that is, each job should be processed on machine 1, machine 2 and then machine 1 and machine 2.

KET WORDS: scheduling; re-entrant flowshop; dominance properties; proofs