Article ID: | iaor20061659 |
Country: | Netherlands |
Volume: | 164 |
Issue: | 3 |
Start Page Number: | 627 |
End Page Number: | 638 |
Publication Date: | Aug 2005 |
Journal: | European Journal of Operational Research |
Authors: | Gupta J.N.D., Ecker K.H. |
Keywords: | optimization |
This paper considers the problem of scheduling a given set of precedence constraint tasks on a flexible machine equipped with a tool magazine where each task requires exactly one of the tools during its execution. Changing from one tool to another requires a certain amount of time that depends on the pair of tools being exchanged. We present a new algorithmic approach for general task precedence relations when it is desired to sequence the tasks in such a way that the total time required for tool changes is minimized. The proposed algorithm is of polynomial time complexity in case of task precedences of limited width