A Bucket Indexed Formulation for Nonpreemptive Single Machine Scheduling Problems

References

• Abdul-Razaq TS, Potts CN, Van Wassenhove LN (1990) A survey of algorithms for the single machine total weighted tardiness scheduling problem. Discrete Appl. Math. 26:235–253.Crossref, Google Scholar
• Avella P, Boccia M, D’Auria B (2005) Near-optimal solutions of large-scale single-machine scheduling problems. INFORMS J. Comput. 17:183–191.Link, Google Scholar
• Baker KR, Keller B (2010) Solving the single-machine sequencing problem using integer programming. Comput. Indust. Engrg. 59:730–735.Crossref, 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
• Beasley JE (1990) OR-Library: Distributing test problems by electronic mail. J. Oper. Res. Soc. 41:1069–1072.Crossref, Google Scholar
• Belvaux G, Wolsey LA (2000) bc—prod: A specialized branch-and-cut system for lot-sizing problems. Management Sci. 46:724–738.Link, Google Scholar
• Belvaux G, Wolsey LA (2001) Modelling practical lot-sizing problems as mixed-integer programs. Management Sci. 47:993–1007.Link, Google Scholar
• Bigras L-P, 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 (2013a) A big bucket time indexed formulation for nonpreemptive single machine scheduling problems. E-print 3773, Optimization Online, http://www.optimization-online.org/.Google Scholar
• Boland N, Clement R, Waterer H (2013b) A variable sized bucket indexed formulation for nonpreemptive single machine scheduling problems. Piantadosi J, Anderssen RS, Boland J, eds. MODSIM2013, 20th International Congress on Modelling and Simulation (Modelling and Simulation Society of Australia and New Zealand, Canberra, Australia), 3288–3294.Google Scholar
• Brucker P (1995) Scheduling Algorithms (Springer-Verlag, Berlin).Crossref, 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
• Dash S, Günlük O, Lodi A, Tramontani A (2012) A time bucket formulation for the travelling salesman problem with time windows. INFORMS J. Comput. 24:132–147.Link, 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
• Erera A, Hewitt M, Savelsbergh M, Zhang Y (2012) Improved load plan design through integer programming based local search. Transportation Sci. 47:412–427.Link, Google Scholar
• Fleischer L, Skutella M (2007) Quickest flows over time. SIAM J. Comput. 36:1600–1630.Crossref, Google Scholar
• Hall LA, Schulz AS, Shmoys DB, Wein J (1997) Scheduling to minimize average completion time: Off-line and on-line approximation algorithms. Math. Oper. Res. 22:513–544.Link, Google Scholar
• Hane CA, Barnhart C, Johnson EL, Marsten RE, Nemhauser GL, Sigismondi G (1995) The fleet assignment problem: Solving a large-scale integer program. Math. Programming 70:211–232.Crossref, Google Scholar
• Hashemi SM, Nasrabadi E (2012) On solving continuous-time dynamic network flows. J. Global Optim. 53:497–524.Crossref, Google Scholar
• IBM Corporation (2011) IBM ILOG CPLEX Optimization Studio V12.3. Accessed January 6, 2016, http://www.ibm.com/software/integration/optimization/cplex-optimization-studio/.Google Scholar
• Keha AB, Khowala K, Fowler JW (2009) Mixed integer programming formulations for single machine scheduling problems. Comput. Indust. Engrg. 56:357–367.Crossref, 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. Logistics of Production and Inventory, Handbooks in Operations Research and Management Science, Vol. 4 (North Holland, Amsterdam),445–522.Crossref, Google Scholar
• Nessah R, Kacem I (2012) Branch-and-bound method for minimizing the weighted completion time scheduling problem on a single machine with release dates. Comput. Oper. Res. 39:471–478.Crossref, Google Scholar
• Pan Y (2003) An improved branch and bound algorithm for single machine scheduling with deadlines to minimize total weighted completion time. Oper. Res. Lett. 31:492–496.Crossref, 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, 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
• Pinedo M (2002) Scheduling: Theory, Algorithms, and Systems (Prentice-Hall, Upper Saddle River, NJ).Google Scholar
• Pochet Y, Wolsey LA (2006) Production Planning by Mixed Integer Programming, Springer Series in Operations Research and Financial Engineering (Springer-Verlag, New York).Google Scholar
• Potts C, Wassenhove L (1985) A branch-and-bound algorithm for the total weighted tardiness problem. Oper. Res. 32:363–377.Link, Google Scholar
• Queyranne M, Schulz AS (1994) Polyhedral approaches to machine scheduling. Preprint 408/1994, Technische Universität Berlin, revised in June 1997.Google Scholar
• Savelsbergh MWP, Uma RN, Wein J (2005) An experimental study of LP-based approximation algorithms for scheduling problems. INFORMS J. Comput. 17:123–136.Link, 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 (2012) A dynamic-programming-based exact algorithm for general single-machine scheduling with machine idle time. J. Scheduling 15: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:575–593.Crossref, 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 S, Savelsbergh MWP (1999) A polyhedral approach to single-machine scheduling problems. Math. Programming 85:541–572.Crossref, Google Scholar
• Wang X, Regan A (2009) On the convergence of a new time window discretization method for the traveling salesman problem with time window constraints. Comput. Indust. Engrg. 56:161–164.Crossref, Google Scholar
• Waterer H (2001) Polyhedral approaches to scheduling shutdowns in production planning problems. Ph.D. thesis, Georgia Institute of Technology, Atlanta.Google Scholar
• Waterer H, Johnson EL, Nobili P, Savelsbergh MWP (2002) The relation of time indexed formulations of single machine scheduling problems to the node packing problem. Math. Programming 93:477–494.Crossref, Google Scholar