An Exact Branch-Price-and-Cut Algorithm for the Unrelated Parallel Machine Scheduling Problem

References

• Azizoglu M, Kirca O (1999) Scheduling jobs on unrelated parallel machines to minimize regular total cost functions. IIE Trans. 31(2):153–159.Crossref, Google Scholar
• Baldacci R, Christofides N, Mingozzi A (2008) An exact algorithm for the vehicle routing problem based on the set partitioning formulation with additional cuts. Math. Program. 115(2):351–385.Crossref, Google Scholar
• Barnhart C, Johnson EL, Nemhauser GL, Savelsbergh MWP, Vance PH (1998) Branch-and-price: Column generation for solving huge integer programs. Oper. Res. 46(3):316–329. Link, Google Scholar
• Bulhões T, Sadykov R, Subramanian A, Uchoa E (2020) On the exact solution of a large class of parallel machine scheduling problems. J. Scheduling 23(4):411–429.Crossref, Google Scholar
• Che A, Zhang S, Wu X (2017) Energy-conscious unrelated parallel machine scheduling under time-of-use electricity tariffs. J. Cleaner Production 156:688–697.Crossref, Google Scholar
• Chen ZL, Powell WB (1999) Solving parallel machine scheduling problems by column generation. INFORMS J. Comput. 11(1):78–94. Link, Google Scholar
• Chen J, Chu C, Sahli A, Li K (2024) A branch-and-price algorithm for unrelated parallel machine scheduling with machine usage costs. Eur. J. Oper. Res. 316(3):856–872.Crossref, Google Scholar
• Costa L, Contardo C, Desaulniers G (2019) Exact branch-price-and-cut algorithms for vehicle routing. Transportation Sci. 53(4):946–985.Link, Google Scholar
• Desaulniers G, Gschwind T, Irnich S (2020) Variable fixing for two-arc sequences in branch-price-and-cut algorithms on path-based models. Transportation Sci. 54(5):1170–1188.Link, Google Scholar
• Desrosiers J, Lübbecke M, Desaulniers G, Gauthier J (2024) Branch-and-price. Report, Les Cahiers du GERAD ISSN 711-2440, GERAD, Montréal, Québec.Google Scholar
• Detienne B, Dauzère-Pérès S, Yugma C (2011) Scheduling jobs on parallel machines to minimize a regular step total cost function. J. Scheduling 14(6):523–538.Crossref, Google Scholar
• Dey SS, Dubey Y, Molinaro M, Shah P (2024) A theoretical and computational analysis of full strong-branching. Math. Programming 205(1–2):303–336. Crossref, Google Scholar
• Durasević M, Jakobović D (2023) Heuristic and metaheuristic methods for the parallel unrelated machines scheduling problem: A survey. Artificial Intelligence Rev. 56(4):3181–3289.Crossref, Google Scholar
• Ekici A, Elyasi M, Özener OÖ, Sarıkaya MB (2019) An application of unrelated parallel machine scheduling with sequence-dependent setups at Vestel Electronics. Comput. Oper. Res. 111:130–140. Crossref, Google Scholar
• Fukasawa R, Longo H, Lysgaard J, de Pragão MP, Reis M, Uchoa E, Werneck RF (2006) Robust branch-and-cut-and-price for the capacitated vehicle routing problem. Math. Programming 106(3):491–511. Crossref, Google Scholar
• Heath LS, Pemmaraju SV (1999) Stack and queue layouts of directed acyclic graphs: Part II. SIAM J. Comput. 28(5):1588–1626.Crossref, Google Scholar
• Iori M, Locatelli A, Locatelli M (2023) A GRASP for a real-world scheduling problem with unrelated parallel print machines and sequence-dependent setup times. Internat. J. Production Res. 61(21):7367–7385.Crossref, Google Scholar
• Jepsen M, Petersen B, Spoorendonk S, Pisinger D (2008) Subset-row inequalities applied to the vehicle-routing problem with time windows. Oper. Res. 56(2):497–511.Link, Google Scholar
• Kim YI, Kim HJ (2021) Rescheduling of unrelated parallel machines with job-dependent setup times under forecasted machine breakdown. Internat. J. Production Res. 59(17):5236–5258.Crossref, Google Scholar
• Kowalczyk D, Leus R (2018) A branch-and-price algorithm for parallel machine scheduling using ZDDs and generic branching. INFORMS J. Comput. 30(4):768–782.Link, Google Scholar
• Lawler EL, Lenstra JK, Rinnooy Kan AHG, Shmoys DB (1993) Sequencing and scheduling: Algorithms and complexity. Graves SC, Rinnooy Kan AHG, Zipkin PH, eds. Handbooks in Operations Research and Management Science (Elsevier, Amsterdam), 445–522.Google Scholar
• Li K, Zhang X, Leung JYT, Yang SL (2016) Parallel machine scheduling problems in green manufacturing industry. J. Manufacturing Systems 38:98–106.Crossref, Google Scholar
• Lin YK, Pfund ME, Fowler JW (2011) Heuristics for minimizing regular performance measures in unrelated parallel machine scheduling problems. Comput. Oper. Res. 38(6):901–916.Crossref, Google Scholar
• Lübbecke ME, Desrosiers J (2005) Selected topics in column generation. Oper. Res. 53(6):1007–1023.Link, Google Scholar
• Maecker S, Shen L, Mönch L (2023) Unrelated parallel machine scheduling with eligibility constraints and delivery times to minimize total weighted tardiness. Comput. Oper. Res. 149:105999.Crossref, Google Scholar
• Pecin D, Contardo C, Desaulniers G, Uchoa E (2017a) New enhancements for the exact solution of the vehicle routing problem with time windows. INFORMS J. Comput. 29(3):489–502.Link, Google Scholar
• Pecin D, Pessoa A, Poggi M, Uchoa E (2017b) Improved branch-cut-and-price for capacitated vehicle routing. Math. Programming Comput. 9(1):61–100. Crossref, Google Scholar
• Pereira Lopes MJ, de Carvalho JMV (2007) A branch-and-price algorithm for scheduling parallel machines with sequence dependent setup times. Eur. J. Oper. Res. 176(3):1508–1527.Crossref, Google Scholar
• Pessoa A, Sadykov R, Uchoa E, Vanderbeck F (2018) Automation and combination of linear-programming based stabilization techniques in column generation. INFORMS J. Comput. 30(2):339–360.Link, Google Scholar
• Rodriguez FJ, Lozano M, Blum C, García-Martínez C (2013) An iterated greedy algorithm for the large-scale unrelated parallel machines scheduling problem. Comput. Oper. Res. 40(7):1829–1841.Crossref, Google Scholar
• Rolim GA, Nagano MS, Prata BdA (2023) Formulations and an adaptive large neighborhood search for just-in-time scheduling of unrelated parallel machines with a common due window. Comput. Oper. Res. 153:106159.Crossref, Google Scholar
• Sadykov R, Uchoa E, Pessoa A (2021) A bucket graph-based labeling algorithm with application to vehicle routing. Transportation Sci. 55(1):4–28.Link, Google Scholar
• Sagnol G, Barner C, Borndörfer R, Grima M, Seeling M, Spies C, Wernecke K (2018) Robust allocation of operating rooms: A cutting plane approach to handle lognormal case durations. Eur. J. Oper. Res. 271(2):420–435.Crossref, Google Scholar
• Şen H, Bülbül K (2015) A Strong Preemptive Relaxation for Weighted Tardiness and Earliness/Tardiness Problems on Unrelated Parallel Machines. INFORMS Journal on Computing. 27(1):135–150. Link, Google Scholar
• Shahvari O, Logendran R, Tavana M (2022) An efficient model-based branch-and-price algorithm for unrelated-parallel machine batching and scheduling problems. J. Scheduling 25(5):589–621.Crossref, Google Scholar
• Shim SO, Kim YD (2007) Minimizing total tardiness in an unrelated parallel-machine scheduling problem. J. Oper. Res. Soc. 58(3):346–354.Crossref, Google Scholar
• Smith WE (1956) Various optimizers for single-stage production. Naval Res. Logist. 3(1–2):59–66.Crossref, Google Scholar
• Song G, Leus R (2022) Parallel machine scheduling under uncertainty: Models and exact algorithms. INFORMS J. Comput. 34(6):3059–3079.Link, Google Scholar
• Uchoa E, Pessoa A, Moreno L (2024) Optimizing with Column Generation: Advanced branch-cut-and-price algorithms (Part I). Technical Report L-2024-3, Cadernos do LOGIS-UFF, Universidade Federal Fluminense, Engenharia de Produção, Niterói, RJ, Brazil, https://optimizingwithcolumngeneration.github.io.Google Scholar
• van den Akker JM, Hoogeveen JA, van de Velde SL (1999) Parallel machine scheduling by column generation. Oper. Res. 47(6):862–872. Link, Google Scholar
• van der Aalst WMP (2016) Process Mining: Data Science in Action. 2nd ed. 2016 ed. (Springer, Berlin, Heidelberg).Crossref, Google Scholar
• Wang T, Baldacci R, Lim A, Hu Q (2018) A branch-and-price algorithm for scheduling of deteriorating jobs and flexible periodic maintenance on a single machine. Eur. J. Oper. Res. 271(3):826–838.Crossref, Google Scholar
• Xu X, Ma Y, Zhou Z, Zhao Y (2015) Customer order scheduling on unrelated parallel machines to minimize total completion time. IEEE Trans. Automation Sci. Engrg. 12(1):244–257. Crossref, Google Scholar
• Xu K, Li Y, Liu C, Liu X, Hao X, Gao J, Maropoulos PG (2020) Advanced data collection and analysis in data-driven manufacturing process. Chinese J. Mech. Engrg. 33(1):43Crossref, Google Scholar
• Yan X, Wang T, Shi X (2025) Optimal scheduling on unrelated parallel machines with combinatorial auction. Ann. Oper. Res. 344(2):937–963. Crossref, Google Scholar
• Yu Y, Li X, Baldacci R, Wu Z, Sun W, Tang J, Zhu H (2026) An exact branch-price-and-cut algorithm for the unrelated parallel machine scheduling problem. https://dx.doi.org/10.1287/ijoc.2024.0704.cd, https://github.com/INFORMSJoC/2024.0704.Google Scholar
• Zhao L, Zhu H, Zhang M, Tang J, Wang Y (2026) Large-scale dynamic surgical scheduling under uncertainty by hierarchical reinforcement learning. Internat. J. Production Res. 64(2):719–750. Crossref, Google Scholar