In this paper, we introduce an approach for scheduling problems of tasks on 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.
Mots-clés : Scheduling, parallel identical machines, unavailability periods, metaheuristic, Tabu search
@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://www.numdam.org/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://www.numdam.org/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://www.numdam.org/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. http://www.numdam.org/articles/10.1051/ro/2015013/
and , Parallel machine sheduling to maximize the weighted number of just-in-time jobs. J. Appl. Sci. Technol. 15 (2010) 12–34. | DOI
and , Metaheuristics for scheduling on parallel machine to minimize weighted number of early and tardy jobs. Int. J. Phys. Sci. 7 (2012) 1641–1652. | DOI
and , A Comparative study of metaheuristics for identical parallel machines. J. Eng. Technol. Res. 5 (2013) 207–216. | DOI
P. Baptiste, A. Jouglet, CL. Pape and W. Nuijten, A constraint based approach to minimize the weighted number of late jobs on parallel machines. Technical Report 2000/228, UMR, CNRS 6599, Heudiasyc, France (2000).
, and , Scheduling with relates dates on a single machine to minimize total weighted completion time. Discrete Appl. Math. 36 (1992) 213–231. | DOI | Zbl
J. Carlier and P. Chrétienne, Problèmes d’ordonnancement: Modélisation, Complexité, Algorithmes. Masson, France (1988).
, Future paths for integer programming and links to artificial intelligence. Comput. Open Res. 13 (1986) 533–549. | DOI | Zbl
and , Tabu Search and Finite Convergence. Special Issue on “Foundations of heuristics in Combinatorial Optimization”. Discrete Appl. Math. 119 (2002) 3–36. | Zbl
P. Hansen, The Steepest Ascent Mildest Descent Heuristic for Combinatorial Programming. In Proc. of the Congress on Numerical Methods (1986).
and , Branch and bound-based local search method for the flow shop problème. J. Oper. Res. Soc. 54 (2003) 1076–1084. | DOI | Zbl
and , Guidelines for the use metaheuristics in combinatorial optimization. Eur. J. Oper. Res. 151 (2003) 247–52. | DOI | Zbl
and , Minimizing the number of tardy jobs for m parallel machines. Eur. J. Oper. Res. 84 (1995) 334–355. | Zbl
F. Laburthe, Contraintes et algorithmes en optimisation combinatoire. Ph.D. thesis. University Paris VII, France (1988).
, Machine scheduling with an availability constraints. J. Global Optim. 9 (1996) 395–416. | DOI | Zbl
, Minimizing the makespan in two machines flow shop scheduling problem with availability constraints. Oper. Res. Lett. 20 (1997) 129–139. | DOI | Zbl
, Two machines flow shop scheduling problem with availability constraints. Eur. J. Oper. Res. 114 (1999) 420–429. | DOI | Zbl
and , Scheduling jobs and maintenance activities on parallel machines. Naval Res. Logist. 47 (2000) 145–165. | DOI | Zbl
and , Minimizing the weighted number of tardy jobs of parallel processors. Eur. J. Oper. Res. 160 (2005) 471–484. | DOI | Zbl
C. Sadfi, Problèmes d’ordonnancement avec minimisation des encours. Ph.D. thesis. Institut National Polytechnique de Grenoble, France (2002).
M. Sakarovitch, Optimisation combinatoire: Programmation discrète. Hermann, France (1984).
, Scheduling on semi-identical processors. Z. Oper. Res. A28 (1984) 153–162. | Zbl
, Scheduling with limited machine availability. Eur. J. Oper. Res. 121 (2000) 1–15. | DOI | Zbl
, Various optimizes for single-stage production. Naval Res. Logist. 3 (1956) 59–66. | DOI
, and , Metaheuristics for drilling operation scheduling in Taiwan PCB industries. Int. J. Prod. Econ. 141 (2013) 189–198. | DOI
Cité par Sources :
