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

The authors develop a time-indexed formulation for the general, non- preemptive, single machine scheduling problem. The advantage of this formulation is that restrictions like dead lines and release dates can easily be included and different objective functions, like weighted completion times and weighted tardiness, can be used. On the other hand, the model is quite large, the number of variables and constraints is pseudopolynomial in the number of jobs. The authors provide valid inequalities for the formulation and present the computational results for a first implementation of a cutting plane algorithm based on these valid inequalities. Although only small problems of up to 30 jobs are used the results indicate that the solution method is efficient for this kind of single machine problems compared with a branch-and-bound solution method. It should be mentioned that due to the large model this method may only be used for very hard problems, i.e. for problems which are NP-hard in the strong sense.