An Improved Branch-Cut-and-Price Algorithm for Parallel Machine Scheduling Problems

References

• Abdul-Razaq T, Potts C (1988) Dynamic programming state-space relaxation for single-machine scheduling. J. Oper. Res. Soc. 39(2):141–152.Crossref, Google Scholar
• Abdul-Razaq T, Potts CN, Van Wassenhove LN (1990) A survey of algorithms for the single machine total weighted tardiness scheduling problem. Discrete Appl. Math. 26(2):235–253.Crossref, Google Scholar
• Ibaraki T (1987) Successive sublimation methods for dynamic programming computation. Ann. Oper. Res. 11(1):397–439.Crossref, Google Scholar
• Ibaraki T, Nakamura Y (1994) A dynamic programming method for single machine scheduling. Eur. J. Oper. Res. 76(1):72–82.Crossref, Google Scholar
• Kramer A, Subramanian A (2015) A unified heuristic and an annotated bibliography for a large class of earliness-tardiness scheduling problems. Preprint arXiv:1509.02384 submitted September 8, https://arxiv.org/abs/1509.02384.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(3):543–559.Crossref, Google Scholar
• Pessoa A, Uchoa E, Poggi de Aragão M (2009) A robust branch-cut-and-price algorithm for the heterogeneous fleet vehicle routing problem. Networks. 54(4):167–177.Crossref, 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(3/4):259–290.Crossref, Google Scholar
• Potts CN, Van Wassenhove LN (1985) A branch and bound algorithm for the total weighted tardiness problem. Oper. Res. 33(2):363–377.Link, Google Scholar
• Pritsker AAB, Waiters LJ, Wolfe PM (1969) Multiproject scheduling with limited resources: A zero-one programming approach. Management Sci. 16(1):93–108.Link, Google Scholar
• Pritsker AAB, Watters LJ (1968) A zero-one programming approach to scheduling with limited resources. Research Memorandum RM-5561-PR, RAND Corporation, Santa Monica, CA.Google Scholar
• Rodrigues R, Pessoa A, Uchoa E, Poggi de Aragão M (2008) Heuristic algorithm for the parallel machine total weighted tardiness scheduling problem. Relatório Pesquisa Engenharia Produçao 8(10): Article 10.Google Scholar
• Sourd F (2009) New exact algorithms for one-machine earliness-tardiness scheduling. INFORMS J. Comput. 21(1):167–175.Link, Google Scholar
• Sousa JP, Wolsey LA (1992) A time indexed formulation of non-preemptive single machine scheduling problems. Math. Programming 54(1):353–367.Crossref, Google Scholar
• Tanaka S, Araki M (2006) A branch-and bound algorithm based on Lagrangian relaxation for single machine scheduling. Proc. Internat. Sympos. Scheduling, Tokyo, Japan, 148–153.Google Scholar
• Tanaka S, Araki M (2013) An exact algorithm for the single-machine total weighted tardiness problem with sequence-dependent setup times. Comput. Oper. Res. 40(1):344–352.Crossref, Google Scholar
• Tanaka S, Fujikuma S (2012) A dynamic-programming-based exact algorithm for general single-machine scheduling with machine idle time. J. Scheduling 15(3):347–361.Crossref, Google Scholar
• Tanaka S, Fujikuma S, Araki M (2009) An exact algorithm for single-machine scheduling without machine idle time. J. Scheduling 12(6):575–593.Crossref, Google Scholar
• Uchoa E, Fukasawa R, Lysgaard J, Pessoa A, Poggi de Aragão M, Andrade D (2008) Robust branch-cut-and-price for the capacitated minimum spanning tree problem over a large extended formulation. Math. Programming 112(2):443–472.Crossref, Google Scholar
• Van den Akker J, Hurkens CA, Savelsbergh MW (2000) Time-indexed formulations for machine scheduling problems: Column generation. INFORMS J. Comput. 12(2):111–124.Link, Google Scholar
• Van den Akker J, Van Hoesel C, Savelsbergh MW (1999) A polyhedral approach to single-machine scheduling problems. Math. Programming 85(3):541–572.Crossref, Google Scholar