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(nlogn) 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(n3) 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.
When requesting a correction, please mention this item's handle: RePEc:eee:ejores:v:205:y:2010:i:2:p:479-482. See general information about how to correct material in RePEc.
For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: (Zhang, Lei)
If references are entirely missing, you can add them using this form.