In this work, we address the problem of scheduling a set of n non-preemptive tasks on m dedicated machines in order to minimise the makespan. For each task deterministic processing times and a specific processing machine are given, moreover a set of precedence constraints among the tasks are known. We present a heuristic and some lower bounds on the minimum makespan for a relevant case in manufacturing applications, namely when the precedence constraints form a caterpillar graph. A caterpillar is a directed tree consisting of a single directed path and leaf nodes each of which is incident to the directed path by exactly one incoming arc. A number of computational experiments are also performed in order to test the performance of the proposed solution algorithm.
|Titolo:||Scheduling assembly tasks with caterpillar precedence constraints on dedicated machines|
|Data di pubblicazione:||2017|
|Citazione:||Nicosia, G., & Pacifici, A. (2017). Scheduling assembly tasks with caterpillar precedence constraints on dedicated machines. INTERNATIONAL JOURNAL OF PRODUCTION RESEARCH, 55(6), 1680-1691.|
|Appare nelle tipologie:||1.1 Articolo in rivista|