We study the single-machine scheduling with maintenance intervals under preemptive pattern and resumable pattern, respectively, to minimize the total weighted late work and the weighted number of tardy jobs, respectively, where each job has a release date and a due date. According to the different combinations of the two scheduling patterns and the two scheduling criteria, six scheduling problems (including two Pareto-scheduling problems) are studied in this paper. We show that by modifying the release dates and the due dates, the six problems can be reduced to their corresponding scheduling problems without maintenance intervals in quasi-linear time. As a consequence, complexity results of our problems can be directly obtained from the known results in the literature. In particular, for the problem under resumable pattern to minimize the total weighted late work with all the jobs being released at time 0, an \begin{document}$ O(m{n^2}{P}) $\end{document}-time algorithm was presented in the literature, where m is the number of maintenance intervals, n is the number of jobs, and P is the total processing time of the jobs; and our research shows that the same problem is solvable in \begin{document}$ O(n^{2}{P}+m\log m ) $\end{document} time, improving this known result.
Ru-Yan He, Jin-Jiang Yuan, Yuan Zhang
. The Single-Machine Preemptive or Resumable Scheduling with Maintenance Intervals[J]. Journal of the Operations Research Society of China, 2025
, 13(2)
: 590
-602
.
DOI: 10.1007/s40305-023-00495-z
[1] Graham, R.L., Lawler, E.L., Lenstra, J.K., et al.: Optimization and approximation in deterministic sequencing and scheduling: a survey. Ann. Discrete Math. 5, 287-326 (1979)
[2] Schmidt, G.: Scheduling on semi-identical processors. Zeitschrift für Oper. Res. 28(5), 153-162 (1984)
[3] 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)
[4] Lee, C.Y.: Machine scheduling with an availability constraint. J. Global Optim. 9(3-4), 395-416 (1996)
[5] Yuan, J.J., Lin, Y.X.: Single machine preemptive scheduling with fixed jobs to minimize tardiness related criteria. Eur. J. Oper. Res. 164(3), 851-855 (2005)
[6] Zou, J., Yuan, J.J.: Single-machine scheduling with maintenance activities and rejection. Discrete. Optim. 38, 100609 (2020)
[7] Moore, J.M.: An \begin{document}$ n $\end{document} job, one machine sequencing algorithm for minimizing the number of late jobs. Manage. Sci. 15(1), 102-109 (1968)
[8] Karp, R.M.: Reducibility among combinatorial problems. In: Miller, R.E., Thatcher, J.W. (eds.) Complexity of Computer Computations, pp. 85-103. Plenum Press, New York (1972)
[9] Lawler, E.L., Moore, J.M.: A functional equation and its application to resource allocation and sequencing problems. Manage. Sci. 16(1), 77-84 (1969)
[10] Sahni, S.K.: Algorithms for scheduling independent tasks. J. Assoc. Comput. Mach. 23(1), 116-127 (1976)
[11] Lawler, E.L.: A dynamic programming algorithm for preemptive scheduling of a single machine to minimize the number of late jobs. Ann. Oper. Res. 26(1), 125-133 (1990)
[12] Vakhania, N.: Scheduling jobs with release times preemptively on a single machine to minimize the number of late jobs. Oper. Res. Lett. 37(6), 405-410 (2009)
[13] Blazewicz, J., Finke, G.: Minimizing mean weighted execution time loss on identical and uniform processors. Inform. Process. Lett. 24(4), 259-263 (1987)
[14] Potts, C.N., Van Wassenhove, L.N.: Single machine scheduling to minimize total late work. Oper. Res. 40(3), 586-595 (1992)
[15] Potts, C.N., Van Wassenhove, L.N.: Approximation algorithms for scheduling a single machine to minimize total late work. Oper. Res. Lett. 11(5), 261-266 (1992)
[16] Kovalyov, M.Y., Potts, C.N., Van Wassenhove, L.N.: A fully polynomial approximation scheme for scheduling a single machine to minimize total weighted late work. Math. Oper. Res. 19(1), 86-93 (1994)
[17] Hariri, A.M.A., Potts, C.N., Van Wassenhove, L.N.: Single machine scheduling to minimize total weighted late work. ORSA J. Comput. 7(2), 232-242 (1995)
[18] Leung, J.Y.T., Yu, V.K.M., Wei, W.D.: Minimizing the weighted number of tardy task units. Discrete. Appl. Math. 51(3), 307-316 (1994)
[19] Sterna, M.: A survey of scheduling problems with late work criteria. Omega 39(2), 120-129 (2011)
[20] Chen, R.B., He, R.Y., Yuan, J.J.: Preemptive scheduling to minimize total weighted late work and weighted number of tardy jobs. Comput. Ind. Eng. 167, 107969 (2022)
[21] Guo, S.E., Lu, L.F., Yuan, J.J., et al.: Pareto-scheduling with double-weighted jobs to minimize the weighted number of tardy jobs and total weighted late work. Nav. Res. Log. 69(5), 816-837 (2022)
[22] Zhang, Y., Yuan, J.J.: A note on a two-agent scheduling problem related to the total weighted late work. J. Comb. Optim. 37(3), 989-999 (2019)
[23] Yin, Y.Q., Xu, J.Y., Cheng, T.C.E., et al.: Approximation schemes for single-machine scheduling with a fixed maintenance activity to minimize the total amount of late work. Nav. Res. Log. 63(2), 172-183 (2016)
[24] Li, S.S., Chen, R.X.: Minimizing total weighted late work on a single-machine with non-availability intervals. J. Comb. Optim. 44(2), 1330-1355 (2022)
[25] Yuan, J.J.: Unary NP-hardness of minimizing the number of tardy jobs with deadlines. J. Scheduling. 20(2), 211-218 (2017)
[26] Chen, R.B., Yuan, J.J., Ng, C.T., et al.: Single-machine scheduling with deadlines to minimize the total weighted late work. Nav. Res. Log. 7(66), 582-595 (2019)
