Geodesic
Metaheuristics to solve a tasks scheduling problem in parallel identical machines with unavailability periods
zitouni, Rachid1 ; selt, Omar2
1 Department of Mathematics, Ferhat Abbas University of Setif 1, Algeria.
2 Department of Mathematics, University of M’sila, Algeria.
RAIRO - Operations Research - Recherche Opérationnelle, Tome 50 (2016) no. 1, pp. 83-90

Voir la notice de l'article provenant de la source Numdam

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.

DOI : 10.1051/ro/2015013
Classification : 90C27, 90C59, 90B35, 68M20
Keywords: Scheduling, parallel identical machines, unavailability periods, metaheuristic, Tabu search

zitouni, Rachid 1 ; selt, Omar 2

1 Department of Mathematics, Ferhat Abbas University of Setif 1, Algeria.
2 Department of Mathematics, University of M’sila, Algeria. 
@article{RO_2016__50_1_83_0,
     author = {zitouni, Rachid and selt, Omar},
     title = {Metaheuristics to solve a tasks scheduling problem in parallel identical machines with unavailability periods},
     journal = {RAIRO - Operations Research - Recherche Op\'erationnelle},
     pages = {83--90},
     publisher = {EDP-Sciences},
     volume = {50},
     number = {1},
     year = {2016},
     doi = {10.1051/ro/2015013},
     zbl = {1333.90114},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.1051/ro/2015013/}
}
TY  - JOUR
AU  - zitouni, Rachid
AU  - selt, Omar
TI  - Metaheuristics to solve a tasks scheduling problem in parallel identical machines with unavailability periods
JO  - RAIRO - Operations Research - Recherche Opérationnelle
PY  - 2016
SP  - 83
EP  - 90
VL  - 50
IS  - 1
PB  - EDP-Sciences
UR  - http://geodesic.mathdoc.fr/articles/10.1051/ro/2015013/
DO  - 10.1051/ro/2015013
LA  - en
ID  - RO_2016__50_1_83_0
ER  - 
%0 Journal Article
%A zitouni, Rachid
%A selt, Omar
%T Metaheuristics to solve a tasks scheduling problem in parallel identical machines with unavailability periods
%J RAIRO - Operations Research - Recherche Opérationnelle
%D 2016
%P 83-90
%V 50
%N 1
%I EDP-Sciences
%U http://geodesic.mathdoc.fr/articles/10.1051/ro/2015013/
%R 10.1051/ro/2015013
%G en
%F RO_2016__50_1_83_0
zitouni, Rachid; selt, Omar. Metaheuristics to solve a tasks scheduling problem in parallel identical machines with unavailability periods. RAIRO - Operations Research - Recherche Opérationnelle, Tome 50 (2016) no. 1, pp. 83-90. doi: 10.1051/ro/2015013

Cité par Sources :