Volume 50, Number 1, January-March 2016
|83 - 90
|07 December 2015
Metaheuristics to solve a tasks scheduling problem in parallel identical machines with unavailability periods
Received: 19 February 2014
Accepted: 8 April 2015
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.
Mathematics Subject Classification: 90C27 / 90C59 / 90B35 / 68M20
Key words: Scheduling / parallel identical machines / unavailability periods / metaheuristic / Tabu search
© EDP Sciences, ROADEF, SMAI, 2015
Current usage metrics show cumulative count of Article Views (full-text article views including HTML views, PDF and ePub downloads, according to the available data) and Abstracts Views on Vision4Press platform.
Data correspond to usage on the plateform after 2015. The current usage metrics is available 48-96 hours after online publication and is updated daily on week days.
Initial download of the metrics may take a while.