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.
The journal complies the terms and conditions stated in the Creative Common Attribution-Non Commercial Public License 4.0. Authors of the articles are
granted the privileges stated in the public license and the terms and conditions can be accessed via Creative Common License Link.