Article ID: | iaor19951338 |
Country: | United Kingdom |
Volume: | 22 |
Issue: | 3 |
Start Page Number: | 307 |
End Page Number: | 319 |
Publication Date: | Mar 1995 |
Journal: | Computers and Operations Research |
Authors: | Kim Yeong-Dae |
Keywords: | heuristics |
List scheduling algorithms are commonly used for multi-machine scheduling problems, especially for those with precedence relationships among operations. In most list scheduling algorithms, operations are scheduled forward. This paper suggests a backward approach in which the operations are scheduled backward. It discusses some details that must be considered when applying the backward approach to problems with due dates and suggests several methods of defining parameters needed in the backward approach. Performance of this approach is tested on job shop problems and identical machine problems with several types of precedence constraints.