Scheduling with time-of-use costs

What is it about?

We address a class of problems of scheduling a set of independent jobs onto a single machine that charges each job for its processing under variable time-of-use tariffs. Our scheduling objective is to min- imize the total cost of processing all the jobs subject to a minimum level of performance in one of the regular scheduling criteria. For each of the problems in the class, we establish its computational tractabil- ity. For those that are tractable we provide an efficient algorithm, while for those that are intractable we provide a pseudo-polynomial-time algorithm or a polynomial-time approximation scheme.

Featured Image

Why is it important?

* Detailed picture of computational tractability for the scheduling problems at hand. * Efficient algorithms for tractable problems. * A fully polynomial-time approximation scheme for an intractable problem.