A Time Indexed Formulation of Nonpreemptive Single-machine Scheduling Problems

Sousa, JP.;Wolsey, Laurence
(1992) Mathematical Programming — Vol. 54, n° 3, p. 353-367 (1992)

Files

pdfdocument.pdf
  • Restricted Access
  • Adobe PDF
  • 833.3 KB
Request a copy

Details

Authors
  • Sousa, JP.
    Author
  • Wolsey, LaurenceUCLouvain
    Author
Abstract
We consider the formulation of non-preemptive single machine scheduling problems using time-indexed variables. This approach leads to verv large models, but gives better lower bounds than other mixed integer programming formulations. We derive a variety of valid inequalities, and show the role of constraint aggregation and the knapsack problem with generalised upper bound constraints as a way of generating such inequalities. A cutting plane/branch-and-bound algorithm based on these inequalities has been implemented. Computational experience on small problems with 20/30 jobs and various constraints and objective functions is presented.
Affiliations

Citations

  • APA
  • Chicago
  • FWB

Sousa, JP., & Wolsey, L. (1992). A Time Indexed Formulation of Nonpreemptive Single-machine Scheduling Problems. Mathematical Programming, 54(3), 353-367. https://doi.org/10.1007/BF01586059 (Original work published 1992)