A new two-stage constraint programming approach for open shop scheduling problem with machine blocking

References

• Abreu, Levi R., Jesus O. Cunha, Bruno A. Prata, and Jose M. Framinan. 2020. “A Genetic Algorithm for Scheduling Open Shops with Sequence-dependent Setup Times.” Computers & Operations Research 113: 104793.
   Web of Science ®Google Scholar
• Abreu, Levi R., and Marcelo S. Nagano. 2022. “A New Hybridization of Adaptive Large Neighborhood Search with Constraint Programming for Open Shop Scheduling with Sequence-dependent Setup Times.” Computers & Industrial Engineering 168: 108128.
   Web of Science ®Google Scholar
• Abreu, Levi R., Bruno A. Prata, Jose M. Framinan, and Marcelo S. Nagano. 2022. “New Efficient Heuristics for Scheduling Open Shops with Makespan Minimization.” Computers & Operations Research142: 105744.
   Web of Science ®Google Scholar
• Abreu, Levi R., Roberto F. Tavares-Neto, and Marcelo S. Nagano. 2021. “A New Efficient Biased Random Key Genetic Algorithm for Open Shop Scheduling with Routing by Capacitated Single Vehicle and Makespan Minimization.” Engineering Applications of Artificial Intelligence 104: 104373.
   Web of Science ®Google Scholar
• Ahmadian, Mohammad Mahdi, Mostafa Khatami, Amir Salehipour, and T. C. E. Cheng. 2021. “Four Decades of Research on the Open-shop Scheduling Problem to Minimize the Makespan.” European Journal of Operational Research 295 (2): 399–426.
   Web of Science ®Google Scholar
• Ahmadizar, Fardin, and Mehdi Hosseinabadi Farahani. 2012. “A Novel Hybrid Genetic Algorithm for the Open Shop Scheduling Problem.” The International Journal of Advanced Manufacturing Technology62 (5–8): 775–787.
   Web of Science ®Google Scholar
• Al-Salem, A., et al. 2004. “Scheduling to Minimize Makespan on Unrelated Parallel Machines with Sequence Dependent Setup Times.” Engineering Journal of the University of Qatar 17 (1): 177–187.
   Google Scholar
• Apt, Krzysztof. 2003. Principles of Constraint Programming. Cambridge: Cambridge University Press.
   Google Scholar
• Bai, Danyu, Zhihai Zhang, Qiang Zhang, and Mengqian Tang. 2017. “Open Shop Scheduling Problem to Minimize Total Weighted Completion Time.” Engineering Optimization 49 (1): 98–112.
   Web of Science ®Google Scholar
• Behnamian, Javad, and S. M. T. Fatemi Ghomi. 2016. “A Survey of Multi-factory Scheduling.” Journal of Intelligent Manufacturing 27 (1): 231–249.
   Web of Science ®Google Scholar
• Bruckner, P., J. Hurink, B. Jurish, and B. Wöstmann. 1997. “A Branch and Bound Algorithm for the Open-shop Problem.” Discrete Applied Mathematics 76 (1–3): 43–59.
   Web of Science ®Google Scholar
• Dabah, Adel, Ahcene Bendjoudi, Abdelhakim AitZai, and Nadia Nouali Taboudjemat. 2019. “Efficient Parallel Tabu Search for the Blocking Job Shop Scheduling Problem.” Soft Computing 23 (24): 13283–13295.
   Web of Science ®Google Scholar
• Levi Ribeiro de Abreu, Kennedy A. Guimarães Araújo, Bruno de Athayde Prata, Marcelo Seido Nagano, and João Vitor Moccellin. 2021. “A New Variable Neighbourhood Search with a Constraint Programming Search Strategy for the Open Shop Scheduling Problem with Operation Repetitions.” Engineering Optimization 50: 1–20.
   Google Scholar
• de Araújo, Kennedy A. Guimarães, Tiberius Oliveira Bonates, and Bruno de Athayde Prata. 2021. “Modeling and Scheduling Hybrid Open Shops for Makespan Minimization.” Journal of Modelling in Management 17 (4): 1566–1586.
   Web of Science ®Google Scholar
• Gedik, Ridvan, Darshan Kalathia, Gokhan Egilmez, and Emre Kirac. 2018. “A Constraint Programming Approach for Solving Unrelated Parallel Machine Scheduling Problem.” Computers & Industrial Engineering 121: 139–149.
   Web of Science ®Google Scholar
• Gonzalez, T., and S. Sahni. 1976. “Open-shop Scheduling to Minimize Finish Time.” Journal of the Association for Computing Machinery 23 (4): 665–679.
   Web of Science ®Google Scholar
• Guéret, C., and C. Prins. 1998. “Classical and New Heuristics for the Open-shop Problem: A Computational Evaluation.” European Journal of Operational Research 107 (2): 306–314.
   Web of Science ®Google Scholar
• Guéret, C., and C. Prins. 1999. “A New Lower Bound for the Open Shop Problem.” Annals of Operations Research 92: 165–183.
   Web of Science ®Google Scholar
• Hall, Nicholas G., and Chelliah Sriskandarajah. 1996. “A Survey of Machine Scheduling Problems with Blocking and No-wait in Process.” Operations Research 44 (3): 510–525.
   Web of Science ®Google Scholar
• Hande, Öztop, M. Fatih Tasgetiren, Levent Kandiller, and Quan-Ke Pan. 2021. “Metaheuristics with Restart and Learning Mechanisms for the No-idle Flowshop Scheduling Problem with Makespan Criterion.” Computers & Operations Research 138105616.
   Web of Science ®Google Scholar
• Hardin, Jill R., George L. Nemhauser, and Martin W. P. Savelsbergh. 2008. “Strong Valid Inequalities for the Resource-constrained Scheduling Problem with Uniform Resource Requirements.” Discrete Optimization 5 (1): 19–35.
   Web of Science ®Google Scholar
• Hojabri, Hossein, Michel Gendreau, Jean-Yves Potvin, and Louis-Martin Rousseau. 2018. “Large Neighborhood Search with Constraint Programming for a Vehicle Routing Problem with Synchronization Constraints.” Computers & Operations Research 92: 87–97.
   Web of Science ®Google Scholar
• Kang, Liujiang, Shukai Chen, and Qiang Meng. 2019. “Bus and Driver Scheduling with Mealtime Windows for a Single Public Bus Route.” Transportation Research Part C: Emerging Technologies 101: 145–160.
   Web of Science ®Google Scholar
• Kelbel, Jan, and Zdeněk Hanzálek. 2011. “Solving Production Scheduling with Earliness/tardiness Penalties by Constraint Programming.” Journal of Intelligent Manufacturing 22 (4): 553–562.
   Web of Science ®Google Scholar
• Laborie, Philippe. 2018. “An Update on the Comparison of MIP, CP and Hybrid Approaches for Mixed Resource Allocation and Scheduling.” In International Conference on the Integration of Constraint Programming, Artificial Intelligence, and Operations Research, 403–411. Springer.
   Google Scholar
• Laborie, Philippe, and Daniel Godard. 2007. “Self-adapting Large Neighborhood Search: Application to Single-Mode Scheduling Problems.” Proceedings MISTA-07, Paris, 8.
   Google Scholar
• Lange, Julia, and Frank Werner. 2019. “On Neighborhood Structures and Repair Techniques for Blocking Job Shop Scheduling Problems.” Algorithms 12 (11): 242.
   Web of Science ®Google Scholar
• LaTorre, Antonio, Daniel Molina, Eneko Osaba, Javier Del Ser, and Francisco Herrera. 2020. ““Fairness in Bio-inspired Optimization Research: A Prescription of Methodological Guidelines for Comparing Meta-Heuristics.” arXiv, preprint arXiv:2004.09969.
   Google Scholar
• Levner, E. V. 1969. “Optimal Planning of Parts' Machining on a Number of Machines.” Automatin and Remote Control 12 (12): 1972–1978.
   Google Scholar
• Lin, Hung-Tso, Hong-Tau Lee, and Wen-Jung Pan. 2008. “Heuristics for Scheduling in a No-wait Open Shop with Movable Dedicated Machines.” International Journal of Production Economics 111 (2): 368–377. Special Section on Sustainable Supply Chain, http://www.sciencedirect.com/science/article/pii/S0925527307000515
   Web of Science ®Google Scholar
• Malapert, Arnaud, Hadrien Cambazard, Christelle Guéret, Narendra Jussien, André Langevin, and Louis-Martin Rousseau. 2012. “An Optimal Constraint Programming Approach to the Open-shop Problem.” INFORMS Journal on Computing 24 (2): 228–244.
   Web of Science ®Google Scholar
• Mascis, Alessandro, and Dario Pacciarelli. 2002. “Job-shop Scheduling with Blocking and No-wait Constraints.” European Journal of Operational Research 143 (3): 498–517.
   Web of Science ®Google Scholar
• Mejía, Gonzalo, Juan Pablo Caballero-Villalobos, and Carlos Montoya. 2018. “Petri Nets and Deadlock-free Scheduling of Open Shop Manufacturing Systems.” IEEE Transactions on Systems, Man, and Cybernetics: Systems 48 (6): 1017–1028.
   Web of Science ®Google Scholar
• Mejía, Gonzalo, and Francisco Yuraszeck. 2020. “A Self-tuning Variable Neighborhood Search Algorithm and An Effective Decoding Scheme for Open Shop Scheduling Problems with Travel/setup Times.” European Journal of Operational Research 285 (2): 484–496.
   Web of Science ®Google Scholar
• Meng, Leilei, Chaoyong Zhang, Yaping Ren, Biao Zhang, and Chang Lv. 2020. “Mixed-integer Linear Programming and Constraint Programming Formulations for Solving Distributed Flexible Job Shop Scheduling Problem.” Computers & Industrial Engineering 142: 106347.
   Web of Science ®Google Scholar
• Miyata, Hugo Hissashi, and Marcelo Seido Nagano. 2019. “The Blocking Flow Shop Scheduling Problem: A Comprehensive and Conceptual Review.” Expert Systems with Applications 137: 130–156.
   Web of Science ®Google Scholar
• Moccellin, João Vitor, Marcelo Seido Nagano, Anselmo Ramalho Pitombeira Neto, and Bruno de Athayde Athayde Prata. 2018. “Heuristic Algorithms for Scheduling Hybrid Flow Shops with Machine Blocking and Setup Times.” Journal of the Brazilian Society of Mechanical Sciences and Engineering40 (2): 40. doi:10.1007/s40430-018-0980-4
   Web of Science ®Google Scholar
• Mogali, Jayanth Krishna, Laura Barbulescu, and Stephen F. Smith. 2021. “Efficient Primal Heuristic Updates for the Blocking Job Shop Problem.” European Journal of Operational Research 295 (1), 82–101.
   Web of Science ®Google Scholar
• Montgomery, Douglas C. 2017. Design and Analysis of Experiments. New York: John Wiley & Sons.
   Google Scholar
• Naderi, B., S. M. T. Fatemi Ghomi, M. Aminnayeri, and M. Zandieh. 2010. “A Contribution and New Heuristics for Open Shop Scheduling.” Computers & Operations Research 37 (1): 213–221.
   Web of Science ®Google Scholar
• Naderi, B., S. M. T. Fatemi Ghomi, M. Aminnayeri, and M. Zandieh. 2011. “A Study on Open Shop Scheduling to Minimise Total Tardiness.” International Journal of Production Research 49 (15): 4657–4678.
   Web of Science ®Google Scholar
• Naderi, Bahman, Esmaeil Najafi, and Mehdi Yazdani. 2012. “An Electromagnetism-like Metaheuristic for Open-shop Problems with No Buffer.” Journal of Industrial Engineering International 8 (1): 29. doi:10.1186/2251-712X-8-29
   Google Scholar
• Naderi, B., and M. Zandieh. 2014. “Modeling and Scheduling No-wait Open Shop Problems.” International Journal of Production Economics 158: 256–266.
   Web of Science ®Google Scholar
• Palacios, Juan José, Inés González-Rodríguez, Camino R. Vela, and Jorge Puente. 2015. “Swarm Lexicographic Goal Programming for Fuzzy Open Shop Scheduling.” Journal of Intelligent Manufacturing 26 (6): 1201–1215.
   Web of Science ®Google Scholar
• Pinedo, M. 2016. Scheduling: Theory, Algorithms, and Systems. New York: Springer.
   Google Scholar
• Rahmani Hosseinabadi, Ali Asghar, Javad Vahidi, Behzad Saemi, Arun Kumar Sangaiah, and Mohamed Elhoseny. 2018. “Extended Genetic Algorithm for Solving Open-shop Scheduling Problem.” Soft Computing 23 (13): 5099–5116. doi:10.1007/s00500-018-3177-y.
   Web of Science ®Google Scholar
• Rossi, Francesca, Peter Van Beek, and Toby Walsh. 2006. Handbook of Constraint Programming. New York: Elsevier.
   Google Scholar
• Saberi-Aliabad, Hossein, Mohammad Reisi-Nafchi, and Ghasem Moslehi. 2020. “Energy-efficient Scheduling in An Unrelated Parallel-machine Environment Under Time-of-use Electricity Tariffs.” Journal of Cleaner Production 249: 119393.
   Web of Science ®Google Scholar
• Sidney, Jeffrey B., and Chelliah Sriskandarajah. 1999. “A Heuristic for the Two-machine No-wait Openshop Scheduling Problem.” Naval Research Logistics (NRL) 46 (2): 129–145.
   Web of Science ®Google Scholar
• Stafford, E. F., Fan T. Tseng, and Jatinder N. D. Gupta. 2005. “Comparative Evaluation of MILP Flowshop Models.” Journal of the Operational Research Society 56 (1): 88–101.
   Web of Science ®Google Scholar
• Taillard, E. 1993. “Benchmarks for Basic Scheduling Problems.” European Journal of Operational Research 64 (2): 278–285.
   Web of Science ®Google Scholar
• Yao, Ming-Jong, Hanijanto Soewandi, and Salah E. Elmaghraby. 2000. “Simple Heuristics for the Two Machine Openshop Problem with Blocking.” Journal of the Chinese Institute of Industrial Engineers17 (5): 537–547. doi:10.1080/10170669.2000.10432874
   Google Scholar
• Yunusoglu, Pinar, and Seyda Topaloglu Yildiz. 2021. “Constraint Programming Approach for Multi-resource-constrained Unrelated Parallel Machine Scheduling Problem with Sequence-dependent Setup Times.” International Journal of Production Research 60 (7): 2212–2229.
   Web of Science ®Google Scholar
• Zarandi, M. H. Fazel, H. Khorshidian, and M. Akbarpour Shirazi. 2016. “A Constraint Programming Model for the Scheduling of JIT Cross-docking Systems with Preemption.” Journal of Intelligent Manufacturing 27 (2): 297–313.
   Web of Science ®Google Scholar