Article ID: | iaor19981665 |
Country: | Netherlands |
Volume: | 85 |
Issue: | 3 |
Start Page Number: | 541 |
End Page Number: | 555 |
Publication Date: | Sep 1995 |
Journal: | European Journal of Operational Research |
Authors: | Kim Yeong-Dae |
Keywords: | programming: branch and bound |
We consider the permutation flowshop scheduling problem with the objective of minimizing total tardiness. Presented are several properties that are used to calculate lower bounds on total tardiness of jobs for a given partial sequence and to identify sequences dominated by others. We develop a branch and bound algorithm using these bounds and a dominance rule. Results of computational experiments on randomly generated problems are reported.