{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,3]],"date-time":"2026-04-03T00:48:01Z","timestamp":1775177281856,"version":"3.50.1"},"reference-count":42,"publisher":"MDPI AG","issue":"7","license":[{"start":{"date-parts":[[2023,7,10]],"date-time":"2023-07-10T00:00:00Z","timestamp":1688947200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Computation"],"abstract":"<jats:p>This paper presents a comprehensive approach for minimizing makespan in the challenging two-stage hybrid flowshop with dedicated machines, a problem known to be strongly NP-hard. This study proposed a constraint programming approach, a novel heuristic based on a priority rule, and Tabu search procedures to tackle this optimization problem. The constraint programming model, implemented using a commercial solver, serves as the exact resolution method, while the heuristic and Tabu search explore approximate solutions simultaneously. The motivation behind this research is the need to address the complexities of scheduling problems in the context of two-stage hybrid flowshop with dedicated machines. This problem presents significant challenges due to its NP-hard nature and the need for efficient optimization techniques. The contribution of this study lies in the development of an integrated approach that combines constraint programming, a novel heuristic, and Tabu search to provide a comprehensive and efficient solution. The proposed constraint programming model offers exact resolution capabilities, while the heuristic and Tabu search provide approximate solutions, offering a balance between accuracy and efficiency. To enhance the search process, the research introduces effective elimination rules, which reduce the search space and simplify the search effort. This approach improves the overall optimization performance and contributes to finding high-quality solutions. The results demonstrate the effectiveness of the proposed approach. The heuristic approach achieves complete success in solving all instances for specific classes, showcasing its practical applicability. Furthermore, the constraint programming model exhibits exceptional efficiency, successfully solving problems with up to n=500 jobs. This efficiency is noteworthy compared to instances solved by other exact solution approaches, indicating the scalability and effectiveness of the proposed method.<\/jats:p>","DOI":"10.3390\/computation11070137","type":"journal-article","created":{"date-parts":[[2023,7,11]],"date-time":"2023-07-11T01:40:02Z","timestamp":1689039602000},"page":"137","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":8,"title":["Makespan Minimization for the Two-Stage Hybrid Flow Shop Problem with Dedicated Machines: A Comprehensive Study of Exact and Heuristic Approaches"],"prefix":"10.3390","volume":"11","author":[{"given":"Mohamed Karim","family":"Hajji","sequence":"first","affiliation":[{"name":"College of Engineering and Technology, American University of the Middle East, Egaila 54200, Kuwait"}]},{"given":"Hatem","family":"Hadda","sequence":"additional","affiliation":[{"name":"Oasis, Ecole Nationale d\u2019Ing\u00e9nieurs de Tunis, Universit\u00e9 de Tunis El Manar, Tunis 1068, Tunisia"}]},{"given":"Najoua","family":"Dridi","sequence":"additional","affiliation":[{"name":"Oasis, Ecole Nationale d\u2019Ing\u00e9nieurs de Tunis, Universit\u00e9 de Tunis El Manar, Tunis 1068, Tunisia"}]}],"member":"1968","published-online":{"date-parts":[[2023,7,10]]},"reference":[{"key":"ref_1","unstructured":"Esswein, C. (2003). Un Apport de Flexibilit\u00e9 S\u00e9quentielle pour L\u2019ordonnancement Robuste. [Ph.D. Thesis, Tours]."},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"535","DOI":"10.1016\/S0377-2217(99)00224-6","article-title":"Sequencing of jobs in some production system","volume":"125","author":"Grabowski","year":"2000","journal-title":"Eur. J. Oper. Res."},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"216","DOI":"10.1111\/j.1937-5956.2002.tb00492.x","article-title":"Scheduling hybrid flowshops in printed circuit board assembly lines","volume":"11","author":"Jin","year":"2002","journal-title":"Prod. Oper. Manag."},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"133","DOI":"10.1016\/S0925-5273(03)00011-2","article-title":"A case study in a two-stage hybrid flow shop with setup time and dedicated machines","volume":"86","author":"Lin","year":"2003","journal-title":"Int. J. Prod. Econ."},{"key":"ref_5","unstructured":"Hadda, H. (2009). Contribution \u00e0 L\u2019\u00e9tude et \u00e0 la R\u00e9solution des Probl\u00e8mes D\u2019ordonnancement de Flow Shops D\u2019assemblage et de Flow Shops Hybrides \u00e0 Machines D\u00e9di\u00e9es. [Ph.D. Thesis, \u00c9cole Nationale d\u2019ing\u00e9nieurs de Tunis]."},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"113556","DOI":"10.1016\/j.eswa.2020.113556","article-title":"A comprehensive review of branch-and-bound algorithms: Guidelines and directions for further research on the flowshop scheduling problem","volume":"158","author":"Tomazella","year":"2020","journal-title":"Expert Syst. Appl."},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"400","DOI":"10.1287\/opre.13.3.400","article-title":"Application of the branch and bound technique to some flow-shop scheduling problems","volume":"13","author":"Ignall","year":"1965","journal-title":"Oper. Res."},{"key":"ref_8","unstructured":"Besbes, W., Loukil, T., and Teghem, J. (2010, January 10\u201312). A two-stage flow shop with parallel dedicated Machines. Proceedings of the 8th International Conference of Modeling and Simulation\u2014MOSIM, Hammamet, Tunisia."},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"12","DOI":"10.1016\/j.ijpe.2015.03.013","article-title":"A parallel neighborhood search for order acceptance and scheduling in flow shop environment","volume":"165","author":"Lei","year":"2015","journal-title":"Int. J. Prod. Econ."},{"key":"ref_10","first-page":"11","article-title":"Milp formulation and genetic algorithm for non-permutation flow shop scheduling problem with availability constraints","volume":"4","author":"Ramezanian","year":"2014","journal-title":"Int. J. Appl. Oper. Res."},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"1705","DOI":"10.1021\/ie1016199","article-title":"Integrated constraint programming scheduling approach for automated wet-etch stations in semiconductor manufacturing","volume":"50","author":"Zeballos","year":"2011","journal-title":"Ind. Eng. Chem. Res."},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"141","DOI":"10.1016\/j.cor.2016.12.013","article-title":"On the exact solution of the no-wait flow shop problem with due date constraints","volume":"81","author":"Samarghandi","year":"2017","journal-title":"Comput. Oper. Res."},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"614","DOI":"10.1016\/j.cie.2019.07.048","article-title":"Minimizing the makespan in a flow shop environment under minimum and maximum time-lag constraints","volume":"136","author":"Samarghandi","year":"2019","journal-title":"Comput. Ind. Eng."},{"key":"ref_14","unstructured":"Said, A.B., and Mouhoub, M. (2022, January 4\u20137). A constraint satisfaction problem (csp) approach for the nurse scheduling problem. Proceedings of the 2022 IEEE Symposium Series on Computational Intelligence (SSCI), Singapore."},{"key":"ref_15","unstructured":"Gehring, M., Volk, R., Braun, N., and Schultmann, F. (2021). International Conference on Operations Research, Springer."},{"key":"ref_16","first-page":"131","article-title":"A constraint programming approach to scheduling of malleable tasks","volume":"9","author":"Nishikawa","year":"2019","journal-title":"Int. J. Netw. Comput."},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"874","DOI":"10.1016\/j.ejor.2022.01.034","article-title":"An algorithm selection approach for the flexible job shop scheduling problem: Choosing constraint programming solvers through machine learning","volume":"302","author":"Kress","year":"2022","journal-title":"Eur. J. Oper. Res."},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"2212","DOI":"10.1080\/00207543.2021.1885068","article-title":"Constraint programming approach for multi-resource-constrained unrelated parallel machine scheduling problem with sequence-dependent setup times","volume":"60","author":"Yunusoglu","year":"2022","journal-title":"Int. J. Prod. Res."},{"key":"ref_19","unstructured":"Herrmann, J.W., and Lee, C.-Y. (1992). Three-Machine Look-Ahead Scheduling Problems, Department of Industrial and Systems Engineering, University of Florida."},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"61","DOI":"10.1002\/nav.3800010110","article-title":"Optimal two-and three-stage production schedules with setup times included","volume":"1","author":"Johnson","year":"1954","journal-title":"Nav. Res. Logist. Q."},{"key":"ref_21","unstructured":"Conway, R.W., Maxwell, W.L., and Miller, L.W. (1967). Theory of Scheduling, Addison-Wesley Publishing Company."},{"key":"ref_22","unstructured":"Xiao, W., Hao, P., Zhang, S., and Xu, X. (July, January 26). Hybrid flow shop scheduling using genetic Algorithms. Proceedings of the 3rd World Congress on Intelligent Control and Automation (Cat. No. 00EX393), Hefei, China."},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"43","DOI":"10.1016\/S0167-6377(97)00004-7","article-title":"Heuristic algorithms for the two-stage hybrid flowshop problem","volume":"21","author":"Haouari","year":"1997","journal-title":"Oper. Res. Lett."},{"key":"ref_24","unstructured":"Hajji, M.K., and Hadda, H. (2012). Contribution \u00e0 la R\u00e9solution des Probl\u00e8mes de Flow Shops avec Mechines D\u00e9di\u00e9es, Dates de Disponiblit\u00e9 et D\u00e9lais de Livraison. [Master\u2019s Thesis, Institut Sup\u00e8rieur de Transport et de la Logistique]."},{"key":"ref_25","first-page":"300","article-title":"The two-stage hybrid flow shop problem with dedicated machines under release dates and delivery times","volume":"7","author":"Hajji","year":"2015","journal-title":"Int. J. Adv. Oper. Manag."},{"key":"ref_26","doi-asserted-by":"crossref","first-page":"226","DOI":"10.1016\/S0377-2217(97)00260-9","article-title":"The flow shop with parallel machines: A tabu search approach","volume":"106","author":"Nowicki","year":"1998","journal-title":"Eur. J. Oper. Res."},{"key":"ref_27","doi-asserted-by":"crossref","first-page":"380","DOI":"10.1016\/S0377-2217(02)00873-1","article-title":"A tabu search algorithm for the multi-stage parallel machine problem with limited buffer capacities","volume":"155","author":"Wardono","year":"2004","journal-title":"Eur. J. Oper. Res."},{"key":"ref_28","doi-asserted-by":"crossref","first-page":"322","DOI":"10.1016\/j.ijpe.2004.12.025","article-title":"Metaheuristic algorithms for the multistage hybrid flowshop scheduling problem","volume":"100","author":"Jin","year":"2006","journal-title":"Int. J. Prod. Econ."},{"key":"ref_29","doi-asserted-by":"crossref","first-page":"1891","DOI":"10.1016\/S0305-0548(03)00145-X","article-title":"A very fast tabu search algorithm for the permutation flow shop problem with makespan criterion","volume":"31","author":"Grabowski","year":"2004","journal-title":"Comput. Oper. Res."},{"key":"ref_30","doi-asserted-by":"crossref","first-page":"40","DOI":"10.1016\/j.ejor.2006.06.033","article-title":"A tabu search algorithm for the integrated scheduling problem of container handling systems in a maritime terminal","volume":"181","author":"Chen","year":"2007","journal-title":"Eur. J. Oper. Res."},{"key":"ref_31","first-page":"7459","article-title":"A hybrid genetic algorithm and tabu search for minimizing makespan in flow shop scheduling problem","volume":"34","author":"Umam","year":"2022","journal-title":"J. King Saud Univ. Comput. Inf. Sci."},{"key":"ref_32","doi-asserted-by":"crossref","first-page":"107318","DOI":"10.1016\/j.cie.2021.107318","article-title":"A multi-objective scheduling method for distributed and flexible job shop based on hybrid genetic algorithm and tabu search considering operation outsourcing and carbon emission","volume":"157","author":"Xu","year":"2021","journal-title":"Comput. Ind. Eng."},{"key":"ref_33","doi-asserted-by":"crossref","first-page":"106185","DOI":"10.1016\/j.cor.2023.106185","article-title":"Tabu search for proactive project scheduling problem with flexible resources","volume":"153","author":"Ma","year":"2023","journal-title":"Comput. Oper. Res."},{"key":"ref_34","doi-asserted-by":"crossref","first-page":"466","DOI":"10.1109\/TIV.2022.3166564","article-title":"Real-time scheduling of autonomous mining trucks via flow allocation-accelerated tabu search","volume":"7","author":"Zhang","year":"2022","journal-title":"IEEE Trans. Intell. Veh."},{"key":"ref_35","doi-asserted-by":"crossref","first-page":"287","DOI":"10.1016\/S0167-5060(08)70356-X","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_36","doi-asserted-by":"crossref","first-page":"544","DOI":"10.1287\/mnsc.19.5.544","article-title":"Optimal sequencing of a single machine subject to precedence Constraints","volume":"19","author":"Lawler","year":"1973","journal-title":"Manag. Sci."},{"key":"ref_37","unstructured":"Brucker, P., and Knust, S. (2023, June 14). Complexity Results for Scheduling Problems. Available online: http:\/\/www.mathematik.uni-osnabrueck.de\/research\/OR\/class."},{"key":"ref_38","unstructured":"Baptiste, P., Le Pape, C., and Nuijten, W. (2012). Constraint-Based Scheduling: Applying Constraint Programming to Scheduling Problems, Springer Science & Business Media."},{"key":"ref_39","doi-asserted-by":"crossref","first-page":"5073","DOI":"10.1080\/00207543.2013.784418","article-title":"Batch scheduling in differentiation flow shops for makespan minimization","volume":"51","author":"Huang","year":"2013","journal-title":"Int. J. Prod. Res."},{"key":"ref_40","unstructured":"Hajji, M.K., Hadda, H., and Dridi, N. (2016, January 10\u201312). Une heuristique pour le flow shop hybride \u00e0 deux \u00e9tages avec machines d\u00e9di\u00e9es. Proceedings of the ROADEF 2016: 17eme Congr\u00e9 Annuel de le Soci\u00e9t\u00e9 Fran\u00e7aise de Recherche Op\u00e9rationnelle et d\u2019Aide \u00e0 la D\u00e9cision, Compi\u00e8gne, France."},{"key":"ref_41","doi-asserted-by":"crossref","first-page":"421","DOI":"10.1051\/ro\/2009024","article-title":"M\u00e9thode heuristique pour le probl\u00e8me de flow shop hybride avec machines d\u00e9di\u00e9es","volume":"43","author":"Dridi","year":"2009","journal-title":"RAIRO-Oper. Res."},{"key":"ref_42","doi-asserted-by":"crossref","first-page":"2329","DOI":"10.1007\/s11590-014-0741-y","article-title":"Exact resolution of the two-stage hybrid flow shop with dedicated machines","volume":"8","author":"Hadda","year":"2014","journal-title":"Optim. Lett."}],"container-title":["Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/2079-3197\/11\/7\/137\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,10]],"date-time":"2025-10-10T20:09:57Z","timestamp":1760126997000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/2079-3197\/11\/7\/137"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,7,10]]},"references-count":42,"journal-issue":{"issue":"7","published-online":{"date-parts":[[2023,7]]}},"alternative-id":["computation11070137"],"URL":"https:\/\/doi.org\/10.3390\/computation11070137","relation":{},"ISSN":["2079-3197"],"issn-type":[{"value":"2079-3197","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,7,10]]}}}