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 schedule’s 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 same
problem. The computational results show that the proposed tabu search procedure generally outperforms the existing
heuristic for small- and large-sized problems |
