A unified analysis for the single-machine scheduling problem with controllable and non-controllable variable job processing times

摘要

We present a unified analysis for single-machine scheduling problems in which the actual job processing times are controlled by either a linear or a convex resource allocation function and also vary concurrently depending on either the job's position in the sequence and/or on the total processing time of the already processed jobs. We show that the problem is solvable in O(n log n) time by using a weight-matching approach when a convex resource allocation function is in effect. In the case of a linear resource allocation function, we show that the problem can be solved in O(n(3)) time by using an assignment formulation. Our approach generalizes the solution approach for the corresponding problems with controllable job processing times to incorporate the variability of the job processing times stemming from either the job's position in the sequence and/or the total processing time of the already processed jobs.