This paper deals with the problem of assigning operators to jobs, within a free assignment-changing mode, in a job-shop environment subject to a fixed processing sequence of the jobs. We seek an assignment of operators that minimizes the maximum lateness. Within this model, a job needs an operator during the entire duration of its processing. We show that the problem is -hard when the number of operators is arbitrary and exhibit polynomial time algorithms for the cases involving one and two operators, respectively.
Accepté le :
Première publication :
Publié le :
DOI : 10.1051/ro/2019116
Keywords: Scheduling, job shop, operators, maximum lateness
@article{RO_2020__54_2_555_0,
author = {Benkalai, Im\`ene and Rebaine, Djamal and Baptiste, Pierre},
title = {Scheduling job shop problems with operators with respect to the maximum lateness},
journal = {RAIRO - Operations Research - Recherche Op\'erationnelle},
pages = {555--568},
year = {2020},
publisher = {EDP Sciences},
volume = {54},
number = {2},
doi = {10.1051/ro/2019116},
mrnumber = {4071320},
zbl = {1437.90072},
language = {en},
url = {https://www.numdam.org/articles/10.1051/ro/2019116/}
}
TY - JOUR AU - Benkalai, Imène AU - Rebaine, Djamal AU - Baptiste, Pierre TI - Scheduling job shop problems with operators with respect to the maximum lateness JO - RAIRO - Operations Research - Recherche Opérationnelle PY - 2020 SP - 555 EP - 568 VL - 54 IS - 2 PB - EDP Sciences UR - https://www.numdam.org/articles/10.1051/ro/2019116/ DO - 10.1051/ro/2019116 LA - en ID - RO_2020__54_2_555_0 ER -
%0 Journal Article %A Benkalai, Imène %A Rebaine, Djamal %A Baptiste, Pierre %T Scheduling job shop problems with operators with respect to the maximum lateness %J RAIRO - Operations Research - Recherche Opérationnelle %D 2020 %P 555-568 %V 54 %N 2 %I EDP Sciences %U https://www.numdam.org/articles/10.1051/ro/2019116/ %R 10.1051/ro/2019116 %G en %F RO_2020__54_2_555_0
Benkalai, Imène; Rebaine, Djamal; Baptiste, Pierre. Scheduling job shop problems with operators with respect to the maximum lateness. RAIRO - Operations Research - Recherche Opérationnelle, Tome 54 (2020) no. 2, pp. 555-568. doi: 10.1051/ro/2019116
[1] , , and , A job shop problem with one additional resource type. J. Scheduling 14 (2010) 225–237. | MR | Zbl | DOI
[2] , and , A job shop scheduling problem with human operators in handicraft production. Int. J. Prod. Res. 52 (2014) 3820–3831. | DOI
[3] and , Throughput optimization for the robotic cell problem with controllable processing times. RAIRO: OR 51 (2017) 805–818. | MR | Numdam | Zbl | DOI
[4] and , Scheduling of parts and robot activities in a two machine robotic cell. Comput. Oper. Res. 26 (1999) 297–312. | Zbl | DOI
[5] , , and , Preemptive scheduling of a single machine to minimize maximum cost subject to release dates and precedence constraints. Oper. Res. 31 (1983) 381–386. | DOI
[6] , Some Problems in One-Operator Scheduling. Ph.D. thesis. University of Waterloo (1999).
[7] and , Ordonnancement sur machines parallèles avec partage d’opérateurs. In: 10ème Congrès International de Génie Industriel-CIGI 2013 (2013).
[8] , , and , Gestion de production et ressources humaines. Presses Internationales Polytechnique (2005).
[9] , and , Ordonnancement d’ateliers de type flow shop avec contrainte d’opérateurs. In: 11ème Congrès International de Génie Industriel-CIGI 2015 (2015).
[10] , and , Ordonnancement d’ateliers de type flow shop avec opérateurs en mode d’affectation libre. In: 17 ème conférence ROADEF (2016).
[11] , and , Ordonnancement d’ateliers de type flow shop avec opérateurs en mode d’affectation libre. In: 17ème Conférence ROADEF de la Société Française de Recherche Opérationnelle et Aide à la Décision (2016).
[12] , and , Assigning operators in a flow shop environment. In: Information Systems, Logistics and Supply Chain (2016).
[13] , and , Scheduling flow shops with operators. Int. J. Prod. Res. 57 (2019) 338–356. | DOI
[14] , A generalized permutation approach to jobshop scheduling with genetic algorithms. Oper. Res. Spectr. 17 (1995) 87–92. | Zbl | DOI
[15] , , , and , Handbook on scheduling: From theory to applications. Springer (2007). | Zbl
[16] , and , One-operator-two-machine flowshop scheduling with setup and dismounting times. Comput. Oper. Res. 26 (1999) 715–730. | Zbl | DOI
[17] , Gestion des ressources humaines en production cyclique. Ph.D. thesis. ENSM Saint-Étienne (2005).
[18] , , and , Sequencing and scheduling in robotic cells: Recent developments. J. Scheduling 8 (2005) 387–426. | Zbl | MR | DOI
[19] , and , Robotic cells with parallel machines and multiple dual gripper robots: a comparative overview. IIE Trans. 40 (2008) 1211–1227. | DOI
[20] and , Algorithms for solving production scheduling problems. Oper. Res. 8 (1960) 487–503. | MR | Zbl | DOI
[21] , and , Activities planning and resources assignment on distinct places: a mathematical model. RAIRO: OR 49 (2015) 79–98. | MR | Numdam | Zbl | DOI
[22] , Preemptive scheduling of precedence-constrained jobs on parellel machines. In: Deterministic and Stochastic Scheduling, Proceedings of the NATO Advanced Study and Reasearch Institute on Theoretical Approaches to Scheduling Problems. D. Reidel publishing Co. (1982) 101–123. | Zbl
[23] , , , and , Solving the job shop scheduling problem with operators by depth-first heuristic search enhanced with global pruning rules. Artif. Intell. Commun. 28 (2015) 365–381. | MR | Zbl
[24] , , and , Genetic algorithm for job shop with operatos, edited by , , and . In: Vol. 6687 of New challenges on bioinspired applications. IWINAC. Lecture Notes in Computer Science, Springer, Berlin, Heidelberg (2011). | DOI
[25] , and , An efficient hybrid search algorithm for job shop scheduling with operators. Int. J. Prod. Res. 51 (2013) 5221–5237. | DOI
[26] , , and , A genetic algorithm for job shop scheduling with operators enhanced by weal lamarckian evolution and search space narrowing. Nat. Comput. 13 (2014) 179–192. | MR | DOI
[27] , , and , Memetic algorithms for the job shop scheduling problem with operators. Appl. Soft Comput. 34 (2015) 94–105. | DOI
[28] and , A classification scheme for integrated staff rostering and scheduling problems. RAIRO: OR 49 (2015) 393–412. | MR | Zbl | Numdam | DOI
[29] , Scheduling: Theory, Algorithms and Systems. Prentice Hall (2002). | Zbl
[30] , , , and , Sequencing of parts and robot moves in a robotic cell. Int. J. Flexible Manuf. Syst. 4 (1992) 331–358. | DOI
[31] , , and , Repair shop job scheduling with parallel operators and multiple constraints using simulated annealing. Int. J. Comput. Intell. Syst. 6 (2013) 223–233. | DOI
[32] , and , Optimally scheduling a job shop with operators and total flow time, edited by , and . In: Vol. 7027 of Advances in Artificial intelligence. CAEPIA. Lecture Notes in Computer Science. Springer, Berlin, Heidelberg (2011).
[33] , and , New schedule generation schemes for the job shop problem with operators. J. Intell. Manuf. 26 (2015) 511–525. | DOI
[34] , Complexity of sequencing problems. In: Computer and Job/Shop Scheduling Theory. Wiley & Sons, Inc., New York (1976).
[35] , Choosing the job sequence and processing times to minimize total processing plus flow cost on a single machine. Oper. Res. 28 (1980) 1155–1167. | Zbl | DOI
[36] , Two single machine sequencing problems involving controllable job processing times. AIIE Trans. 12 (1980) 258–262. | MR | DOI
[37] , Ordonnancement de machines parallèles identiques avec des contraintes de ressources humaines. Ph.D. thesis, École Polytechnique Montréal (2009).
Cité par Sources :
