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