{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,9]],"date-time":"2025-10-09T20:52:44Z","timestamp":1760043164846,"version":"3.37.3"},"reference-count":49,"publisher":"EDP Sciences","issue":"2","license":[{"start":{"date-parts":[[2019,6,5]],"date-time":"2019-06-05T00:00:00Z","timestamp":1559692800000},"content-version":"vor","delay-in-days":65,"URL":"https:\/\/www.edpsciences.org\/en\/authors\/copyright-and-licensing"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["RAIRO-Oper. Res."],"accepted":{"date-parts":[[2017,10,5]]},"published-print":{"date-parts":[[2019,4]]},"abstract":"<jats:p>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 <jats:italic>worst-case<\/jats:italic> 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 <jats:italic>worst-case<\/jats:italic> performance. While the existing literature only tackles the <jats:italic>worst-case<\/jats:italic> evaluation of the groups of permutable operations, this paper deals with its <jats:italic>best-case<\/jats:italic> 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.<\/jats:p>","DOI":"10.1051\/ro\/2017073","type":"journal-article","created":{"date-parts":[[2017,10,5]],"date-time":"2017-10-05T18:43:21Z","timestamp":1507229001000},"page":"593-608","source":"Crossref","is-referenced-by-count":4,"title":["Evaluation of a new decision-aid parameter for job shop scheduling under uncertainties"],"prefix":"10.1051","volume":"53","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-3222-5186","authenticated-orcid":false,"given":"Zakaria","family":"Yahouni","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Nasser","family":"Mebarki","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Zaki","family":"Sari","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"250","published-online":{"date-parts":[[2019,6,5]]},"reference":[{"key":"R1","doi-asserted-by":"crossref","unstructured":"Alloulou M.A. and Artigues C., Worst-case evaluation of flexible solutions in disjunctive scheduling problems. ICCSA\u201907 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\u20131036.","DOI":"10.1007\/978-3-540-74484-9_89"},{"key":"R2","doi-asserted-by":"crossref","first-page":"314","DOI":"10.1016\/j.ejor.2004.04.004","volume":"165","author":"Artigues","year":"2005","journal-title":"Eur. J. Operat. Res."},{"key":"R3","unstructured":"Artigues Ch., Billaut J.-Ch., Cherif A., Mebarki N., Yahouni Z., Robust machine scheduling based on group of permutable jobs. In: Robustness Analysis in Decision Aiding, Optimization, and Analytics, edited by Doumpos M., Zopounidis C., Grigoroudis E. International Series in Operations Research & Management Science, vol. 241. Springer, Cham (2016)."},{"key":"R4","unstructured":"Baptiste P. and Le Pape C., Edge-finding constraint propagation algorithms for disjunctive and cumulative scheduling. In Proceedings 15th Workshop of the U.K. Planning Special Interest Group (1996)."},{"key":"R5","doi-asserted-by":"crossref","first-page":"470","DOI":"10.1287\/opre.39.3.470","volume":"39","author":"Bean","year":"1991","journal-title":"Option Res."},{"key":"R6","unstructured":"Beasley J., Job shop benchmark instances (2004)."},{"key":"R7","unstructured":"Behnke D. and Geiger M.J., Test instances for the flexible job shop scheduling problem with work centers. Technical report, Universitat Der Bundewehr Hamburg (2012)."},{"key":"R8","doi-asserted-by":"crossref","first-page":"315","DOI":"10.1007\/s10951-008-0080-x","volume":"12","author":"Bidot","year":"2008","journal-title":"J. Scheduling"},{"key":"R9","doi-asserted-by":"crossref","unstructured":"Billaut J.C., Moukrim A. and Sanlaville E., Flexibility and Robustness in Scheduling. Wiley-ISTE (2008).","DOI":"10.1002\/9780470611432"},{"key":"R10","first-page":"1","volume":"17","author":"Birge","year":"1987","journal-title":"Math. Program. Soc."},{"key":"R11","doi-asserted-by":"crossref","first-page":"107","DOI":"10.1016\/0166-218X(94)90204-6","volume":"49","author":"Brucker","year":"1994","journal-title":"Discrete Appl. Math."},{"key":"R12","unstructured":"Brucker P. and Knust S., Complexity results for scheduling, problems (2007)."},{"key":"R13","doi-asserted-by":"crossref","first-page":"199","DOI":"10.1016\/j.ijpe.2013.06.023","volume":"146","author":"Cardin","year":"2013","journal-title":"Inter. J. Production Econ."},{"key":"R14","doi-asserted-by":"crossref","unstructured":"Carlier J., The one machine problem. Eur. J. Oper. Res. 42\u201347 (1982).","DOI":"10.1016\/S0377-2217(82)80007-6"},{"key":"R15","doi-asserted-by":"crossref","first-page":"164","DOI":"10.1287\/mnsc.35.2.164","volume":"35","author":"Carlier","year":"1989","journal-title":"Manag. Sci."},{"key":"R16","doi-asserted-by":"crossref","first-page":"269","DOI":"10.1007\/BF03543071","volume":"26","author":"Carlier","year":"1991","journal-title":"Ann. Oper. Res."},{"key":"R17","doi-asserted-by":"crossref","first-page":"146","DOI":"10.1016\/0377-2217(94)90379-4","volume":"78","author":"Carlier","year":"1994","journal-title":"Eur. J. Oper. Res."},{"key":"R18","doi-asserted-by":"crossref","first-page":"830","DOI":"10.1007\/s001700200095","volume":"19","author":"Chan","year":"2002","journal-title":"Inter. J. Adv. Manuf. Techn."},{"key":"R19","first-page":"231","volume":"10","author":"Da Silva","year":"2014","journal-title":"World J. Model. Simul."},{"key":"R20","unstructured":"Davenport A.J. and Beck J.C., A survey of techniques for scheduling with uncertainty (2000)."},{"key":"R21","doi-asserted-by":"crossref","unstructured":"Erschler  and Roubellat , An approach for real time scheduling for activities with time and resource constraints Advances in project scheduling. Edited by Slowinski R. and Weglarz J.. Elsevier (1989).","DOI":"10.1016\/B978-0-444-87358-3.50015-8"},{"key":"R22","unstructured":"Esswein C., Un apport de flexibilit\u00e9 s\u00e9quentielle pour l\u2019ordonnancement robuste. Ph.D. thesis, Universit\u00e9 Fran\u00e7ois Rabelais Tours, France (2003)."},{"key":"R23","doi-asserted-by":"crossref","first-page":"585","DOI":"10.1007\/s10696-015-9210-x","volume":"27","author":"Fang","year":"2015","journal-title":"Flexible Services and Manufacturing J."},{"key":"R24","unstructured":"Fisher H. and Thomson G.L., Probabilistic learning combinations of local job-shop scheduling rules, Industrial Scheduling (1963) 225\u2013251."},{"key":"R25","unstructured":"Fu N., Varakantham P. and Lau H.Ch., 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\u201316 2010 (2010) 73\u201380."},{"key":"R26","unstructured":"Gallego G., 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)."},{"key":"R27","unstructured":"Gallego G., 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."},{"key":"R28","unstructured":"Goldratt E.M, Critical Chain. North River Press (1997)."},{"key":"R29","doi-asserted-by":"crossref","first-page":"287","DOI":"10.1016\/S0167-5060(08)70356-X","volume":"5","author":"Graham","year":"1979","journal-title":"Ann. Discrete Math."},{"key":"R30","doi-asserted-by":"crossref","first-page":"289","DOI":"10.1016\/j.ejor.2004.04.002","volume":"165","author":"Herroelen","year":"2005","journal-title":"Europ. J. Oper. Res."},{"key":"R31","doi-asserted-by":"crossref","unstructured":"Kouvelis P. and Yu G., Robust Discrete Optimization and Its Applications, Kluwer Academic Publishers (1997).","DOI":"10.1007\/978-1-4757-2620-6"},{"key":"R32","doi-asserted-by":"crossref","first-page":"121","DOI":"10.1007\/s10951-007-0021-0","volume":"11","author":"Lambrechts","year":"2008","journal-title":"J. Scheduling"},{"key":"R33","doi-asserted-by":"crossref","first-page":"544","DOI":"10.1287\/mnsc.19.5.544","volume":"19","author":"Lawler","year":"1973","journal-title":"Manag. Sci."},{"key":"R34","unstructured":"Lawrence S., Resource constrained project scheduling: an experimental investigation of heuristic scheduling techniques (supplement) (1984)."},{"key":"R35","doi-asserted-by":"crossref","first-page":"3688","DOI":"10.1080\/00207543.2012.762131","volume":"51","author":"Mebarki","year":"2013","journal-title":"Inter. J. Produc. Res."},{"key":"R36","first-page":"239","volume":"8","author":"Morikawa","year":"2009","journal-title":"Industrial Eng. Manag. Syst."},{"key":"R37","unstructured":"Muise Ch., Beck J.Ch. and McIlraith Sh.A., Flexible execution of partial order plans with temporal constraints. In Inter. Joint Confer. Artificial Intell. (2013) 2328\u20132335."},{"key":"R38","doi-asserted-by":"crossref","first-page":"271","DOI":"10.1023\/A:1009687210594","volume":"3","author":"Nuijten","year":"1998","journal-title":"J. Heuristics"},{"key":"R39","doi-asserted-by":"crossref","unstructured":"Pinot G. and Mebarki N., Best-case lower bounds in a group sequence for the job shop problem. In 17th IFAC World Congress (2008) 14876\u201314881.","DOI":"10.3182\/20080706-5-KR-1001.02518"},{"key":"R40","doi-asserted-by":"crossref","unstructured":"Policella N., Oddi A., Smith S.F. and Cesta A., Generating Robust Partial Order Schedules. Springer, Berlin Heidelberg, Berlin, Heidelberg (2004) 496\u2013511.","DOI":"10.1007\/978-3-540-30201-8_37"},{"key":"R41","first-page":"683","volume":"8","author":"Roubellat","year":"1995","journal-title":"Revue Automat. Productique Appl."},{"key":"R42","unstructured":"Roy B. and Sussmann B., Les probl\u00e8mes d\u2019ordonnancement avec contraintes disjonctives. Rapport de recherches no 9, SEMA (1964)."},{"key":"R43","doi-asserted-by":"crossref","first-page":"138","DOI":"10.1080\/09511920802209033","volume":"22","author":"Sabuncuoglu","year":"2009","journal-title":"Inter. J. Comput. Integrated Manufacturing"},{"key":"R44","doi-asserted-by":"crossref","first-page":"341","DOI":"10.1287\/ijoc.12.4.341.11881","volume":"12","author":"Sourd","year":"2000","journal-title":"INFORMS J. comput."},{"key":"R45","unstructured":"Swanson K., Bresina J. and Drummond M., Just-in-case scheduling. In AAAI conference, Seattle (1994)."},{"key":"R46","doi-asserted-by":"crossref","unstructured":"Szczesny K. and Knig M., Reactive scheduling based on actual logistics data by applying simulation-based optimization. Visualiz. Eng. 3 (2015).","DOI":"10.1186\/s40327-015-0020-8"},{"key":"R47","doi-asserted-by":"crossref","first-page":"179","DOI":"10.1051\/ro\/1995290201791","volume":"29","author":"Tadei","year":"1995","journal-title":"RAIRO: OR"},{"key":"R48","doi-asserted-by":"crossref","first-page":"195","DOI":"10.1007\/s10951-007-0011-2","volume":"10","author":"Van de vonder","year":"2007","journal-title":"J. Scheduling"},{"key":"R49","first-page":"245","volume":"4","author":"Wojakowski","year":"2014","journal-title":"Res. Logistics Prod."}],"container-title":["RAIRO - Operations Research"],"original-title":[],"link":[{"URL":"https:\/\/www.rairo-ro.org\/10.1051\/ro\/2017073\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,3,20]],"date-time":"2020-03-20T07:57:48Z","timestamp":1584691068000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.rairo-ro.org\/10.1051\/ro\/2017073"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,4]]},"references-count":49,"journal-issue":{"issue":"2"},"alternative-id":["ro160160"],"URL":"https:\/\/doi.org\/10.1051\/ro\/2017073","relation":{},"ISSN":["0399-0559","1290-3868"],"issn-type":[{"type":"print","value":"0399-0559"},{"type":"electronic","value":"1290-3868"}],"subject":[],"published":{"date-parts":[[2019,4]]}}}