Minimizing total tardiness in a two-machine re-entrant flowshop with sequence-dependent setup times |
| |
Affiliation: | 1. Department of Pathology, Tohoku University Graduate School of Medicine, Sendai 980-8575, Japan;2. Department of Pathology, Tohoku University Hospital, Sendai 980-8575, Japan;3. Department of Surgery, Tohoku University Hospital, Sendai 980-8575, Japan;4. Department of Vascular Biology, Institute of Development, Aging and Cancer, Tohoku University, Sendai 980-8575, Japan |
| |
Abstract: | We consider a two-machine re-entrant flowshop scheduling problem in which all jobs must be processed twice on each machine and there are sequence-dependent setup times on the second machine. For the problem with the objective of minimizing total tardiness, we develop dominance properties and a lower bound by extending those for a two-machine re-entrant flowshop problem (without sequence-dependent setup times) as well as heuristic algorithms, and present a branch and bound algorithm in which these dominance properties, lower bound, and heuristics are used. For evaluation of the performance of the branch and bound algorithm and heuristics, computational experiments are performed on randomly generated instances, and results are reported. |
| |
Keywords: | Scheduling Re-entrant flowshop Sequence-dependent setup times Branch and bound Heuristics |
本文献已被 ScienceDirect 等数据库收录! |
|