Abstract
In many real-life applications, job processing times are a function of the waiting time prior to their execution. In the most general setting, each job comprises of a basic processing time, which is independent of its start time, and a start time-dependent deterioration function. Some common examples of deteriorating systems include fire fighting, pollution containment, and medical treatments. To date, research has focused on scheduling models where the basic processing time of jobs is constant. However, job processing times are often controllable through the allocation of a limited non-renewable resource. We study a single-machine setting that combines these two models under the assumptions of general linear deterioration and convex resource functions. We develop a polynomial time solution for minimizing the makespan. For the total flowtime criterion, we compute the optimal resource allocation policy for a given job instance and show that the sequencing problem is at least as hard as the case with non-controllable jobs. We follow by discussing the properties of several special cases.
Similar content being viewed by others
References
Alidaee B and Ahmadian A (1993). Two parallel machine sequencing problems involving controllable job processing times. European Journal of Operational Research 70 (3): 335–341.
Browne S and Yechiali U (1990). Scheduling deteriorating jobs on a single processor. Operations Research 38 (3): 495–498.
Cheng TCE, Ding Q and Lin BMT (2004). A concise survey of scheduling with time-dependent processing times. European Journal of Operational Research 152 (1): 1–13.
Gupta JND and Gupta SK (1988). Single facility scheduling with nonlinear processing times. Computers & Industrial Engineering 14 (4): 387–393.
Gupta SK, Kunnathur AS and Dandanpani K (1987). Optimal repayment policies for multiple loans. Omega 15 (4): 323–330.
Janiak A (1989). Minimization of blooming mills standstills—Mathematical model, suboptimal algorithms. Mechanika 8 (2): 37–49.
Janiak A and Kovalyov MY (1996). Single machine scheduling subject to deadlines and resource dependent processing times. European Journal of Operational Research 94 (2): 284–291.
Kaspi M and Shabtay D (2003). Optimization of machining economics problem for a multi-stage transfer machine under failure, opportunistic and integrated replacement strategies. International Journal of Production Research 41 (10): 2229–2248.
Kuo W-H and Yang D-L (2008). A note on due-date assignment and single-machine scheduling with deteriorating jobs. Journal of the Operational Research Society 59 (6): 857–859.
Kuo W-H and Yang D-L (2011). A note on due-date assignment and single-machine scheduling with deteriorating jobs and learning effects. Journal of the Operational Research Society 62 (1): 206–210.
Lee CY and Lei L (2001). Multiple-project scheduling with controllable project duration and hard resource constraint: Some solvable cases. Annals of Operations Research 102 (1–4): 287–307.
Monma CL, Schrijver A, Todd MJ and Wei VK (1990). Convex resource allocation problems on directed acyclic graphs: Duality, complexity, special cases and extensions. Mathematics of Operations Research 15 (4): 736–748.
Mosheiov G (1992). V-shaped policies for scheduling deteriorating jobs. Operations Research 39 (6): 979–991.
Ng CT, Cai X, Cheng TCE and Lam SS (2005). Minimizing completion time variance with compressible processing times. Journal of Global Optimization 31 (2): 333–352.
Shabtay D (2004). Single and two-resource allocation algorithms for minimizing the maximal lateness in a single machine. Computers and Operations Research 31 (8): 1303–1315.
Shabtay D and Steiner G (2007). A survery of scheduling with controllable processing times. Discrete Applied Mathematics 155 (13): 1643–1666.
Shakhlevich NV and Strusevich VA (2006). Single machine scheduling with controllable release and processing parameters. Discrete Applied Mathematics 154 (15): 2178–2199.
Sun L-H, Sun L-Y and Wang J-B (2011). Single-machine scheduling to minimize total absolute differences in waiting times with deteriorating jobs. Journal of the Operational Research Society 62 (4): 768–775.
Vickson RG (1980). Two single machine sequencing problems involving controllable job processing times. AIIE Transactions 12 (3): 258–262.
Acknowledgements
The author is grateful to the Associate Editor and three anonymous reviewers for their valuable feedback and helpful comments. The author would also like to thank Sagit Morali for the meaningful discussions on an earlier version of the paper.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Oron, D. Scheduling controllable processing time jobs in a deteriorating environment. J Oper Res Soc 65, 49–56 (2014). https://doi.org/10.1057/jors.2013.5
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1057/jors.2013.5