Computer Engineering Commons^™

A Tabu Search Algorithm To Minimize The Makespan For The Unrelated Parallel Machines Scheduling Problem With Setup Times, Magdy Helal, Ghaith Rabadi, Ameer Al-Salem

Engineering Management & Systems Engineering Faculty Publications

In this paper we propose a tabu search implementation to solve the unrelated parallel machines scheduling problem with sequence- and machine- dependent setup times to minimize the schedules makespan. The problem is NP-hard and finding an optimal solution efficiently is unlikely. Therefore, heuristic techniques are more appropriate to find near-optimal solutions. The proposed tabu search algorithm uses two phases of perturbation schemes: the intra-machine perturbation, which optimizes the sequence of jobs on the machines, and the inter-machine perturbation, which balances the assignment of the jobs to the machines. We compare the proposed algorithm to an existing one that addressed the …