Scheduling tasks on a flexible manufacturing machine to minimize tool change delays

Scheduling tasks on a flexible manufacturing machine to minimize tool change delays

0.00 Avg rating0 Votes
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: ,
Keywords: optimization
Abstract:

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 w, i.e. for precedence relations where each subset of independent tasks has not more than w elements. Since the task precedences width w could be arbitrary, we describe two heuristic algorithms and empirically evaluate their effectiveness in finding schedules with minimum total time required for tool changes.

Reviews

Required fields are marked *. Your email address will not be published.