A Tabu Search Approach for the Non-identical Parallel-Machines Scheduling Problem With Sequence-Dependent Setup Times

Full Citation:
Helal, M., Hosni, Y. 2003. A tabu search approach to the non-identical parallel machines scheduling problem with sequence dependent setup times. IERC 03, The IIE Annual Conference, May 18-20, Portland, OR

Abstract:
We present a tabu search-based heuristic algorithm for the solution of the non-identical parallel machines scheduling problem with sequence-dependent setup times. The problem is an NP-hard and finding an optimal solution is unlikely in general. Consequently, heuristic techniques are appropriate for solving it. The criterion of interest in this work is the minimum makespan. The proposed algorithm uses two phases of perturbation in the search of better solutions. One phase (Intra-machine perturbation) optimizes the sequence of jobs on the machines, while the second (inter-machine perturbation) balances the assignment of the jobs to the machine. Structure of the algorithm and the tabu search concepts, are explained and defined. Computational results are reported.
Keywords: Scheduling, Non-identical, Parallel machines, setup times, tabu search