Scheduling jobs and maintenance activities subject to job-dependent machine deteriorations. (English) Zbl 1373.90058
Summary: This paper considers machine scheduling that integrates machine deterioration caused by jobs and, consequently, maintenance activities. The maintenance state of the machine is represented by a maintenance level which drops by a certain, possibly job-dependent amount while jobs are processed. A maintenance level of less than zero is associated with the machine’s breakdown and is therefore forbidden. Hence, maintenance activities that raise the maintenance level may become necessary and have to be scheduled additionally. We consider the objective to minimize the makespan throughout the paper. For the single machine case, we provide a linear-time approximation algorithm with worst-case a bound of 5/4, and comment on how an FPTAS from previous literature can be employed to apply to our problem. Due to problem similarity, these results also apply to the minimum subset sum problem, and the 5/4 linear-time approximation algorithm is an improvement over the 5/4 quadratic-time approximation algorithm of
Güntzer and Jungnickel. For the general problem with multiple machines, we provide approximability results, two fast heuristics, an approximation algorithm with an instance-dependent approximation factor and a computational study evaluating the heuristics.
MSC:
| 90B35 | Deterministic scheduling theory in operations research |
| 68M20 | Performance evaluation, queueing, and scheduling in the context of computer systems |
| 90C59 | Approximation methods and heuristics in mathematical programming |
| 90B25 | Reliability, availability, maintenance, inspection in operations research |
Keywords:
parallel machines; maintenance; makespan; approximation algorithms; heuristics; minimum subset sumReferences:
| [1] | Bock, S., Briskorn, D., & Horbach, A. (2012). Scheduling flexible maintenance activities subject to job-dependent machine deterioration. Journal of Scheduling, 15(5), 565-578. · Zbl 1280.90031 · doi:10.1007/s10951-011-0248-7 |
| [2] | Brucker, P. (2004). Scheduling Algorithms. Berlin: Springer. · Zbl 1060.90034 · doi:10.1007/978-3-540-24804-0 |
| [3] | Chen, B. (1991). Tighter bound for MULTIFIT scheduling on uniform processors. Discrete Applied Mathematics, 31, 227-260. · Zbl 0738.68010 · doi:10.1016/0166-218X(91)90053-Y |
| [4] | Chen, J.-S. (2008). Scheduling of nonresumable jobs and flexible maintenance activities on a single machine to minimize makespan. European Journal of Operational Research, 190, 90-102. · Zbl 1146.90028 · doi:10.1016/j.ejor.2007.06.029 |
| [5] | Coffman, E. G., Garey, M. R., & Johnson, D. S. (1978). An application of bin-packing to multiprocessor scheduling. SIAM Journal on Computing, 7, 1-17. · Zbl 0374.68032 · doi:10.1137/0207001 |
| [6] | Friesen, D., & Langston, M. (1983). Bounds for multifit scheduling on uniform processors. SIAM Journal on Computing, 12, 60-69. · Zbl 0514.68048 · doi:10.1137/0212004 |
| [7] | Garey, M. R., & Johnson, D. S. (1979). Computers and Intractability - A guide to the theory of NP-completeness. New York: W.H Freemand and Company. · Zbl 0411.68039 |
| [8] | Gens, G., & Levner, E. (1981). Fast approximation algorithm for job sequencing with deadlines. Discrete Applied Mathematics, 3, 313-318. · Zbl 0464.90035 · doi:10.1016/0166-218X(81)90008-1 |
| [9] | Graham, R. L., Lawler, E. L., Lenstra, J. K., & Kan, A. G. H. R. (1979). Optimisation and approximation in deterministic sequencing and scheduling: A survey. Annals of Discrete Mathematics, 5, 236-287. · Zbl 0411.90044 |
| [10] | Grigoriu, L., & Friesen, D. K. (2010). Scheduling on same-speed processors with at most one downtime on each machine. Discrete Optimization, 7, 212-221. · Zbl 1241.90047 · doi:10.1016/j.disopt.2010.04.003 |
| [11] | Güntzer, M., & Jungnickel, D. (2000). Approximate minimization algorithms for the 0/1 knapsack and subset-sum problem. Operations Research Letters, 26, 55-66. · Zbl 0946.90051 · doi:10.1016/S0167-6377(99)00066-8 |
| [12] | Hochbaum, D. S., & Shmoys, D. B. (1987). Using dual approximation algorithms for scheduling problems theoretical and practical results. Journal of the ACM, 34(1), 144-162. · doi:10.1145/7531.7535 |
| [13] | Janiak, A., & Kovalyov, M. (1996). Single machine scheduling subject to deadlines and resource dependent processing times. European Journal of Operational Research, 94, 284-291. · Zbl 0947.90584 · doi:10.1016/0377-2217(96)00129-4 |
| [14] | Kellerer, H., Mansini, R., & Speranza, M. (2000). Two linear approximation algorithms for the subset-sum problem. European Journal of Operational Research, 120, 289-296. · Zbl 0955.90150 · doi:10.1016/S0377-2217(99)00157-5 |
| [15] | Kellerer, H., Pferschy, U., & Pisinger, D. (2004). Knapsack Problems. Berlin: Springer. · Zbl 1103.90003 · doi:10.1007/978-3-540-24777-7 |
| [16] | Kovalyov, M. (1996). A rounding technique to construct approximation algorithms for knapsack and partition type problems. Applied Mathematics and Computer Science, 6, 101-113. |
| [17] | Lee, C.-Y. (2004). Machine scheduling with availability constraints. In: J. Y.-T. Leung (Eds.), Handbook of scheduling: Algorithms, models and performance analysis (pp. 22-1-22-13). Boca Raton, FL: Chapman and Hall/CRC. · Zbl 1103.90002 |
| [18] | Lodree, E. J, Jr., & Geiger, C. D. (2010). A note on the optimal sequence position for a rate-modifying activity under simple linear deterioration. European Journal of Operational Research, 201, 644-648. · Zbl 1192.90076 · doi:10.1016/j.ejor.2009.03.027 |
| [19] | Mor, B., & Mosheiov, G. (2012). Scheduling a maintenance activity and due-window assignment based on common flow allowance. International Journal of Production Economics, 135, 222-230. · doi:10.1016/j.ijpe.2011.07.013 |
| [20] | Mosheiov, G., & Sarig, A. (2009). Scheduling a maintenance activity and due-window assignment on a single machine. Computers & Operations Research, 36, 2541-2545. · Zbl 1179.90146 · doi:10.1016/j.cor.2008.10.007 |
| [21] | Pinedo, M. (2012). Scheduling: Theory, Algorithms, and Systems. Berlin: Springer. · Zbl 1239.90002 · doi:10.1007/978-1-4614-2361-4 |
| [22] | Rustogi, K., & Strusevich, V. A. (2012a). Single machine scheduling with general positional deterioration and rate-modifying maintenance. Omega, 40, 791-804. · doi:10.1016/j.omega.2011.12.007 |
| [23] | Rustogi, K., & Strusevich, V. A. (2012b). Simple matching vs linear assignment in scheduling models with positional effects: A critical review. European Journal of Operational Research, 222, 393-407. · Zbl 1253.90117 · doi:10.1016/j.ejor.2012.04.037 |
| [24] | Rustogi, K., & Strusevich, V. A. (2014). Combining time and position dependent effects on a single machine subject to rate-modifying activities. Omega, 42, 166-178. · doi:10.1016/j.omega.2013.05.005 |
| [25] | Shabtay, D., & Steiner, G. (2007). A survey of scheduling with controllable processing times. Discrete Applied Mathematics, 155, 1643-1666. · Zbl 1119.90022 · doi:10.1016/j.dam.2007.02.003 |
| [26] | Sun, K., & Li, H. (2010). Scheduling problems with multiple maintenance activities and non-preemptive jobs on two identical parallel machines. International Journal of Production Economics, 124, 151-158. · Zbl 1280.90031 |
| [27] | Yang, D.-L., & Yang, S.-J. (2013). Unrelated parallel-machine scheduling problems with multiple rate-modifying activities. Information Sciences, 235, 280-286. · Zbl 1284.90027 · doi:10.1016/j.ins.2013.02.013 |
| [28] | Yang, D.-L., Cheng, T. C. E., & Yang, S.-J. (2014). Parallel-machine scheduling with controllable processing times and rate-modifying activities to minimise total cost involving total completion time and job compressions. International Journal of Production Research, 52, 1133-1141. · doi:10.1080/00207543.2013.841330 |
| [29] | Yang, S.-J. (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, 3321-3329. · Zbl 1202.90149 · doi:10.1016/j.amc.2010.08.064 |
| [30] | Yang, S.-J., & Yang, D.-L. (2010a). Minimizing the makespan on single-machine scheduling with aging effect and variable maintenance activities. Omega, 38, 528-533. · doi:10.1016/j.omega.2010.01.003 |
| [31] | Yang, S.-J., & Yang, D.-L. (2010b). Minimizing the total completion time in single-machine scheduling with aging/deteriorating effects and deteriorating maintenance activities. Computers and Mathematics with Applications, 60, 2161-2169. · Zbl 1205.90141 · doi:10.1016/j.camwa.2010.08.003 |
| [32] | Yue, M. (1990). On the exact upper bound of the multifit processor scheduling algorithm. Annals of Operations Research, 24, 233-259. · Zbl 0708.90042 · doi:10.1007/BF02216826 |
| [33] | Zhao, C.-L., & Tang, H.-Y. (2010). Single machine scheduling with general job-dependent aging effect and maintenance activities to minimize makespan. Applied Mathematical Modelling, 34, 837-841. · Zbl 1185.90106 · doi:10.1016/j.apm.2009.07.002 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
