Omar Selt and Rachid Zitouni
Keywords: Scheduling, parallel identical machines, unavailability periods, metaheuristic, tabu search
Abstract: In this paper, we propose a comparative study between metaheuristic and a new heuristic for solving scheduling problems of n tasks on m identical parallel machines with unavailability periods. This problem is NP-complete in the strong sense of the expression and finding an optimal solution appears unlikely. In this frame, we suggested a new heuristic in which availability periods of each machine are filled with the highest weighted tasks. To improve the performance of this heuristic, we used three diversification strategies (T1, T2 and T3) with the aim of exploring unvisited regions of the solution space and two well-known neighborhoods (neighborhood by swapping and neighborhood by insertion). The computational experiment was carried out on three identical parallel machines with different availability periods. It must be noted that tasks movement can be within one machine or between different machines. Note that all data in this problem are integer and deterministic. The weighted sum of the end dates of tasks constitutes the optimization performance criterion in the problem treated in this paper.
[View Complete Article]