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.
Nicosia, G., Pacifici, A. (2017). Scheduling assembly tasks with caterpillar precedence constraints on dedicated machines. INTERNATIONAL JOURNAL OF PRODUCTION RESEARCH, 55(6), 1680-1691 [10.1080/00207543.2016.1220686].
Scheduling assembly tasks with caterpillar precedence constraints on dedicated machines
NICOSIA, GAIA;Pacifici, Andrea
2017-01-01
Abstract
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.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.