Equivalence of some different maintenance activities in single-machine scheduling. (English) Zbl 1424.90094
Summary: We study single-machine scheduling problems with a single maintenance activity (MA) of length \(p_0\) under three types of assumptions: (A) the MA is required in a fixed time interval \([T-p_0, T]\) with \(T\geqslant p_0\) and the job processing is of preemptive and resumable; (B) the MA is required in a relaxed time interval \([0, T]\) with \(T\geqslant p_0\) and the job processing is of nonpreemptive; (C) the MA is required in a relaxed time interval \([T_0, T]\) with \(0\leqslant T_0\leqslant T-p_0\) and the job processing is of nonpreemptive. We show in this paper that, up to the time complexity for solving scheduling problems, assumptions (A) and (B) are equivalent, and moreover, if \(T-(T_0+p_0)\) is greater than or equal to the maximum processing time of all jobs, the assumption (C) is also equivalent to (A) and (B). As an application, we study the scheduling for minimizing the weighted number of tardy jobs under the above three assumptions, respectively, and present corresponding time-complexity results.
MSC:
| 90B35 | Deterministic scheduling theory in operations research |
| 90C39 | Dynamic programming |
| 90B25 | Reliability, availability, maintenance, inspection in operations research |
References:
| [1] | Lee, C.Y.: Machine scheduling with an availability constraints. J. Glob. Optim. 9, 363-382 (1996) · Zbl 0870.90071 · doi:10.1007/BF00121681 |
| [2] | Kacem, I.: Approximation algorithms for the makespan minimization with positive tails on a single machine with a fixed nonavailability interval. J. Comb. Optim. 17, 117-133 (2009) · Zbl 1170.90393 · doi:10.1007/s10878-007-9102-4 |
| [3] | Ibarra, O., Kim, C.E.: Fast approximation algorithms for the knapsack and sum of subset problems. J. Assoc. Comput. Mach. 22, 463-468 (1975) · Zbl 0345.90049 · doi:10.1145/321906.321909 |
| [4] | Yuan, J.J., Qi, X.L., Lu, L.F., Li, W.H.: Single machine unbounded parallel-batch scheduling with forbidden intervals. Eur. J. Oper. Res. 186, 1212-1217 (2008) · Zbl 1146.90428 · doi:10.1016/j.ejor.2007.02.051 |
| [5] | Mosheiov, G., Sarig, A.: Scheduling a maintenance activity to minimize total weighted completion-time. Comput. Math. Appl. 57, 619-623 (2009) · Zbl 1165.90465 · doi:10.1016/j.camwa.2008.11.008 |
| [6] | Yang, D.L., Hung, C.L., Hsu, C.J., Chern, M.S.: Minimizing the makespan in a single machine scheduling problem with a flexible maintenance. J. Chin. Inst. Ind. Eng. 19, 63-66 (2002) |
| [7] | Yang, S.L., Ma, Y., Xu, D.L., Yang, J.B.: Minimizing total completion time on a single machine with a flexible maintenance activity. Comput. Oper. Res. 38, 755-770 (2011) · Zbl 1202.90148 · doi:10.1016/j.cor.2010.09.003 |
| [8] | Chen, J.S.: Optimization models for the machine scheduling problem with a single flexible maintenance activity. Eng. Optim. 38, 53-71 (2006) · doi:10.1080/03052150500270594 |
| [9] | Chen, W.J.: Minimizing number of tardy jobs on a single machine subject to periodic maintenance. Omega. 37, 591-599 (2009) · doi:10.1016/j.omega.2008.01.001 |
| [10] | Cui, W.W., Lu, Z.Q.: Minimizing the makespan on a single machine with flexible maintenances and jobs’ release dates. Comput. Oper. Res. 80, 11-22 (2017) · Zbl 1391.90204 · doi:10.1016/j.cor.2016.11.008 |
| [11] | Lee, J.Y., Kim, Y.D.: Minimizing the number of tardy jobs in a single-machine scheduling problem with periodic maintenance. Comput. Oper. Res. 39, 2196-2205 (2012) · Zbl 1251.90162 · doi:10.1016/j.cor.2011.11.002 |
| [12] | Liu, M., Wang, S., Chu, C., Chu, F.: An improved exact algorithm for single-machine scheduling to minimise the number of tardy jobs with periodic maintenance. Int. J. Prod. Res. 54, 1-12 (2016) · doi:10.1080/00207543.2015.1114186 |
| [13] | Sbihi, M., Varnier, C.: Single-machine scheduling with periodic and flexible periodic maintenance to minimize maximum tardiness. Comput. Ind. Eng. 55, 830-840 (2008) · doi:10.1016/j.cie.2008.03.005 |
| [14] | Yu, X.Y., Zhang, Y.L., Steiner, G.: Single-machine scheduling with periodic maintenance to minimize makespan revisited. J. Sched. 17, 263-270 (2014) · Zbl 1297.68045 · doi:10.1007/s10951-013-0350-0 |
| [15] | Yuan, J.J., Lin, Y.X.: Single machine preemptive scheduling with fixed jobs to minimize tardiness related criteria. Eur. J. Oper. Res. 164, 851-855 (2005) · Zbl 1057.90024 · doi:10.1016/j.ejor.2003.10.043 |
| [16] | Lawler, E.L., Moore, J.M.: A functional equation and its applications to resource allocation and sequencing problems. Manag. Sci. 16, 77-84 (1969) · Zbl 0184.23303 · doi:10.1287/mnsc.16.1.77 |
| [17] | Sahni, S.: Algorithms for scheduling independent tasks. J. Assoc. Comput. Mach. 23, 116-127 (1976) · Zbl 0326.68024 · doi:10.1145/321921.321934 |
| [18] | Moore, J.M.: An \[n\] n job, one machine sequencing algorithm for minimizing the number of late jobs. Manag. Sci. 15, 102-109 (1968) · Zbl 0164.20002 · doi:10.1287/mnsc.15.1.102 |
| [19] | Morton, T.E., Pentico, D.W.: Heuristic Scheduling Systems: with Applications to Production Systems and Project Management. Wiley, New York (1993) |
| [20] | Karp, R.M.: Reducibility among combinatorial problems. In: Complexity of Computer Computations (Proceedings of a Symposium, IBM Thomas J. Watson Res. Center, Yorktown Heights, 1972). pp. 85-103. Plenum, New York, (1972) · Zbl 1467.68065 |
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.
