{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,18]],"date-time":"2026-08-18T04:29:52Z","timestamp":1787027392446,"version":"build-2736575974"},"reference-count":37,"publisher":"MDPI AG","issue":"3","license":[{"start":{"date-parts":[[2020,3,24]],"date-time":"2020-03-24T00:00:00Z","timestamp":1585008000000},"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>An important element in the integration of the fourth industrial revolution is the development of efficient algorithms to deal with dynamic scheduling problems. In dynamic scheduling, jobs can be admitted during the execution of a given schedule, which necessitates appropriately planned rescheduling decisions for maintaining a high level of performance. In this paper, a dynamic case of the multiprocessor open shop scheduling problem is addressed. This problem appears in different contexts, particularly those involving diagnostic operations in maintenance and health care industries. Two objectives are considered simultaneously\u2014the minimization of the makespan and the minimization of the mean weighted flow time. The former objective aims to sustain efficient utilization of the available resources, while the latter objective helps in maintaining a high customer satisfaction level. An exact algorithm is presented for generating optimal Pareto front solutions. Despite the fact that the studied problem is NP-hard for both objectives, the presented algorithm can be used to solve small instances. This is demonstrated through computational experiments on a testbed of 30 randomly generated instances. The presented algorithm can also be used to generate approximate Pareto front solutions in case computational time needed to find proven optimal solutions for generated sub-problems is found to be excessive. Furthermore, computational results are used to investigate the characteristics of the optimal Pareto front of the studied problem. Accordingly, some insights for future metaheuristic developments are drawn.<\/jats:p>","DOI":"10.3390\/a13030074","type":"journal-article","created":{"date-parts":[[2020,3,24]],"date-time":"2020-03-24T13:04:04Z","timestamp":1585055044000},"page":"74","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":9,"title":["Bi-Objective Dynamic Multiprocessor Open Shop Scheduling: An Exact Algorithm"],"prefix":"10.3390","volume":"13","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-1516-6057","authenticated-orcid":false,"given":"Tamer F.","family":"Abdelmaguid","sequence":"first","affiliation":[{"name":"Department of Mechanical Design and Production, Faculty of Engineering, Cairo University, Giza 12613, Egypt"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"1968","published-online":{"date-parts":[[2020,3,24]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","unstructured":"Pinedo, M. (2012). Scheduling: Theory, Algorithms, and Systems, Springer.","DOI":"10.1007\/978-1-4614-2361-4"},{"key":"ref_2","doi-asserted-by":"crossref","unstructured":"Werner, F., Burtseva, L., and Sotskov, Y.N. (2018). Special Issue on Algorithms for Scheduling Problems. Algorithms, 11.","DOI":"10.3390\/a11060087"},{"key":"ref_3","doi-asserted-by":"crossref","unstructured":"Werner, F., Burtseva, L., and Sotskov, Y.N. (2019). Special Issue on Exact and Heuristic Scheduling Algorithms. Algorithms, 13.","DOI":"10.3390\/a13010009"},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"186","DOI":"10.1016\/j.jmsy.2018.10.004","article-title":"Production rescheduling review: Opportunities for industrial integration and practical applications","volume":"49","author":"Uhlmann","year":"2018","journal-title":"J. Manuf. Syst."},{"key":"ref_5","doi-asserted-by":"crossref","unstructured":"Hwang, C.L., and Masud, A.S.M. (1979). Multiple Objective Decision Making\u2014Methods and Applications: A State-of-the-Art Survey, Springer.","DOI":"10.1007\/978-3-642-45511-7"},{"key":"ref_6","first-page":"169","article-title":"Optimization and approximation in deterministic sequencing and scheduling: A survey","volume":"5","author":"Graham","year":"1979","journal-title":"Ann. Discret. Math."},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"117","DOI":"10.1051\/ro:1999108","article-title":"Les flowshop hybrides: \u00e9tat de l\u2019art (in French)","volume":"33","author":"Vignier","year":"1999","journal-title":"RAIRO-Oper. Res."},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"665","DOI":"10.1145\/321978.321985","article-title":"Open Shop Scheduling to Minimize Finish Time","volume":"23","author":"Gonzalez","year":"1976","journal-title":"J. ACM"},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"709","DOI":"10.1137\/0211058","article-title":"Scheduling the open shop to minimize mean flow time","volume":"11","author":"Achugbue","year":"1982","journal-title":"SIAM J. Comput."},{"key":"ref_10","doi-asserted-by":"crossref","unstructured":"Seraj, O., Tavakkoli-Moghaddam, R., and Jolai, F. (200, January 6\u20138). A fuzzy multi-objective tabu-search method for a new bi-objective open shop scheduling problem. Proceedings of the 2009 International Conference on Computers Industrial Engineering, Troyes, France.","DOI":"10.1109\/ICCIE.2009.5223549"},{"key":"ref_11","unstructured":"Sha, D.Y., Lin, H.H., and Hsu, C.Y. (2010, January 17\u201319). A Modified Particle Swarm Optimization for Multi-objective Open Shop Scheduling. Proceedings of the International MultiConference of Engineers and Computer Scientists 2010 (IMECS 2010), Hong Kong, China."},{"key":"ref_12","doi-asserted-by":"crossref","unstructured":"Tavakkoli-Moghaddam, R., Panahi, H., and Heydar, M. (2008, January 8\u201311). Minimization of weighted tardiness and makespan in an open shop environment by a novel hybrid multi-objective meta-heuristic method. Proceedings of the 2008 IEEE International Conference on Industrial Engineering and Engineering Management, Singapore.","DOI":"10.1109\/IEEM.2008.4737895"},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"2817","DOI":"10.1016\/j.eswa.2010.08.073","article-title":"Solving a multi-objective open shop scheduling problem by a novel hybrid ant colony optimization","volume":"38","author":"Panahi","year":"2011","journal-title":"Expert Syst. Appl."},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"895","DOI":"10.1007\/s00170-012-4375-x","article-title":"Scheduling multi-objective open shop scheduling using a hybrid immune algorithm","volume":"66","author":"Naderi","year":"2013","journal-title":"Int. J. Adv. Manuf. Tech."},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"157","DOI":"10.1016\/S0167-6377(99)00005-X","article-title":"Approximation algorithms for the multiprocessor open shop scheduling problem","volume":"24","author":"Schuurman","year":"1999","journal-title":"Oper. Res. Lett."},{"key":"ref_16","doi-asserted-by":"crossref","unstructured":"Reichel, H., and Tison, S. (2000). Polynomial Time Approximation Schemes for the Multiprocessor Open and Flow Shop Scheduling Problem. STACS 2000, Springer.","DOI":"10.1007\/3-540-46541-3"},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"273","DOI":"10.1016\/S0166-218X(00)00375-9","article-title":"Linear time approximation scheme for the multiprocessor open shop problem","volume":"114","author":"Sevastianov","year":"2001","journal-title":"Discret. Appl. Math."},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"1275","DOI":"10.1016\/j.cam.2010.08.013","article-title":"Scheduling open shops with parallel machines to minimize total completion time","volume":"235","author":"Naderi","year":"2011","journal-title":"J. Comput. Appl. Math."},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"9603","DOI":"10.1016\/j.apm.2013.05.002","article-title":"A hybrid imperialist competitive algorithm for minimizing makespan in a multi-processor open shop","volume":"37","author":"Goldansaz","year":"2013","journal-title":"Appl. Math. Model."},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"106292","DOI":"10.1016\/j.cie.2020.106292","article-title":"Scatter search with path relinking for multiprocessor open shop scheduling","volume":"141","author":"Abdelmaguid","year":"2020","journal-title":"Comput. Ind. Eng."},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"2601","DOI":"10.1016\/j.cor.2008.11.009","article-title":"A genetic algorithm for the proportionate multiprocessor open shop","volume":"36","author":"Matta","year":"2009","journal-title":"Comput. Oper. Res."},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"187","DOI":"10.1007\/s10589-013-9621-0","article-title":"A tabu search approach for proportionate multiprocessor open shop scheduling","volume":"58","author":"Abdelmaguid","year":"2014","journal-title":"Comput. Optim. Appl."},{"key":"ref_23","doi-asserted-by":"crossref","unstructured":"Abdelmaguid, T.F. (2014, January 9\u201312). A Hybrid PSO-TS Approach for Proportionate Multiprocessor Open Shop Scheduling. Proceedings of the 2014 IEEE International Conference on Industrial Engineering and Engineering Management (IEEM), Bandar Sunway, Malaysia.","DOI":"10.1109\/IEEM.2014.7058610"},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"385","DOI":"10.1007\/s10878-017-0246-6","article-title":"Large-scale medical examination scheduling technology based on intelligent optimization","volume":"37","author":"Zhang","year":"2019","journal-title":"J. Combin. Optim."},{"key":"ref_25","doi-asserted-by":"crossref","first-page":"207","DOI":"10.1016\/j.cor.2015.10.012","article-title":"Flexible open shop scheduling problem to minimize makespan","volume":"67","author":"Bai","year":"2016","journal-title":"Comput. Oper. Res."},{"key":"ref_26","doi-asserted-by":"crossref","unstructured":"Wang, Y.T.H., and Chou, F.D. (2017, January 21\u201323). A Bi-criterion Simulated Annealing Method to Solve Four-Stage Multiprocessor Open Shops with Dynamic Job Release Time. Proceedings of the 2017 International Conference on Computing Intelligence and Information System (CIIS), Nanjing, China.","DOI":"10.1109\/CIIS.2017.61"},{"key":"ref_27","doi-asserted-by":"crossref","unstructured":"Abdelmaguid, T.F. (2018). An Efficient Mixed Integer Linear Programming Model for the Minimum Spanning Tree Problem. Mathematics, 6.","DOI":"10.3390\/math6100183"},{"key":"ref_28","doi-asserted-by":"crossref","first-page":"621","DOI":"10.1287\/opre.7.5.621","article-title":"The Schedule-Sequencing Problem","volume":"7","author":"Bowman","year":"1959","journal-title":"Oper. Res."},{"key":"ref_29","doi-asserted-by":"crossref","first-page":"131","DOI":"10.1002\/nav.3800060205","article-title":"An integer linear-programming model for machine scheduling","volume":"6","author":"Wagner","year":"1959","journal-title":"Nav. Res. Logist. Q."},{"key":"ref_30","doi-asserted-by":"crossref","first-page":"219","DOI":"10.1287\/opre.8.2.219","article-title":"On the Job-Shop Scheduling Problem","volume":"8","author":"Manne","year":"1960","journal-title":"Oper. Res."},{"key":"ref_31","doi-asserted-by":"crossref","first-page":"88","DOI":"10.1057\/palgrave.jors.2601805","article-title":"Comparative evaluation of MILP flowshop models","volume":"56","author":"Stafford","year":"2005","journal-title":"J. Oper. Res. Soc."},{"key":"ref_32","doi-asserted-by":"crossref","first-page":"4657","DOI":"10.1080\/00207543.2010.497174","article-title":"A study on open shop scheduling to minimise total tardiness","volume":"49","author":"Naderi","year":"2011","journal-title":"Int. J. Prod. Res."},{"key":"ref_33","doi-asserted-by":"crossref","first-page":"977","DOI":"10.1016\/j.apm.2012.03.020","article-title":"Evaluation of mathematical models for flexible job-shop scheduling problems","volume":"37","author":"Demir","year":"2013","journal-title":"Appl. Math. Model."},{"key":"ref_34","doi-asserted-by":"crossref","first-page":"165","DOI":"10.1016\/j.cor.2016.04.006","article-title":"Mixed Integer Programming models for job shop scheduling: A computational analysis","volume":"73","author":"Ku","year":"2016","journal-title":"Comput. Oper. Res."},{"key":"ref_35","first-page":"455","article-title":"Effective implementation of the \u03f5-constraint method in Multi-Objective Mathematical Programming problems","volume":"213","author":"Mavrotas","year":"2009","journal-title":"Appl. Math. Comput."},{"key":"ref_36","unstructured":"Van Hentenryck, P. (1999). The OPL Optimization Programming Language, MIT Press."},{"key":"ref_37","doi-asserted-by":"crossref","first-page":"62","DOI":"10.1016\/j.ins.2019.05.048","article-title":"A many-objective population extremal optimization algorithm with an adaptive hybrid mutation operation","volume":"498","author":"Chen","year":"2019","journal-title":"Inform. Sci."}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/13\/3\/74\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T09:11:12Z","timestamp":1760173872000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/13\/3\/74"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,3,24]]},"references-count":37,"journal-issue":{"issue":"3","published-online":{"date-parts":[[2020,3]]}},"alternative-id":["a13030074"],"URL":"https:\/\/doi.org\/10.3390\/a13030074","relation":{},"ISSN":["1999-4893"],"issn-type":[{"value":"1999-4893","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,3,24]]}}}