Weitere Artikel dieser Ausgabe durch Wischen aufrufen
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.
Bitte loggen Sie sich ein, um Zugang zu diesem Inhalt zu erhalten
Sie möchten Zugang zu diesem Inhalt erhalten? Dann informieren Sie sich jetzt über unsere Produkte:
Bock, S., Briskorn, D., & Horbach, A. (2012). Scheduling flexible maintenance activities subject to job-dependent machine deterioration. Journal of Scheduling, 15(5), 565–578. CrossRef
Brucker, P. (2004). Scheduling Algorithms. Berlin: Springer. CrossRef
Chen, B. (1991). Tighter bound for MULTIFIT scheduling on uniform processors. Discrete Applied Mathematics, 31, 227–260. CrossRef
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. CrossRef
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. CrossRef
Friesen, D., & Langston, M. (1983). Bounds for multifit scheduling on uniform processors. SIAM Journal on Computing, 12, 60–69. CrossRef
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.
Gens, G., & Levner, E. (1981). Fast approximation algorithm for job sequencing with deadlines. Discrete Applied Mathematics, 3, 313–318. CrossRef
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.
Grigoriu, L., & Friesen, D. K. (2010). Scheduling on same-speed processors with at most one downtime on each machine. Discrete Optimization, 7, 212–221. CrossRef
Güntzer, M., & Jungnickel, D. (2000). Approximate minimization algorithms for the 0/1 knapsack and subset-sum problem. Operations Research Letters, 26, 55–66. CrossRef
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. CrossRef
Janiak, A., & Kovalyov, M. (1996). Single machine scheduling subject to deadlines and resource dependent processing times. European Journal of Operational Research, 94, 284–291. CrossRef
Kellerer, H., Mansini, R., & Speranza, M. (2000). Two linear approximation algorithms for the subset-sum problem. European Journal of Operational Research, 120, 289–296. CrossRef
Kellerer, H., Pferschy, U., & Pisinger, D. (2004). Knapsack Problems. Berlin: Springer. CrossRef
Kovalyov, M. (1996). A rounding technique to construct approximation algorithms for knapsack and partition type problems. Applied Mathematics and Computer Science, 6, 101–113.
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.
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. CrossRef
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. CrossRef
Mosheiov, G., & Sarig, A. (2009). Scheduling a maintenance activity and due-window assignment on a single machine. Computers & Operations Research, 36, 2541–2545. CrossRef
Pinedo, M. (2012). Scheduling: Theory, Algorithms, and Systems. Berlin: Springer. CrossRef
Rustogi, K., & Strusevich, V. A. (2012a). Single machine scheduling with general positional deterioration and rate-modifying maintenance. Omega, 40, 791–804. CrossRef
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. CrossRef
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. CrossRef
Shabtay, D., & Steiner, G. (2007). A survey of scheduling with controllable processing times. Discrete Applied Mathematics, 155, 1643–1666. CrossRef
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.
Yang, D.-L., & Yang, S.-J. (2013). Unrelated parallel-machine scheduling problems with multiple rate-modifying activities. Information Sciences, 235, 280–286. CrossRef
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. CrossRef
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. CrossRef
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. CrossRef
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. CrossRef
Yue, M. (1990). On the exact upper bound of the multifit processor scheduling algorithm. Annals of Operations Research, 24, 233–259. CrossRef
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. CrossRef
- Scheduling jobs and maintenance activities subject to job-dependent machine deteriorations
- Springer US
Neuer Inhalt/© Stellmach, Neuer Inhalt/© Maturus, Pluta Logo/© Pluta, digitale Transformation/© Maksym Yemelyanov | Fotolia