A Branch-and-Price Algorithm for Parallel Machine Scheduling Using ZDDs and Generic Branching

References

• Agarwal Y, Mathur K, Salkin H (1989) A set-partitioning-based exact algorithm for the vehicle routing problem. Networks 19(7):731–749.Crossref, Google Scholar
• Akers S (1978) Binary decision diagrams. IEEE Trans. Comput. 100(6):509–516.Crossref, Google Scholar
• Azizoglu M, Kirca O (1999) On the minimization of total weighted flow time with identical and uniform parallel machines. Eur. J. Oper. Res. 113(1):91–100.Crossref, Google Scholar
• Belouadah H, Potts C (1994) Scheduling identical parallel machines to minimize total weighted completion time. Discrete Appl. Math. 48(3):201–218.Crossref, Google Scholar
• Ben-Ameur W, Neto J (2007) Acceleration of cutting-plane and column generation algorithms: Applications to network design. Networks 49(1):3–17.Crossref, Google Scholar
• Bergman D, Cire A, van Hoeve WJ, Hooker J (2016) Discrete optimization with decision diagrams. INFORMS J. Comput. 28(1):47–66.Link, Google Scholar
• Bigras LP, Gamache M, Savard G (2008) Time-indexed formulations and the total weighted tardiness problem. INFORMS J. Comput. 20(1):133–142.Link, Google Scholar
• Bruno J, Coffman EJ, Sethi R (1974) Scheduling independent tasks to reduce mean finishing time. Comm. ACM 17(7):382–387.Crossref, Google Scholar
• Bülbül K, Şen H (2017) An exact extended formulation for the unrelated parallel machine total weighted completion time problem. J. Scheduling 20(4):373–389.Crossref, Google Scholar
• Chen ZL, Powell W (1999) Solving parallel machine scheduling problems by column generation. INFORMS J. Comput. 11(1):78–94.Link, Google Scholar
• Cire A, van Hoeve WJ (2013) Multivalued decision diagrams for sequencing problems. Oper. Res. 61(6):1411–1428.Link, Google Scholar
• Dyer M, Wolsey L (1990) Formulating the single machine sequencing problem with release dates as a mixed integer program. Discrete Appl. Math. 26(2):255–270.Crossref, Google Scholar
• Elmaghraby S, Park S (1974) Scheduling jobs on a number of identical machines. AIIE Trans. 6(1):1–13.Crossref, Google Scholar
• Fukasawa R, Longo H, Lysgaard J, de Aragão M, Reis M, Uchoa E, Werneck R (2006) Robust branch-and-cut-and-price for the capacitated vehicle routing problem. Math. Programming 106(3):491–511.Crossref, Google Scholar
• Held S, Cook W, Sewell E (2012) Maximum-weight stable sets and safe lower bounds for graph coloring. Math. Programming Comput. 4(4):363–381.Crossref, Google Scholar
• Hooker J (2013) Decision diagrams and dynamic programming. Gomes C, Sellmann M, eds. Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems (Springer, Berlin), 94–110.Google Scholar
• Iwashita H, Minato SI (2013) Efficient top-down ZDD construction techniques using recursive specifications. Technical Report TCS-TR-A-13-69, Graduate School of Information Science and Technology, Hokkaido University, Sapporo, Japan.Google Scholar
• Knuth DE (2011) The Art of Computer Programming, Volume 4A: Combinatorial Algorithms, Part 1 (Addison-Wesley, Upper Saddle River, NJ).Google Scholar
• Lawler E, Moore J (1969) A functional equation and its application to resource allocation and sequencing problems. Management Sci. 16(1):77–84.Link, Google Scholar
• Lee CY (1959) Representation of switching circuits by binary-decision programs. Bell System Tech. J. 38(4):985–999.Crossref, Google Scholar
• Lee CY, Uzsoy R (1992) A new dynamic programming algorithm for the parallel machines total weighted completion time problem. Oper. Res. Lett. 11(2):73–75.Crossref, Google Scholar
• Lenstra J, Rinnooy Kan A, Brucker P (1977) Complexity of machine scheduling problems. Ann. Discrete Math. 1:343–362.Crossref, Google Scholar
• Lopes M, de Carvalho J (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
• Mehrotra A, Trick M (1996) A column generation approach for graph coloring. INFORMS J. Comput. 8(4):344–354.Link, Google Scholar
• Minato SI (1993) Zero-suppressed BDDs for set manipulation in combinatorial problems. Proc. 30th Internat. Design Automation Conf. (Association for Computing Machinery, New York), 272–277.Crossref, Google Scholar
• Morrison D, Sewell E, Jacobson S (2016a) Solving the pricing problem in a branch-and-price algorithm for graph coloring using zero-suppressed binary decision diagrams. INFORMS J. Comput. 28(1):67–82.Link, Google Scholar
• Morrison D, Jacobson S, Sauppe J, Sewell E (2016b) Branch-and-bound algorithms: A survey of recent advances in searching, branching, and pruning. Discrete Optim. 19:79–102.Crossref, Google Scholar
• Pessoa A, Sadykov R, Uchoa E, Vanderbeck F (2015) Automation and combination of linear-programming based stabilization techniques in column generation. INFORMS J. Comput. 30(2):339–360.Link, Google Scholar
• Pessoa A, Uchoa E, de Aragão M, Rodrigues R (2010) Exact algorithm over an arc-time-indexed formulation for parallel machine scheduling problems. Math. Programming Comput. 2(3–4):259–290.Crossref, Google Scholar
• Rothkopf M (1966) Scheduling independent tasks on parallel processors. Management Sci. 12(5):437–447.Link, Google Scholar
• Ryan D, Foster B (1981) An integer programming approach to scheduling. Wren A, ed. Computer Scheduling of Public Transport: Urban Passenger Vehicle and Crew Scheduling (North-Holland, Amsterdam), 269–280.Google Scholar
• Sadykov R, Vanderbeck F (2013) Column generation for extended formulations. EURO J. Computational Optim. 1(1–2):81–115.Crossref, Google Scholar
• Smith W (1956) Various optimizers for single-stage production. Naval Res. Logist. Quart. 3(1–2):59–66.Crossref, Google Scholar
• van den Akker J, Hoogeveen J, van de Velde S (1999) Parallel machine scheduling by column generation. Oper. Res. 47(6):862–872.Link, Google Scholar
• van den Akker J, Hoogeveen H, van de Velde S (2002) Combining column generation and Lagrangean relaxation to solve a single-machine common due date problem. INFORMS J. Comput. 14(1):37–51.Link, Google Scholar
• van den Akker J, Hurkens C, Savelsbergh M (2000) Time-indexed formulations for machine scheduling problems: Column generation. INFORMS J. Comput. 12(2):111–124.Link, Google Scholar
• Vance P, Barnhart C, Johnson E, Nemhauser G (1994) Solving binary cutting stock problems by column generation and branch-and-bound. Comput. Optim. Appl. 3(2):111–130.Crossref, Google Scholar
• Webster S (1992) New bounds for the identical parallel processor weighted flow time problem. Management Sci. 38(1):124–136.Link, Google Scholar
• Wentges P (1997) Weighted Dantzig–Wolfe decomposition for linear mixed-integer programming. Internat. Trans. Oper. Res. 4(2):151–162.Crossref, Google Scholar