IDEAS home Printed from https://ideas.repec.org/a/eee/jomega/v117y2023ics0305048322002298.html
   My bibliography  Save this article

Constraint programming and logic-based Benders decomposition for the integrated process planning and scheduling problem

Author

Listed:
  • Zhu, Xuedong
  • Son, Junbo
  • Zhang, Xi
  • Wu, Jianguo

Abstract

The integrated process planning and scheduling (IPPS) problem is of critical importance in achieving desirable performance for complex manufacturing systems. The IPPS problem is often categorized into two types, i.e., Type-I and Type-II, depending on how the process plan is represented. In recent years, several approaches have been proposed to solve the IPPS problem in the literature. However, due to the complexity of the problem, optimal solutions of some benchmark datasets still cannot be obtained in a reasonable time, and few of them can be used to simultaneously address both types of IPPS problem. To this end, this study constructs a constraint programming (CP) model considering both types of IPPS problem, and proposes two basic logic-based Benders decomposition (LBBD) algorithms: one for each type of IPPS problem. In order to ensure computational efficiency, an enhanced LBBD algorithm is designed for both types of IPPS problem with three effective enhancement strategies. The performance of proposed methods is rigorously evaluated and compared with the existing approaches in the literature based on thirteen datasets. The results show that our methods significantly outperform these approaches.

Suggested Citation

  • Zhu, Xuedong & Son, Junbo & Zhang, Xi & Wu, Jianguo, 2023. "Constraint programming and logic-based Benders decomposition for the integrated process planning and scheduling problem," Omega, Elsevier, vol. 117(C).
    • Handle: RePEc:eee:jomega:v:117:y:2023:i:c:s0305048322002298
    DOI: 10.1016/j.omega.2022.102823
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0305048322002298
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.omega.2022.102823?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Han, Jialin & Zhang, Jiaxiang & Zeng, Bing & Mao, Mingsong, 2021. "Optimizing dynamic facility location-allocation for agricultural machinery maintenance using Benders decomposition," Omega, Elsevier, vol. 105(C).
    2. Arnaud Malapert & Hadrien Cambazard & Christelle Guéret & Narendra Jussien & André Langevin & Louis-Martin Rousseau, 2012. "An Optimal Constraint Programming Approach to the Open-Shop Problem," INFORMS Journal on Computing, INFORMS, vol. 24(2), pages 228-244, May.
    3. J. Carlier & E. Pinson, 1989. "An Algorithm for Solving the Job-Shop Problem," Management Science, INFORMS, vol. 35(2), pages 164-176, February.
    4. Ulrich Dorndorf & Erwin Pesch & Toàn Phan-Huy, 2002. "Constraint Propagation and Problem Decomposition: A Preprocessing Procedure for the Job Shop Problem," Annals of Operations Research, Springer, vol. 115(1), pages 125-145, September.
    5. Bukchin, Yossi & Raviv, Tal, 2018. "Constraint programming for solving various assembly line balancing problems," Omega, Elsevier, vol. 78(C), pages 57-68.
    6. S. Zhang & T. N. Wong, 2018. "Integrated process planning and scheduling: an enhanced ant colony optimization heuristic with parameter tuning," Journal of Intelligent Manufacturing, Springer, vol. 29(3), pages 585-601, March.
    7. Wheatley, David & Gzara, Fatma & Jewkes, Elizabeth, 2015. "Logic-based Benders decomposition for an inventory-location problem with service constraints," Omega, Elsevier, vol. 55(C), pages 10-23.
    8. Hooshmand, F. & Mirarabrazi, F. & MirHassani, S.A., 2020. "Efficient Benders decomposition for distance-based critical node detection problem," Omega, Elsevier, vol. 93(C).
    9. Zhang, Luping & Wong, T.N., 2015. "An object-coding genetic algorithm for integrated process planning and scheduling," European Journal of Operational Research, Elsevier, vol. 244(2), pages 434-444.
    10. Barzanji, Ramin & Naderi, Bahman & Begen, Mehmet A., 2020. "Decomposition algorithms for the integrated process planning and scheduling problem," Omega, Elsevier, vol. 93(C).
    11. J. N. Hooker, 2007. "Planning and Scheduling by Logic-Based Benders Decomposition," Operations Research, INFORMS, vol. 55(3), pages 588-602, June.
    12. Pohl, Maximilian & Artigues, Christian & Kolisch, Rainer, 2022. "Solving the time-discrete winter runway scheduling problem: A column generation and constraint programming approach," European Journal of Operational Research, Elsevier, vol. 299(2), pages 674-689.
    13. Liangliang Jin & Qiuhua Tang & Chaoyong Zhang & Xinyu Shao & Guangdong Tian, 2016. "More MILP models for integrated process planning and scheduling," International Journal of Production Research, Taylor & Francis Journals, vol. 54(14), pages 4387-4402, July.
    14. Diarmuid Grimes & Emmanuel Hebrard, 2015. "Solving Variants of the Job Shop Scheduling Problem Through Conflict-Directed Search," INFORMS Journal on Computing, INFORMS, vol. 27(2), pages 268-284, May.
    15. Enayaty-Ahangar, Forough & Rainwater, Chase E. & Sharkey, Thomas C., 2019. "A Logic-based Decomposition Approach for Multi-Period Network Interdiction Models," Omega, Elsevier, vol. 87(C), pages 71-85.
    16. Fatemi-Anaraki, Soroush & Tavakkoli-Moghaddam, Reza & Foumani, Mehdi & Vahedi-Nouri, Behdin, 2023. "Scheduling of Multi-Robot Job Shop Systems in Dynamic Environments: Mixed-Integer Linear Programming and Constraint Programming Approaches," Omega, Elsevier, vol. 115(C).
    17. Rahmaniani, Ragheb & Crainic, Teodor Gabriel & Gendreau, Michel & Rei, Walter, 2017. "The Benders decomposition algorithm: A literature review," European Journal of Operational Research, Elsevier, vol. 259(3), pages 801-817.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Guo, Penghui & Zhu, Jianjun, 2023. "Capacity reservation for humanitarian relief: A logic-based Benders decomposition method with subgradient cut," European Journal of Operational Research, Elsevier, vol. 311(3), pages 942-970.
    2. Barzanji, Ramin & Naderi, Bahman & Begen, Mehmet A., 2020. "Decomposition algorithms for the integrated process planning and scheduling problem," Omega, Elsevier, vol. 93(C).
    3. Hassan Zohali & Bahman Naderi & Vahid Roshanaei, 2022. "Solving the Type-2 Assembly Line Balancing with Setups Using Logic-Based Benders Decomposition," INFORMS Journal on Computing, INFORMS, vol. 34(1), pages 315-332, January.
    4. Rohaninejad, Mohammad & Hanzálek, Zdeněk, 2023. "Multi-level lot-sizing and job shop scheduling with lot-streaming: Reformulation and solution approaches," International Journal of Production Economics, Elsevier, vol. 263(C).
    5. Fatemi-Anaraki, Soroush & Tavakkoli-Moghaddam, Reza & Foumani, Mehdi & Vahedi-Nouri, Behdin, 2023. "Scheduling of Multi-Robot Job Shop Systems in Dynamic Environments: Mixed-Integer Linear Programming and Constraint Programming Approaches," Omega, Elsevier, vol. 115(C).
    6. Naderi, Bahman & Begen, Mehmet A. & Zaric, Gregory S. & Roshanaei, Vahid, 2023. "A novel and efficient exact technique for integrated staffing, assignment, routing, and scheduling of home care services under uncertainty," Omega, Elsevier, vol. 116(C).
    7. Simon Emde & Shohre Zehtabian & Yann Disser, 2023. "Point-to-point and milk run delivery scheduling: models, complexity results, and algorithms based on Benders decomposition," Annals of Operations Research, Springer, vol. 322(1), pages 467-496, March.
    8. Özgün Elçi & John Hooker, 2022. "Stochastic Planning and Scheduling with Logic-Based Benders Decomposition," INFORMS Journal on Computing, INFORMS, vol. 34(5), pages 2428-2442, September.
    9. Schmid, Nico André & Limère, Veronique & Raa, Birger, 2021. "Mixed model assembly line feeding with discrete location assignments and variable station space," Omega, Elsevier, vol. 102(C).
    10. Wenkang Zhang & Yufan Zheng & Rafiq Ahmad, 2023. "The integrated process planning and scheduling of flexible job-shop-type remanufacturing systems using improved artificial bee colony algorithm," Journal of Intelligent Manufacturing, Springer, vol. 34(7), pages 2963-2988, October.
    11. Diarmuid Grimes & Emmanuel Hebrard, 2015. "Solving Variants of the Job Shop Scheduling Problem Through Conflict-Directed Search," INFORMS Journal on Computing, INFORMS, vol. 27(2), pages 268-284, May.
    12. Jin Huang & Liangliang Jin & Chaoyong Zhang, 2017. "Mathematical Modeling and a Hybrid NSGA-II Algorithm for Process Planning Problem Considering Machining Cost and Carbon Emission," Sustainability, MDPI, vol. 9(10), pages 1-18, September.
    13. Rahmati, Reza & Neghabi, Hossein & Bashiri, Mahdi & Salari, Majid, 2023. "Stochastic regional-based profit-maximizing hub location problem: A sustainable overview," Omega, Elsevier, vol. 121(C).
    14. Rahmaniani, Ragheb & Crainic, Teodor Gabriel & Gendreau, Michel & Rei, Walter, 2017. "The Benders decomposition algorithm: A literature review," European Journal of Operational Research, Elsevier, vol. 259(3), pages 801-817.
    15. Teodor Gabriel Crainic & Mike Hewitt & Francesca Maggioni & Walter Rei, 2021. "Partial Benders Decomposition: General Methodology and Application to Stochastic Network Design," Transportation Science, INFORMS, vol. 55(2), pages 414-435, March.
    16. Bahman Naderi & Rubén Ruiz & Vahid Roshanaei, 2023. "Mixed-Integer Programming vs. Constraint Programming for Shop Scheduling Problems: New Results and Outlook," INFORMS Journal on Computing, INFORMS, vol. 35(4), pages 817-843, July.
    17. Polyakovskiy, Sergey & M’Hallah, Rym, 2021. "Just-in-time two-dimensional bin packing," Omega, Elsevier, vol. 102(C).
    18. Tapia-Ubeda, Francisco J. & Miranda, Pablo A. & Macchi, Marco, 2018. "A Generalized Benders Decomposition based algorithm for an inventory location problem with stochastic inventory capacity constraints," European Journal of Operational Research, Elsevier, vol. 267(3), pages 806-817.
    19. Bahman Naderi & Kannan Govindan & Hamed Soleimani, 2020. "A Benders decomposition approach for a real case supply chain network design with capacity acquisition and transporter planning: wheat distribution network," Annals of Operations Research, Springer, vol. 291(1), pages 685-705, August.
    20. Roshanaei, Vahid & Luong, Curtiss & Aleman, Dionne M. & Urbach, David R., 2020. "Reformulation, linearization, and decomposition techniques for balanced distributed operating room scheduling," Omega, Elsevier, vol. 93(C).

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:eee:jomega:v:117:y:2023:i:c:s0305048322002298. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Catherine Liu (email available below). General contact details of provider: http://www.elsevier.com/wps/find/journaldescription.cws_home/375/description#description .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.