A Flow-Based Formulation for Parallel Machine Scheduling Using Decision Diagrams

References

• Ahuja RK, Magnanti TL, Orlin JB (1993) Network Flows: Theory, Algorithms, and Applications (Prentice-Hall, Upper Saddle River, NJ).Google Scholar
• Akers SB (1978) Binary decision diagrams. IEEE Trans. Comput. 100:509–516.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. Programming 115:351–385.Crossref, Google Scholar
• Baldacci R, Mingozzi A, Roberti R (2011) New route relaxation and pricing strategies for the vehicle routing problem. Oper. Res. 59:1269–1283.Link, Google Scholar
• Baptiste P, Sadykov R (2009) On scheduling a single machine to minimize a piecewise linear objective function: A compact MIP formulation. Naval Res. Logist. 56:487–502.Crossref, Google Scholar
• Bergman D, Cire AA, van Hoeve WJ, Hooker JN (2016) Discrete optimization with decision diagrams. INFORMS J. Comput. 28: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:133–142.Link, Google Scholar
• Boland N, Clement R, Waterer H (2016) A bucket indexed formulation for nonpreemptive single machine scheduling problems. INFORMS J. Comput. 28:14–30.Link, Google Scholar
• Castro MP, Cire AA, Beck JC (2022) Decision diagrams for discrete optimization: A survey of recent advances. INFORMS J. Comput. 34:2271–2295.Link, Google Scholar
• Cire AA, van Hoeve W-J (2013) Multivalued decision diagrams for sequencing problems. Oper. Res. 61:1411–1428.Link, Google Scholar
• Clement R (2015) Mixed integer linear programming models for machine scheduling. PhD thesis, University of Newcastle, Newcastle, Australia.Google Scholar
• Crama Y, Spieksma FCR (1996) Scheduling jobs of equal length: Complexity, facets and computational results. Math. Programming 72:207–227.Crossref, Google Scholar
• Dolan ED, Moré JJ (2002) Benchmarking optimization software with performance profiles. Math. Programming 91:201–213.Crossref, Google Scholar
• Dyer ME, Wolsey LA (1990) Formulating the single machine sequencing problem with release dates as a mixed integer program. Discrete Appl. Math. 26:255–270.Crossref, Google Scholar
• Fukasawa R, Longo H, Lysgaard J, Poggi de Aragão M, Reis M, Uchoa E, Werneck RF (2006) Robust branch-and-cut-and-price for the capacitated vehicle routing problem. Math. Programming 106:491–511.Crossref, Google Scholar
• Houck DJ Jr, Picard JC, Queyranne M, Vemuganti RR (1978) Traveling salesman problem as a constrained shortest path problem: Theory and computational experience. Technical report, Ecole Polytechnique de Montréal, Montreal.Google Scholar
• Irnich S, Villeneuve D (2006) The shortest-path problem with resource constraints and k-cycle elimination for k ≥ 3. INFORMS J. Comput. 18:391–406.Link, Google Scholar
• Irnich S, Desaulniers G, Desrosiers J, Hadjar A (2010) Path-reduced costs for eliminating arcs in routing and scheduling. INFORMS J. Comput. 22:297–313.Link, Google Scholar
• Iwashita H, Minato SI (2013) Efficient top-down ZDD construction techniques using recursive specifications. Technical report, Graduate School of Information Science and Technology, Hokkaido University, Hokkaido, Japan.Google Scholar
• Kowalczyk D, Leus R, Hojny C, Røpke S (2024) A flow-based formulation for parallel machine scheduling using decision diagrams. URL https://dx.doi.org/10.1287/ijoc.2022.0301.cd, https://github.com/INFORMSJoC/2022.0301.Google Scholar
• Kramer A, Subramanian A (2019) A unified heuristic and an annotated bibliography for a large class of earliness–tardiness scheduling problems. J. Scheduling 22:21–57.Crossref, Google Scholar
• Lawler EL (1977) A “pseudopolynomial” algorithm for sequencing jobs to minimize total tardiness. Annals Discrete Math. 1:331–342.Crossref, Google Scholar
• Lee CY (1959) Representation of switching circuits by binary-decision programs. Bell Systems Tech. J. 38:985–999.Crossref, Google Scholar
• Linderoth JT, Savelsbergh MWP (1999) A computational study of search strategies for mixed integer programming. INFORMS J. Comput. 11:173–187.Link, Google Scholar
• Minato SI (1993) Zero-suppressed BDDs for set manipulation in combinatorial problems. Proc. 30th Internat. Design Automation Conf. (ACM, New York), 272–277.Google Scholar
• Oliveira D, Pessoa A (2020) An improved branch-cut-and-price algorithm for parallel machine scheduling problems. INFORMS J. Comput. 32:90–100.Link, Google Scholar
• Pan Y, Shi L (2007) On the equivalence of the max-min transportation lower bound and the time-indexed lower bound for single-machine scheduling problems. Math. Programming 110:543–559.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:339–360.Link, Google Scholar
• Pessoa A, Uchoa E, Poggi de Aragão M, Rodrigues R (2010) Exact algorithm over an arc-time-indexed formulation for parallel machine scheduling problems. Math. Programming Comput. 2:259–290.Crossref, Google Scholar
• Poggi de Aragão M, Uchoa E (2003) Integer program reformulation for robust branch-and-cut-and-price algorithms. Proc. Math. Programming Rio Conf. Honour Nelson Maculan, 56–61.Google Scholar
• Potts CN, Van Wassenhove LN (1985) A branch and bound algorithm for the total weighted tardiness problem. Oper. Res. 33:363–377.Link, Google Scholar
• Queyranne M, Schulz AS (1994) Polyhedral approaches to machine scheduling. Technical report, Technical University of Berlin, Berlin.Google Scholar
• Sadykov R, Vanderbeck F (2013) Column generation for extended formulations. EURO J. Comput. Optim. 1:81–115.Crossref, Google Scholar
• Sourd F (2009) New exact algorithms for one-machine earliness-tardiness scheduling. INFORMS J. Comput. 21:167–175.Link, Google Scholar
• Sousa JP, Wolsey LA (1992) A time indexed formulation of non-preemptive single machine scheduling problems. Math. Programming 54:353–367.Crossref, Google Scholar
• Tanaka S, Fujikuma S, Araki M (2009) An exact algorithm for single-machine scheduling without machine idle time. J. Scheduling 12:575–593.Crossref, Google Scholar
• van den Akker JM, Hoogeveen JA, van de Velde SL (1999a) Parallel machine scheduling by column generation. Oper. Res. 47:862–872.Link, Google Scholar
• van den Akker JM, Hurkens CAJ, Savelsbergh MWP (2000) Time-indexed formulations for machine scheduling problems: Column generation. INFORMS J. Comput. 12:111–124.Link, Google Scholar
• van den Akker JM, Van Hoesel CPM, Savelsbergh MWP (1999b) A polyhedral approach to single-machine scheduling problems. Math. Programming 85:541–572.Crossref, Google Scholar
• van Hoeve WJ (2022) Graph coloring with decision diagrams. Math. Programming 192:631–674.Crossref, Google Scholar
• Wentges P (1997) Weighted Dantzig–Wolfe decomposition for linear mixed-integer programming. Internat. Trans. Oper. Res. 4:151–162.Crossref, Google Scholar