Scheduling problems with controllable processing times

In traditional deterministic scheduling research it is usually assumed that processing times of the jobs are fixed. As a rule, a typical scheduling decision reduces to pure sequencing: finding an optimal job order for each machine. Recent trends in scheduling theory involve extending scheduling models to include more practical constraints. In particular, in many real-life situations, the data may vary and can be controlled. Scheduling decisions often combine job sequencing with finding the optimal regimes of processing the jobs. Depending on the selected regimes, some jobs can be completed earlier but this usually incurs additional costs.

The first part of this talk will present the properties of the model with controllable processing times and formulate a unified framework to tackle various types of problems. The approach is based on reducing the scheduling problems to optimising a cost function over a special polyhedron known as a polymatroid. Due to the classical combinatorial optimisation results known for polymatroids, this class of problems can be solved by the well-known greedy approach.

The second part of the talk will illustrate the applicability of this approach to a range of single-machine and parallel-machine problems. Implementation details will be discussed and it will be demonstrated that the suggested approach provides faster and simpler algorithms that outperform the known algorithms in terms of the running time.

B.Hammer