Scheduling assembly tasks with caterpillar precedence constraints on dedicated machines. Issue 6 (19th March 2017)

• Record Type: Journal Article
• Authors: Nicosia, Gaia; Pacifici, Andrea
• Is Part Of: International journal of production research. Volume 55:Issue 6(2017)
• Page Start: 1680
• Page End: 1691
• Publication Date: 2017-03-19
• Subjects: assembly systems -- dedicated machines -- heuristics -- mixed integer linear programming -- scheduling; Factory management -- Periodicals; 658.57
• DOI: 10.1080/00207543.2016.1220686
• Languages: English
• ISSNs: 0020-7543

Abstract

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.