A TIME INDEXED FORMULATION OF NONPREEMPTIVE SINGLE-MACHINE SCHEDULING PROBLEMS

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.