Time-Indexed Formulations and the Total Weighted Tardiness Problem

References

• Abdul-Razaq T., Potts C., Van Wassenhove L. A survey of algorithms for the single machine total weighted tardiness scheduling problem. Discrete Appl. Math. (1990) 26:235–253Crossref, Google Scholar
• Babu P., Peridy L., Pinson E. A branch and bound algorithm to minimize total weighted tardiness on a single processor. Ann. Oper. Res. (2004) 129:33–246Crossref, Google Scholar
• Bowman E. H. The schedule-sequencing problem. Oper. Res. (1959) 7:621–624Link, Google Scholar
• Congram R. K., Potts C. N., van de Velde S. L. An iterated dynasearch algorithm for the single-machine total weighted tardiness scheduling problem. INFORMS J. Comput. (2002) 14:52–67Link, Google Scholar
• Crauwels H. A. J., Potts C. N., Van Wassenhove L. N. Local search heuristics for the single machine total weighted tardiness scheduling problem. INFORMS J. Comput. (1998) 10:341–350Link, Google Scholar
• Dantzig G. B., Wolfe P. Decomposition principle for linear programs. Oper. Res. (1960) 8:101–111Link, Google Scholar
• du Merle O., Vial J. P. Proximal ACCPM, a cutting plane method for column generation and Lagrangian relaxation: Application to the p-median problem. (2002) . Technical report, Logilab, University of Geneva, GenevaGoogle Scholar
• Dyer M. E., Wolsey L. A. Formulating the single machine sequencing problem with release dates as a mixed integer program. Discrete Appl. Math. (1990) 26:255–270Crossref, Google Scholar
• Elmaghraby S. E. The one-machine sequencing problem with delay costs. J. Indust. Engrg. (1968) 19:105–108Google Scholar
• Emmons H. One-machine sequencing to minimize certain functions of jobs tardiness. Oper. Res. (1969) 17:701–715Link, Google Scholar
• Geoffrion A. Lagrangean relaxation for integer programming. Math. Programming Stud. (1974) 2:82–114Crossref, Google Scholar
• Goemans M. X. Improved approximation algorithms for scheduling with release dates. Proc. 8th Annual ACM-SIAM Sympos. Discrete Algorithms (1997) (Society for Industrial and Applied Mathematics, Philadelphia) 591–598Google Scholar
• Hall L. A., Schultz A. S., Shmoys D. B., Wein J. Scheduling to minimize average completion time: Off line and on line approximation algorithms. Math. Oper. Res. (1997) 22:513–544Link, Google Scholar
• Irnich S., Villeneuve D. The shortest path problem with resource constraints and k-cycle elimination for k ≥ 3. Les Cahiers du GERAD (2003) . G-2003-55Google Scholar
• Jackson J. R. Scheduling a production line to minimize maximum tardiness. (1955) . Research Report 43, Management Science Research Project, University of California, Los AngelesGoogle Scholar
• Lasdon L. S.Optimization Theory for Large Systems (1970) (MacMillan, New York) Google Scholar
• Lawler E. L. A “pseudopolynomial” algorithm for sequencing jobs to minimize total tardiness. Ann. Discrete Math. (1977) 1:331–342Crossref, Google Scholar
• Lawler E. L. Efficient implementation of dynamic programming algorithms for sequencing problems. (1979) . Report BW 106, Mathematisch Centrum, AmsterdamGoogle Scholar
• Nemhauser G., Wolsey L.Integer and Combinatorial Optimization (1988) (John Wiley & Sons, New York) Crossref, Google Scholar
• Pan Y., Shi L. On the equivalence of the max-min transportation lower bound and the time-indexed lower bound for single-machine scheduling problems. Math. Programming Ser. A (2006) . ForthcomingGoogle Scholar
• Phillips C., Stein C., Wein J. Minimizing average completion time in the presence of release dates. Math. Programming (1998) 82:199–223Crossref, Google Scholar
• Potts C. N., Van Wassenhove L. A branch and bound algorithm for the total weighted tardiness problem. Oper. Res. (1985) 33:363–377Link, Google Scholar
• Rinnooy Kan A., Lageweg B., Lenstra J. Minimizing total costs in one-machine scheduling. Oper. Res. (1975) 23:908–927Link, Google Scholar
• Schrage L., Baker K. R. Dynamic programming solution of sequencing problems with precedence constraints. Oper. Res. (1978) 26:444–449Link, Google Scholar
• Schultz A. S. Polytopes and scheduling. (1996) . PhD thesis, Department of Mathematics, Technical University of Berlin, BerlinGoogle Scholar
• Shwimer J. On the N-job, one-machine, sequence-independant scheduling problem with tardiness penalties: A branch-and-bound solution. Management Sci. (1972) 18:301–313Link, Google Scholar
• Smith W. E. Various optimizers for single-stage production. Naval Res. Logist. Quart. (1956) 3:59–66Crossref, Google Scholar
• Sousa J. P., Wolsey L. A. A time indexed formulation of non-preemptive single machine scheduling problems. Math. Programming (1992) 54:353–367Crossref, Google Scholar
• van den Akker J. M., Hurkens C. A. J., Savelsbergh M. W. P. Time-indexed formulations for single-machine scheduling problems: Branch and cut. (1995) . Memorandum COSOR, 95-24, Department of Mathematics and Computing Science, Eindhoven University of Technology, Eindhoven, The NetherlandsGoogle Scholar
• van den Akker J. M., Hurkens C. A. J., Savelsbergh M. W. P. Time-indexed formulations for single-machine scheduling problems: column generation. INFORMS J. Comput. (2000) 12:111–124Link, Google Scholar
• van den Akker J. M., van Hoesel C. P. M., Savelsbergh M. W. P. A polyhedral approach to single-machine scheduling problems. Math. Programming (1999) 85:541–572Crossref, Google Scholar
• Vanderbeck F., Wolsey L. A. An exact algorithm for IP column generation. Oper. Res. Lett. (1996) 10:151–160Crossref, Google Scholar
• Villeneuve D. Un logiciel de génération de colonnes. (1999) . PhD thesis, Département de Mathématiques et de Génie Industriel, École Polytechnique de Montréal, MontréalGoogle Scholar
• Waterer H., Johnson E. L., Nobili P., Savelsbergh M. W. P. The relation of time indexed formulations of single machine scheduling problems to the node packing problem. Math. Programming (2002) 93:477–494Crossref, Google Scholar