Abstract
We study single machine scheduling problems with linear time-dependent deterioration effects and maintenance activities. Maintenance periods (MPs) are included into the schedule, so that the machine, that gets worse during the processing, can be restored to a better state. We deal with a job-independent version of the deterioration effects, that is, all jobs share a common deterioration rate. However, we introduce a novel extension to such models and allow the deterioration rates to change after every MP. We study several versions of this generalized problem and design a range of polynomial-time solution algorithms that enable the decision-maker to determine possible sequences of jobs and MPs in the schedule, so that the makespan objective can be minimized. We show that all problems reduce to a linear assignment problem with a product matrix and can be solved by methods very similar to those used for solving problems with positional effects.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Brucker P (2007). Scheduling Algorithms. Springer: Guildford, Surrey.
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.
Conway RW, Maxwell WL and Miller LW (1967). Theory of Scheduling. Addison-Wesley: Reading, MA.
Gawiejnowicz S (1996). A note on scheduling on a single processor with speed dependent on a number of executed jobs. Information Processing Letters 57 (6): 297–300.
Gawiejnowicz S (2008). Time-Dependent Scheduling. Springer: Berlin.
Gawiejnowicz S, Kurc W and Pankowska L (2006). Pareto and scalar bicriterion optimization in scheduling of deteriorating jobs. Computers and Operations Research 33 (3): 746–767.
Hardy GH, Littlewood JE and Polya G (1934). Inequalities. Cambridge University Press: London.
Kubzin MA and Strusevich VA (2005). Two-machine flow shop no-wait scheduling with machine maintenance. 4OR 3 (4): 303–313.
Kubzin MA and Strusevich VA (2006). Planning machine maintenance in two-machine shop scheduling. Operations Research 54 (4): 789–800.
Kuo WH and Yang DL (2007). Single machine scheduling with past-sequence-dependent setup times and learning effects. Information Processing Letters 102 (1): 22–26.
Kuo WH and Yang DL (2008). Minimizing the makespan in a single-machine scheduling problem with the cyclic process of an aging effect. Journal of the Operational Research Society 59 (3): 416–420.
Lodree Jr. EJ and Geiger CD (2010). A note on the optimal sequence position for a rate-modifying activity under simple linear deterioration. European Journal of Operational Research 201 (2): 644–648.
Okołowski D and Gawiejnowicz S (2010). Exact and heuristic algorithms for parallel-machine scheduling with DeJong's learning effect. Computers and Industrial Engineering 59 (2): 272–279.
Rustogi K and Strusevich VA (2011). Convex and V-shaped sequences of sums of functions that depend on ceiling functions. Journal of Integer Sequences 14: Article 11.1.5, http://www.cs.uwaterloo.ca/journals/JIS/VOL14/Strusevich/strusevich2.html, accessed 30 April 2013.
Rustogi K and Strusevich VA (2012a). Single machine scheduling with general positional deterioration and rate-modifying maintenance. Omega 40 (6): 791–804.
Rustogi K and Strusevich VA (2012b). Simple matching vs linear assignment in scheduling models with positional effects: A critical review. European Journal of Operational Research 222 (3): 393–407.
Rustogi K and Strusevich VA (2014). Combining time and position dependent effects on a single machine subject to rate-modifying activities. Omega 42 (1): 166–178.
Yang SJ (2010). Single-machine scheduling problems with both start-time dependent learning and position dependent aging effects under deteriorating maintenance consideration. Applied Mathematics and Computation 217 (7): 3321–3329.
Yang SJ (2012). Single-machine scheduling problems simultaneously with deterioration and learning effects under deteriorating multi-maintenance activities consideration. Computers and Industrial Engineering 62 (1): 271–275.
Yang SJ and Yang DL (2010). Minimizing the total completion time in single-machine scheduling with ageing/deteriorating effects and deteriorating maintenance activities. Computers and Mathematics with Applications 60 (7): 2161–2169.
Zhao CL and Tang HY (2010). Single machine scheduling with general job-dependent aging effect and maintenance activities to minimize makespan. Applied Mathematical Modelling 34 (3): 837–841.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Rustogi, K., Strusevich, V. Single machine scheduling with time-dependent linear deterioration and rate-modifying maintenance. J Oper Res Soc 66, 500–515 (2015). https://doi.org/10.1057/jors.2014.18
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1057/jors.2014.18