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].
Titolo: | Scheduling assembly tasks with caterpillar precedence constraints on dedicated machines | |
Autori: | ||
Data di pubblicazione: | 2017 | |
Rivista: | ||
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 [10.1080/00207543.2016.1220686]. | |
Handle: | http://hdl.handle.net/11590/313231 | |
Appare nelle tipologie: | 1.1 Articolo in rivista |