A time indexed formulation of non-preemptive single machine scheduling problems

The authors consider the formulation of non-preemptive single machine scheduling problems using time-indexed variables. This approach leads to very large models, but gives better lower bounds than other mixed integer programming formulations. The authors derive a variety of valid inequalities, and show the role of constraint aggregation and the knapsack problem with generalized 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.