{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,12]],"date-time":"2025-10-12T03:53:26Z","timestamp":1760241206607,"version":"build-2065373602"},"reference-count":42,"publisher":"MDPI AG","issue":"1","license":[{"start":{"date-parts":[[2019,12,20]],"date-time":"2019-12-20T00:00:00Z","timestamp":1576800000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>We study two-machine shop-scheduling problems provided that lower and upper bounds on durations of n jobs are given before scheduling. An exact value of the job duration remains unknown until completing the job. The objective is to minimize the makespan (schedule length). We address the issue of how to best execute a schedule if the job duration may take any real value from the given segment. Scheduling decisions may consist of two phases: an off-line phase and an on-line phase. Using information on the lower and upper bounds for each job duration available at the off-line phase, a scheduler can determine a minimal dominant set of schedules (DS) based on sufficient conditions for schedule domination. The DS optimally covers all possible realizations (scenarios) of the uncertain job durations in the sense that, for each possible scenario, there exists at least one schedule in the DS which is optimal. The DS enables a scheduler to quickly make an on-line scheduling decision whenever additional information on completing jobs is available. A scheduler can choose a schedule which is optimal for the most possible scenarios. We developed algorithms for testing a set of conditions for a schedule dominance. These algorithms are polynomial in the number of jobs. Their time complexity does not exceed     O (  n 2  )    . Computational experiments have shown the effectiveness of the developed algorithms. If there were no more than 600 jobs, then all 1000 instances in each tested series were solved in one second at most. An instance with 10,000 jobs was solved in 0.4 s on average. The most instances from nine tested classes were optimally solved. If the maximum relative error of the job duration was not greater than     20 %    , then more than     80 %     of the tested instances were optimally solved. If the maximum relative error was equal to     50 %    , then     45 %     of the tested instances from the nine classes were optimally solved.<\/jats:p>","DOI":"10.3390\/a13010004","type":"journal-article","created":{"date-parts":[[2019,12,20]],"date-time":"2019-12-20T09:50:33Z","timestamp":1576835433000},"page":"4","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":9,"title":["Two-Machine Job-Shop Scheduling Problem to Minimize the Makespan with Uncertain Job Durations"],"prefix":"10.3390","volume":"13","author":[{"given":"Yuri N.","family":"Sotskov","sequence":"first","affiliation":[{"name":"United Institute of Informatics Problems, National Academy of Sciences of Belarus, Surganova Street 6, 220012 Minsk, Belarus"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Natalja M.","family":"Matsveichuk","sequence":"additional","affiliation":[{"name":"Department of Automated Production Management Systems, Belarusian State Agrarian Technical University, Nezavisimosti Avenue 99, 220023 Minsk, Belarus"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Vadzim D.","family":"Hatsura","sequence":"additional","affiliation":[{"name":"Department of Electronic Computing Machines, Belarusian State University of Informatics and Radioelectronics, P. Brovki Street 6, 220013 Minsk, Belarus"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2019,12,20]]},"reference":[{"key":"ref_1","unstructured":"Pinedo, M. (2002). Scheduling: Theory, Algorithms, and Systems, Prentice-Hall."},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"467","DOI":"10.1080\/07408179908969849","article-title":"Two-machine flowshop problem with arbitrary processing time distributions","volume":"31","author":"Elmaghraby","year":"2000","journal-title":"IIE Trans."},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"304","DOI":"10.1016\/S0377-2217(97)00424-4","article-title":"Stochastically minimizing the makespan in two-machine flow shops without blocking","volume":"112","author":"Kamburowski","year":"1999","journal-title":"Eur. J. Oper. Res."},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"130","DOI":"10.1287\/opre.34.1.130","article-title":"On Johnson\u2019s two-machine flow-shop with random processing times","volume":"34","author":"Ku","year":"1986","journal-title":"Oper. Res."},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"101","DOI":"10.1016\/S0377-2217(97)00438-4","article-title":"Stochastically minimizing total flowtime in flowshops with no waiting space","volume":"113","author":"Allahverdi","year":"1999","journal-title":"Eur. J. Oper. Res."},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"9","DOI":"10.1016\/0895-7177(94)90202-X","article-title":"Two-machine ordered flowshop scheduling under random breakdowns","volume":"20","author":"Allahverdi","year":"1999","journal-title":"Math. Comput. Model."},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"751","DOI":"10.1016\/j.ejor.2004.09.056","article-title":"Johnson\u2019s problem with stochastic processing times and optimal service level","volume":"169","author":"Portougal","year":"2006","journal-title":"Eur. J. Oper. Res."},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"363","DOI":"10.1287\/mnsc.41.2.363","article-title":"Robust scheduling to hedge against processing time uncertainty in single stage production","volume":"41","author":"Daniels","year":"1995","journal-title":"Manag. Sci."},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"138","DOI":"10.1080\/09511920802209033","article-title":"Hedging production schedules against uncertainty in manufacturing environment with a review of robustness and stability research","volume":"22","author":"Sabuncuoglu","year":"2009","journal-title":"Int. J. Comput. Integr. Manuf."},{"key":"ref_10","unstructured":"Sotskov, Y.N., and Werner, F. (2014). Sequencing and Scheduling with Inaccurate Data, Nova Science Publishers."},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"141","DOI":"10.1016\/j.cor.2015.08.010","article-title":"The robust (minmax regret) single machine scheduling with interval processing times and total weighted completion time objective","volume":"66","author":"Pereira","year":"2016","journal-title":"Comput. Oper. Res."},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"343","DOI":"10.1016\/j.orl.2007.11.004","article-title":"A 2-approximation algorithm for interval data minmax regret sequencing problems with total flow time criterion","volume":"36","author":"Kasperski","year":"2008","journal-title":"Oper. Res. Lett."},{"key":"ref_13","doi-asserted-by":"crossref","unstructured":"Wu, Z., Yu, S., and Li, T. (2019). A meta-model-based multi-objective evolutionary approach to robust job shop scheduling. Mathematics, 7.","DOI":"10.3390\/math7060529"},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"903","DOI":"10.1080\/00207549408956978","article-title":"Dispatching rules in scheduling: A fuzzy approach","volume":"32","author":"Grabot","year":"1994","journal-title":"Int. J. Prod. Res."},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"593","DOI":"10.1016\/S0377-2217(97)00445-1","article-title":"Optimal fuzzy counterparts of scheduling rules","volume":"113","author":"Duckstein","year":"1999","journal-title":"Eur. J. Oper. Res."},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"1072","DOI":"10.1109\/TFUZZ.2011.2159982","article-title":"Possibilistic minmax regret sequencing problems with fuzzy parameteres","volume":"19","author":"Kasperski","year":"2011","journal-title":"IEEE Trans. Fuzzy Syst."},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"67","DOI":"10.1016\/S0895-7177(97)00132-5","article-title":"Optimal makespan scheduling with given bounds of processing times","volume":"26","author":"Lai","year":"1997","journal-title":"Math. Comput. Model."},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"230","DOI":"10.1057\/palgrave.jors.2600690","article-title":"Sequencing with uncertain numerical data for makespan minimization","volume":"50","author":"Lai","year":"1999","journal-title":"J. Oper. Res. Soc."},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"558","DOI":"10.1016\/S0377-2217(03)00424-7","article-title":"Mean flow time minimization with given bounds of processing times","volume":"159","author":"Lai","year":"2004","journal-title":"Eur. J. Oper. Res."},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"556","DOI":"10.1016\/j.mcm.2009.03.006","article-title":"Minimizing total weighted flow time of a set of jobs with interval processing times","volume":"50","author":"Sotskov","year":"2009","journal-title":"Math. Comput. Model."},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"253","DOI":"10.1002\/(SICI)1099-1425(199911\/12)2:6<253::AID-JOS30>3.0.CO;2-R","article-title":"Proportionate flow shop with controllable processing times","volume":"27","author":"Cheng","year":"1999","journal-title":"J. Sched."},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"751","DOI":"10.1016\/j.ejor.2005.06.021","article-title":"Scheduling with controllable release dates and processing times: Makespan minimization","volume":"175","author":"Cheng","year":"2006","journal-title":"Eur. J. Oper. Res."},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"297","DOI":"10.1016\/j.ejor.2004.03.025","article-title":"Approximation schemes for job shop scheduling problems with controllable processing times","volume":"167","author":"Jansen","year":"2005","journal-title":"Eur. J. Oper. Res."},{"key":"ref_24","first-page":"287","article-title":"Optimization and approximation in deterministic sequencing and scheduling","volume":"5","author":"Graham","year":"1979","journal-title":"Ann. Discret. Appl. Math."},{"key":"ref_25","doi-asserted-by":"crossref","unstructured":"Brucker, P. (1995). Scheduling Algorithms, Springer.","DOI":"10.1007\/978-3-662-03088-2"},{"key":"ref_26","doi-asserted-by":"crossref","unstructured":"Tanaev, V.S., Sotskov, Y.N., and Strusevich, V.A. (1994). Scheduling Theory: Multi-Stage Systems, Kluwer Academic Publishers.","DOI":"10.1007\/978-94-011-1192-8"},{"key":"ref_27","doi-asserted-by":"crossref","first-page":"201","DOI":"10.1002\/nav.3800030307","article-title":"An extension of Johnson\u2019s results on job lot scheduling","volume":"3","author":"Jackson","year":"1956","journal-title":"Nav. Res. Logist. Q."},{"key":"ref_28","doi-asserted-by":"crossref","first-page":"61","DOI":"10.1002\/nav.3800010110","article-title":"Optimal two and three stage production schedules with set up times included","volume":"1","author":"Johnson","year":"1954","journal-title":"Nav. Res. Logist. Q."},{"key":"ref_29","doi-asserted-by":"crossref","first-page":"65","DOI":"10.1111\/1475-3995.00393","article-title":"Two-machine flowshop minimum-lenght scheduling problem with random and bounded processing times","volume":"10","author":"Allahverdi","year":"2003","journal-title":"Int. Trans. Oper. Res."},{"key":"ref_30","unstructured":"Sotskov, Y.N., and Werner, F. (2014). A stability approach to two-stage scheduling problems with uncertain processing times In Sequencing and Scheduling with Inaccurate Data, Nova Science Publishers."},{"key":"ref_31","first-page":"100","article-title":"On the existence of globally optimal schedules for the Bellman-Johnson problem for two machines under uncertainty","volume":"3","author":"Shafranski","year":"2009","journal-title":"Informatika"},{"key":"ref_32","doi-asserted-by":"crossref","first-page":"6336","DOI":"10.1080\/00207543.2017.1398426","article-title":"The optimality box in uncertain data for minimising the sum of the weighted job completion times","volume":"56","author":"Lai","year":"2018","journal-title":"Int. J. Prod. Res."},{"key":"ref_33","doi-asserted-by":"crossref","unstructured":"Sotskov, Y.N., and Egorova, N.G. (2018). Single machine scheduling problem with interval processing times and total completion time objective. Algorithms, 11.","DOI":"10.3390\/a11050066"},{"key":"ref_34","doi-asserted-by":"crossref","first-page":"1271","DOI":"10.1016\/j.cor.2011.02.001","article-title":"Minimizing total weighted flow time under uncertainty using dominance and a stability box","volume":"39","author":"Sotskov","year":"2012","journal-title":"Comput. Oper. Res."},{"key":"ref_35","unstructured":"Sotskov, Y.N., and Werner, F. (2014). Minimizing total flow time under uncertainty using optimality and stability boxes. Sequencing and Scheduling with Inaccurate Data, Nova Science Publishers."},{"key":"ref_36","doi-asserted-by":"crossref","first-page":"991","DOI":"10.1016\/j.mcm.2008.02.004","article-title":"Schedule execution for two-machine flow-shop with interval processing times","volume":"49","author":"Matsveichuk","year":"2009","journal-title":"Math. Comput. Model."},{"key":"ref_37","doi-asserted-by":"crossref","first-page":"277","DOI":"10.1057\/palgrave.jors.2601682","article-title":"Flowshop scheduling problem to minimize total completion time with random and bounded processing times","volume":"55","author":"Sotskov","year":"2004","journal-title":"J. Oper. Res. Soc."},{"key":"ref_38","doi-asserted-by":"crossref","first-page":"2475","DOI":"10.1155\/S016117120321019X","article-title":"Two-machine flowshop scheduling problem to minimize makespan or total completion time with random and bounded setup times","volume":"39","author":"Allahverdi","year":"2003","journal-title":"Int. J. Math. Math. Sci."},{"key":"ref_39","doi-asserted-by":"crossref","unstructured":"Kouvelis, P., and Yu, G. (1997). Robust Discrete Optimization and Its Application, Kluwer Academic Publishers.","DOI":"10.1007\/978-1-4757-2620-6"},{"key":"ref_40","doi-asserted-by":"crossref","first-page":"421","DOI":"10.1080\/07408170008963918","article-title":"Robust scheduling of a two-machine flow shop with uncertain processing times","volume":"32","author":"Kouvelis","year":"2011","journal-title":"IEEE Trans."},{"key":"ref_41","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1142\/S0217595909002432","article-title":"Two-machine flow-shop minimum-length scheduling with interval processing times","volume":"26","author":"Ng","year":"2009","journal-title":"Asia-Pac. J. Oper. Res."},{"key":"ref_42","doi-asserted-by":"crossref","first-page":"1493","DOI":"10.1080\/02331931003657691","article-title":"The dominance digraph as a solution to the two-machine flow-shop problem with interval processing times","volume":"60","author":"Matsveichuk","year":"2011","journal-title":"Optimization"}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/13\/1\/4\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T13:44:07Z","timestamp":1760190247000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/13\/1\/4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,12,20]]},"references-count":42,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2020,1]]}},"alternative-id":["a13010004"],"URL":"https:\/\/doi.org\/10.3390\/a13010004","relation":{},"ISSN":["1999-4893"],"issn-type":[{"type":"electronic","value":"1999-4893"}],"subject":[],"published":{"date-parts":[[2019,12,20]]}}}