Unrelated Parallel Machine Scheduling Problem with Sequence Dependent Setup Times

GOAL group has developed several algorithms and works to deal with parallel machine scheduling problems. One of these works addresses the Unrelated Parallel Machine Scheduling Problem with Sequence Dependent Setup Times. In this problem there is a set of jobs and machines, and for each job there is a processing time associated, which is different for each machine. Given two jobs, there is also a setup time that depends on their sequence and on the machine used. The objective considered in this problem is minimizing the makespan. This NP-Hard problem was tackled in this work by local search meta- heuristics, such as Simulated Annealing, Iterated Local Search and Late Acceptance Hill Climbing, using several neighborhood structures. These structures are dynamically selected according to their effectiveness in runtime. The parameters of the algorithms were set using the irace package. Computational experiments show that the proposed methods outperform many results found in the literature, improving the best known solutions for several instances.

Downloading the files

The instances can also be download from:

http://soa.iti.es/problem-instances