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

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.
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].
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/11590/313231
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 5
  • ???jsp.display-item.citation.isi??? 5
social impact