Look-Ahead Constructive Heuristic for the Unrelated ParallelMachine Problem with Sequence Dependent Setup Times

摘要

This paper presents a look-ahead constructive heuristic for solving the unrelated parallel machine problem withrnsequence dependent setup times, where the objective is to minimize the completion time of the last job, or makespanrn(Cmax). This is an NP-hard problem. Although a variety of practical situations can be modeled using this problem,rnstill a modest number of articles devoted to it can be found in literature. The constructive heuristic proposed in thisrnpaper has a look-ahead mechanism based on a saving criterion, which permits to improve the quality of solutionsrnagainst another constructive heuristic rule already reported in literature.