Metaheuristics to solve a tasks scheduling problem in parallel identical machines with unavailability periods

¹ Department of Mathematics, Ferhat Abbas University of Setif 1, Algeria.
rzitou@yahoo.fr
² Department of Mathematics, University of M’sila, Algeria.
Selt.omar@yahoo.fr

Received: 19 February 2014
Accepted: 8 April 2015

Abstract

In this paper, we introduce an approach for scheduling problems of n tasks on m identical parallel machines with unavailability periods. This problem is strongly NP-complete which makes finding an optimal solution looks impossible task. In this frame, we suggest a novel heuristic in which availability periods of each machine are filled with the highest weighted tasks. To improve the performance of this heuristic, we have used, on one hand, different diversification strategies with the aim of exploring unvisited regions of the solution space, and on the other hand, 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 mentioned that tasks movement can be within one machine or between different machines. The performance criterion to optimize in this problem is the weighted sum of the end dates of tasks. Note that all data in this problem are integer and deterministic.