This paper addresses the groups of permutable operations method. This method is a flexible scheduling approach to hedge against uncertainties and is composed of a proactive/reactive phase. The proactive phase consists of computing a set of solutions (schedule) to a scheduling problem, leaving the choice of executing one of these solutions during the reactive phase according to the current state of the shop floor. During the reactive phase, the remaining decisions have to be made in real-time. The worst-case evaluation of the remaining solutions is a decision-aid parameter used during the reactive phase in order to control the final schedule from exceeding a worst-case performance. While the existing literature only tackles the worst-case evaluation of the groups of permutable operations, this paper deals with its best-case evaluation. For solving this problem, a new lower bound calculating this parameter in polynomial time is proposed. The computational efficiency of this parameter in a reactive algorithm exhibits very good performance. Moreover, the experiments show the robustness of this evaluation allowing this parameter to be used in an unstable job shop environment.
Accepté le :
DOI : 10.1051/ro/2017073
Mots-clés : Scheduling, decision-aid system, lower bounds, Job shop, makespan
@article{RO_2019__53_2_593_0,
author = {Yahouni, Zakaria and Mebarki, Nasser and Sari, Zaki},
title = {Evaluation of a new decision-aid parameter for job shop scheduling under uncertainties},
journal = {RAIRO - Operations Research - Recherche Op\'erationnelle},
pages = {593--608},
publisher = {EDP-Sciences},
volume = {53},
number = {2},
year = {2019},
doi = {10.1051/ro/2017073},
zbl = {1423.90102},
language = {en},
url = {http://www.numdam.org/articles/10.1051/ro/2017073/}
}
TY - JOUR AU - Yahouni, Zakaria AU - Mebarki, Nasser AU - Sari, Zaki TI - Evaluation of a new decision-aid parameter for job shop scheduling under uncertainties JO - RAIRO - Operations Research - Recherche Opérationnelle PY - 2019 SP - 593 EP - 608 VL - 53 IS - 2 PB - EDP-Sciences UR - http://www.numdam.org/articles/10.1051/ro/2017073/ DO - 10.1051/ro/2017073 LA - en ID - RO_2019__53_2_593_0 ER -
%0 Journal Article %A Yahouni, Zakaria %A Mebarki, Nasser %A Sari, Zaki %T Evaluation of a new decision-aid parameter for job shop scheduling under uncertainties %J RAIRO - Operations Research - Recherche Opérationnelle %D 2019 %P 593-608 %V 53 %N 2 %I EDP-Sciences %U http://www.numdam.org/articles/10.1051/ro/2017073/ %R 10.1051/ro/2017073 %G en %F RO_2019__53_2_593_0
Yahouni, Zakaria; Mebarki, Nasser; Sari, Zaki. Evaluation of a new decision-aid parameter for job shop scheduling under uncertainties. RAIRO - Operations Research - Recherche Opérationnelle, Tome 53 (2019) no. 2, pp. 593-608. doi : 10.1051/ro/2017073. http://www.numdam.org/articles/10.1051/ro/2017073/
[1] and , Worst-case evaluation of flexible solutions in disjunctive scheduling problems. ICCSA’07 Proceedings of the 2007 international conference on Computational science and its applications - Volume Part III. In Vol. 1205 of Lecture Notes in Computer Science (2007) 1027–1036.
[2] , and , Maximization of solution flexibility for robust shop scheduling. Eur. J. Operat. Res. 165 (2005) 314–328. | Zbl
[3] , , , , , Robust machine scheduling based on group of permutable jobs. In: Robustness Analysis in Decision Aiding, Optimization, and Analytics, edited by , , International Series in Operations Research & Management Science, vol. 241. Springer, Cham (2016).
[4] and , Edge-finding constraint propagation algorithms for disjunctive and cumulative scheduling. In Proceedings 15th Workshop of the U.K. Planning Special Interest Group (1996).
[5] , , and , Match-up scheduling with multiple resources, release dates and disruptions. Option Res. 39 (1991) 470–483. | Zbl
[6] , Job shop benchmark instances (2004).
[7] and , Test instances for the flexible job shop scheduling problem with work centers. Technical report, Universitat Der Bundewehr Hamburg (2012).
[8] , , and , A theoretic and practical framework for scheduling in a stochastic environment. J. Scheduling 12 (2008) 315–344. | Zbl
[9] , and , Flexibility and Robustness in Scheduling. Wiley-ISTE (2008).
[10] , , , , and , A standard input format for multi-period stochastic linear programs. Math. Program. Soc. 17 (1987) 1–21.
[11] , and , A branch and bound algorithm for the job-shop scheduling problem. Discrete Appl. Math. 49 (1994) 107–127. | Zbl
[12] and , Complexity results for scheduling, problems (2007).
[13] , and , A study of the robustness of the group scheduling method using an emulation of a complex fms. Inter. J. Production Econ. 146 (2013) 199–207.
[14] , The one machine problem. Eur. J. Oper. Res. 42–47 (1982). | Zbl
[15] and , An algorithm for solving the job-shop problem. Manag. Sci. 35 (1989) 164–176. | Zbl
[16] and , A practical use of jackson’s preemptive schedule for solving the job shop problem. Ann. Oper. Res. 26 (1991) 269–287. | Zbl
[17] and , Adjustment of heads and tails for the job-shop problem. Eur. J. Oper. Res. 78 (1994) 146–161. | Zbl
[18] , and , The state of the art in simulation study on fms scheduling: a comprehensive survey. Inter. J. Adv. Manuf. Techn. 19 (2002) 830–849.
[19] , , and , Simulation study of dispatching rules in stochastic job shop dynamic scheduling. World J. Model. Simul. 10 (2014) 231–240.
[20] and , A survey of techniques for scheduling with uncertainty (2000).
[21] and , An approach for real time scheduling for activities with time and resource constraints Advances in project scheduling. Edited by and . Elsevier (1989).
[22] , Un apport de flexibilité séquentielle pour l’ordonnancement robuste. Ph.D. thesis, Université François Rabelais Tours, France (2003).
[23] , , and , An estimation of distribution algorithm and new computational results for the stochastic resource-constrained project scheduling problem. Flexible Services and Manufacturing J. 27 (2015) 585–605.
[24] and , Probabilistic learning combinations of local job-shop scheduling rules, Industrial Scheduling (1963) 225–251.
[25] , and , Towards finding robust execution strategies for rcpsp/max with durational uncertainty. In Proc. 20th Inter. Confer. Automated Planning and Scheduling, ICAPS 2010, Toronto, Ontario, Canada. 12–16 2010 (2010) 73–80.
[26] , Linear control policies for scheduling a single facility after an initial disruption. Technical report, School of operations research and industrial engineering, College of Engineering, Cornell univeresity, ITHACA, New york 14853 (1988).
[27] , Produce-up-to policies for scheduling a single facility after an initial disruption. Technical report. School of operations research and industrial engineering, College of Engineering, Cornell univeresity, ITHACA, New york 14853, 1988.
[28] , Critical Chain. North River Press (1997).
[29] , , and , Optimization and approximation in deterministic sequencing and scheduling: a survey. Ann. Discrete Math. 5 (1979) 287–326. | Zbl
[30] and , Project scheduling under uncertainty: Survey and research potentials. Europ. J. Oper. Res. 165 (2005) 289–306. | Zbl
[31] and , Robust Discrete Optimization and Its Applications, Kluwer Academic Publishers (1997). | Zbl
[32] , and , Proactive and reactive strategies for resource-constrained project scheduling with uncertain resource availabilities. J. Scheduling 11 (2008) 121–136. | Zbl
[33] , Optimal sequencing of a single machine subject to precedence constraints. Manag. Sci. 19 (1973) 544–546. | Zbl
[34] , Resource constrained project scheduling: an experimental investigation of heuristic scheduling techniques (supplement) (1984).
[35] and , Correlation among tardiness-based measures for scheduling using priority dispatching rules. Inter. J. Produc. Res. 51 (2013) 3688–3697.
[36] and , A flexible branch and bound method for the job shop scheduling problem. Industrial Eng. Manag. Syst. 8 (2009) 239–246.
[37] , and , Flexible execution of partial order plans with temporal constraints. In Inter. Joint Confer. Artificial Intell. (2013) 2328–2335.
[38] and , Constraint-based job shop scheduling with ilog sheduler. J. Heuristics 3 (1998) 271–286. | Zbl
[39] and , Best-case lower bounds in a group sequence for the job shop problem. In 17th IFAC World Congress (2008) 14876–14881.
[40] , , and , Generating Robust Partial Order Schedules. Springer, Berlin Heidelberg, Berlin, Heidelberg (2004) 496–511. | Zbl
[41] , and , Ordonnancement d’atelier en temps réel: d’orabaid à ordo. Revue Automat. Productique Appl. 8 (1995) 683–713.
[42] and , Les problèmes d’ordonnancement avec contraintes disjonctives. Rapport de recherches no 9, SEMA (1964).
[43] and , Hedging production schedules against uncertainty in manufacturing environment with a review of robustness and stability research. Inter. J. Comput. Integrated Manufacturing 22 (2009) 138–157.
[44] and , Multiple-machine lower bounds for shop-scheduling problems. INFORMS J. comput. 12 (2000) 341–352. | Zbl
[45] , and , Just-in-case scheduling. In AAAI conference, Seattle (1994).
[46] and , Reactive scheduling based on actual logistics data by applying simulation-based optimization. Visualiz. Eng. 3 (2015).
[47] , and , Advanced search techniques for the job shop problem: a comparison. RAIRO: OR 29 (1995) 179–194. | Zbl
[48] , and , A classication of predictive-reactive project scheduling procedures. J. Scheduling 10 (2007) 195–207. | Zbl
[49] and , The classification of scheduling problems under production uncertainty. Res. Logistics Prod. 4 (2014) 245–255.
Cité par Sources :
