Positive half-products and scheduling with controllable processing times

What is it about?

We study the single machine scheduling problem with controllable job processing times to minimize a linear combination of the total weighted job completion time and the total weighted processing time compression. We show that this scheduling problem is a positive half-product minimization problem. Positive half-products make up an interesting subclass of half-products and are introduced in this paper to provide a conceptual framework for the problem with controllable job processing times as well as other problems. This framework allows to readily derive in one fell swoop a number of results for the problem with controllable processing times from more general results obtained earlier for the half-product. We also present fast fully polynomial time approximation schemes for the problem with controllable processing times. The schemes apply to all positive half-products.

Featured Image

Why is it important?

Positive half-products make up an interesting subclass of half-products and are introduced in this paper to provide a conceptual framework for the problem with controllable job processing times as well as other problems. This framework allows to readily derive in one fell swoop a number of results for the problem with controllable processing times from more general results obtained earlier for the half-product.