Economics at your fingertips  

Scheduling assembly tasks with caterpillar precedence constraints on dedicated machines

Gaia Nicosia and Andrea Pacifici

International Journal of Production Research, 2017, vol. 55, issue 6, 1680-1691

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.

Date: 2017
References: View references in EconPapers View complete reference list from CitEc
Citations Track citations by RSS feed

Downloads: (external link) (text/html)
Access to full text is restricted to subscribers.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link:

Ordering information: This journal article can be ordered from

Access Statistics for this article

International Journal of Production Research is currently edited by Professor A. Dolgui

More articles in International Journal of Production Research from Taylor & Francis Journals
Bibliographic data for series maintained by Chris Longhurst ().

Page updated 2018-10-20
Handle: RePEc:taf:tprsxx:v:55:y:2017:i:6:p:1680-1691