Domain-Independent Dynamic Programming and Constraint Programming Approaches for Assembly Line Balancing Problems with Setups

References

• Achterberg T (2009) SCIP: Solving constraint integer programs. Math. Programming Comput. 1(1):1–41.Crossref, Google Scholar
• Akpinar Ş, Baykasoğlu A (2014) Modeling and solving mixed-model assembly line balancing problem with setups. Part II: A multiple colony hybrid bees algorithm. J. Manufacturing Systems 33(4):445–461.Crossref, Google Scholar
• Akpinar S, Elmi A, Bektaş T (2017) Combinatorial benders cuts for assembly line balancing problems with setups. Eur. J. Oper. Res. 259(2):527–537.Crossref, Google Scholar
• Andres C, Miralles C, Pastor R (2008) Balancing and scheduling tasks in assembly lines with sequence-dependent setup times. Eur. J. Oper. Res. 187(3):1212–1223.Crossref, Google Scholar
• Becker C, Scholl A (2006) A survey on problems and methods in generalized assembly line balancing. Eur. J. Oper. Res. 168(3):694–715.Crossref, Google Scholar
• Bergman D, Cire AA, Van Hoeve WJ, Hooker J (2016) Decision Diagrams for Optimization, vol. 1 (Springer, Cham, Switzerland).Crossref, Google Scholar
• Berthold T (2013) Measuring the impact of primal heuristics. Oper. Res. Lett. 41(6):611–614.Crossref, Google Scholar
• Bockmayr A, Kasper T (1998) Branch and infer: A unifying framework for integer and finite domain constraint programming. INFORMS J. Comput. 10(3):287–300.Link, Google Scholar
• Boysen N, Schulze P, Scholl A (2022) Assembly line balancing: What happened in the last fifteen years? Eur. J. Oper. Res. 301(3):797–814.Crossref, Google Scholar
• Bukchin Y, Raviv T (2018) Constraint programming for solving various assembly line balancing problems. Omega 78:57–68.Crossref, Google Scholar
• Çil ZA, Kizilay D, Li Z, Öztop H (2022) Two-sided disassembly line balancing problem with sequence-dependent setup time: A constraint programming model and artificial bee colony algorithm. Expert Systems Appl. 203:117529.Crossref, Google Scholar
• Dooms G, Deville Y, Dupont P (2005) CP (graph): Introducing a graph computation domain in constraint programming. van Beek P, ed. Proc. 11th Internat. Conf. Principles Practice Constraint Programming (Springer, Berlin), 211–225.Google Scholar
• Esmaeilbeigi R, Naderi B, Charkhgard P (2016) New formulations for the setup assembly line balancing and scheduling problem. OR Spectrum 38:493–518.Crossref, Google Scholar
• Gillard X, Schaus P, Coppé V (2021) Ddo, a generic and efficient framework for MDD-based optimization. Bessiere C, ed. Proc. 29th Internat. Joint Conf. Artificial Intelligence (IJCAI.org), 5243–5245.Google Scholar
• Güner F, Görür AK, Satır B, Kandiller L, Drake JH (2024) A constraint programming approach to a real-world workforce scheduling problem for multi-manned assembly lines with sequence-dependent setup times. Internat. J. Production Res. 62(9):3212–3229.Crossref, Google Scholar
• Gurobi Optimization (2021) Gurobi Optimizer reference manual. Accessed March 1, 2024, https://www.gurobi.com/documentation/9.5/refman/.Google Scholar
• Hart PE, Nilsson NJ, Raphael B (1968) A formal basis for the heuristic determination of minimum cost paths. IEEE Trans. Systems Sci. Cybernetics 4(2):100–107.Crossref, Google Scholar
• Hooker JN (2002) Logic, optimization, and constraint programming. INFORMS J. Comput. 14(4):295–321.Link, Google Scholar
• Hooker JN, van Hoeve WJ (2018) Constraint programming and operations research. Constraints 23(2):172–195.Crossref, Google Scholar
• IBM (2023) IBM ILOG CPLEX CP optimizer. Accessed March 1, 2024, https://www.ibm.com/products/ilog-cplex-optimization-studio/cplex-cp-optimizer.Google Scholar
• Kizilay D (2022) A novel constraint programming and simulated annealing for disassembly line balancing problem with and/or precedence and sequence dependent setup times. Comput. Oper. Res. 146:105915.Crossref, Google Scholar
• Kumar N, Mahto D (2013) Assembly line balancing: A review of developments and trends in approach to industrial application. Global J. Res. Engrg. Indust. Engrg. 13(2):29–50.Google Scholar
• Kuroiwa R, Beck JC (2023a) Domain-independent dynamic programming: Generic state space search for combinatorial optimization. Koenig S, Stern R, Vallati M, eds. Proc. 33rd Internat. Conf. Automated Planning Scheduling (AAAI Press, Palo Alto, CA), 236–244.Google Scholar
• Kuroiwa R, Beck JC (2023b) Solving domain-independent dynamic programming problems with anytime heuristic search. Koenig S, Stern R, Vallati M, eds. Proc. 33rd Internat. Conf. Automated Planning Scheduling (AAAI Press, Palo Alto, CA), 245–253.Google Scholar
• Kuroiwa R, Beck JC (2024) Domain-independent dynamic programming. Preprint, submitted January 25, https://arxiv.org/abs/2401.13883.Google Scholar
• Laborie P, Rogerie J, Shaw P, Vilím P (2018) IBM ILOG CP optimizer for scheduling: 20+ years of scheduling with constraints at IBM/ILOG. Constraints 23:210–250.Crossref, Google Scholar
• Martino L, Pastor R (2010) Heuristic procedures for solving the general assembly line balancing problem with setups. Internat. J. Production Res. 48(6):1787–1804.Crossref, Google Scholar
• Morrison DR, Sewell EC, Jacobson SH (2014) An application of the branch, bound, and remember algorithm to a new simple assembly line balancing data set. Eur. J. Oper. Res. 236(2):403–409.Crossref, Google Scholar
• Nethercote N, Stuckey PJ, Becket R, Brand S, Duck GJ, Tack G (2007) MiniZinc: Toward a standard CP modelling language. Bessière C, ed. Proc. Internat. Conf. Principles Practice Constraint Programming (Springer, Berlin), 529–543.Google Scholar
• Özcan U (2019) Balancing and scheduling tasks in parallel assembly lines with sequence-dependent setup times. Internat. J. Production Econom. 213:81–96.Crossref, Google Scholar
• Rossi F, Van Beek P, Walsh T (2006) Handbook of Constraint Programming (Elsevier, Amsterdam).Google Scholar
• Şahin M, Kellegöz T (2017) Increasing production rate in U-type assembly lines with sequence-dependent set-up times. Engrg. Optim. 49(8):1401–1419.Crossref, Google Scholar
• Scholl A, Klein R (1997) Salome: A bidirectional branch-and-bound procedure for assembly line balancing. INFORMS J. Comput. 9(4):319–334.Link, Google Scholar
• Scholl A, Boysen N, Fliedner M (2013) The assembly line balancing and scheduling problem with sequence-dependent setup times: Problem extension, model formulation and efficient heuristics. OR Spectrum 35(1):291–320.Crossref, Google Scholar
• Seyed-Alagheband S, Ghomi SF, Zandieh M (2011) A simulated annealing algorithm for balancing the assembly line type II problem with sequence-dependent setup times between tasks. Internat. J. Production Res. 49(3):805–825.Crossref, Google Scholar
• Shapiro SC (1992) Encyclopedia of Artificial Intelligence, 2nd ed. (Wiley, Hoboken, NJ).Google Scholar
• Tang Q, Liang Y, Zhang L, Floudas CA, Cao X (2016) Balancing mixed-model assembly lines with sequence-dependent tasks via hybrid genetic algorithm. J. Global Optim. 65(1):83–107.Crossref, Google Scholar
• Wee T, Magazine MJ (1982) Assembly line balancing as generalized bin packing. Oper. Res. Lett. 1(2):56–58.Crossref, Google Scholar
• Yang W, Cheng W (2020) Modelling and solving mixed-model two-sided assembly line balancing problem with sequence-dependent setup time. Internat. J. Production Res. 58(21):6638–6659.Crossref, Google Scholar
• Yolmeh A, Kianfar F (2012) An efficient hybrid genetic algorithm to solve assembly line balancing problem with sequence-dependent setup times. Comput. Indust. Engrg. 62(4):936–945.Crossref, Google Scholar
• Zhang W (1998) Complete anytime beam search. Mostow J, Rich C, eds. Proc. AAAI Conf. Artificial Intelligence (Association for the Advancement of Artificial Intelligence, Washington, DC), 425–430.Google Scholar
• Zhang J, Beck JC (2024a) Appendix to Domain-independent dynamic programming and constraint programming approaches for assembly line balancing problems with setups. https://github.com/INFORMSJoC/2024.0603/blob/main/IJOC_SUALBP_Appendix.pdf.Google Scholar
• Zhang J, Beck JC (2024b) Domain-independent dynamic programming and constraint programming approaches for assembly line balancing problems with setups. http://dx.doi.org/10.1287/ijoc.2024.0603.cd, https://github.com/INFORMSJoC/2024.0603.Google Scholar
• Zohali H, Naderi B, Roshanaei V (2022) Solving the type-2 assembly line balancing with setups using logic-based benders decomposition. INFORMS J. Comput. 34(1):315–332.Link, Google Scholar