On Scheduling a Deteriorating Rate-Modifying Activity to Minimize the Number of Tardy Jobs

doi:10.1007/s40305-018-0207-5

Abstract

Abstract: We investigate a single-machine scheduling problem, where a deteriorating rate-modifying activity can be performed on the machine to reduce the processing times of jobs.The objective is to minimize the number of tardy jobs.Under the assumption that the duration of the rate-modifying activity is a nonnegative and nondecreasing functionon its starting time,we propose an optimal polynomial time algorithm running in O(n³) time.

Key words: Scheduling, Rate-modifying activity, Due date, Polynomial time algorithm

CLC Number:

90B35

Wen-Chang Luo. On Scheduling a Deteriorating Rate-Modifying Activity to Minimize the Number of Tardy Jobs[J]. Journal of the Operations Research Society of China, 2020, 8(1): 165-175.

TrendMD

References

[1] Lee, C.Y., Leon, V.J.:Machine scheduling with a rate-modifying activity. Eur. J. Oper. Res. 128(1), 119-128(2001)
[2] Lodree Jr., E.J., Geiger, C.D.:A note on the optimal sequence position for a rate-modifying activity under simple linear deterioration. Eur. J. Oper. Res. 201(2), 644-648(2010)
[3] Zhao, C., Tang, H.:A note to due-window assignment and single machine scheduling with deteriorating jobs and a rate-modifying activity. Comput. Oper. Res. 39(6), 1300-1303(2012)
[4] Ji, M., Cheng, T.E.:Scheduling with job-dependent learning effects and multiple rate-modifying activities. Inf. Process. Lett. 110(11), 460-463(2010)
[5] Rustogi, K., Strusevich, V.A.:Single machine scheduling with general positional deterioration and rate-modifying maintenance. Omega 40(6), 791-804(2012)
[6] Zhao, C.L., Tang, H.Y., Cheng, C.D.:Two-parallel machines scheduling with rate-modifying activities to minimize total completion time. Eur. J. Oper. Res. 198(1), 354-357(2009)
[7] Hsu, C.J., Cheng, T.E., Yang, D.L.:Unrelated parallel-machine scheduling with rate-modifying activities to minimize the total completion time. Inf. Sci. 181(20), 4799-4803(2011)
[8] Cheng, T.E., Hsu, C.J., Yang, D.L.:Unrelated parallel-machine scheduling with deteriorating maintenance activities. Comput. Ind. Eng. 60(4), 602-605(2011)
[9] Yin, Y., Cheng, T.C.E., Xu, D., Wu, C.C.:Common due date assignment and scheduling with a ratemodifying activity to minimize the due date, earliness, tardiness, holding, and batch delivery cost. Comput. Ind. Eng. 63(1), 223-234(2012)
[10] Yin, Y., Cheng, T.C.E., Wu, C.C., Cheng, S.R.:Single-machine batch delivery scheduling and common due-date assignment with a rate-modifying activity. Int. J. Prod. Res. 52(19), 5583-5596(2014)
[11] Ji, M., Ge, J., Chen, K., Cheng, T.C.E.:Single-machine due-window assignment and scheduling with resource allocation, aging effect, and a deteriorating rate-modifying activity. Comput. Ind. Eng. 66(4), 952-961(2013)
[12] Kellerer, H., Rustogi, K., Strusevich, V.A.:Approximation schemes for scheduling on a single machine subject to cumulative deterioration and maintenance. J. Sched. 16(6), 675-683(2013)
[13] Yang, D.L., Yang, S.J.:Unrelated parallel-machine scheduling problems with multiple rate-modifying activities. Inf. Sci. 235(20), 280-286(2013)
[14] Mosheiov, G., Sidney, J.B.:Scheduling a deteriorating maintenance activity on a single machine. J. Oper. Res. Soc. 61(5), 882-887(2010)
[15] Kubzin, M.A., Strusevich, V.A.:Planning machine maintenance in two-machine shop scheduling. Oper. Res. 54(4), 789-800(2006)
[16] Luo, W., Chen, L., Zhang, G.:Approximation algorithms for scheduling with a variable machine maintenance. In:Algorithmic Aspects in Information and Management, LNCS, vol. 6124, pp. 209-219. Springer, Berlin (2010)
[17] Moore, J.M.:An n jobs, one machine sequencing algorithm for minimizing the number of late jobs. Manag. Sci. 15, 102-109(1968)
[18] Lin, Y., Wang, X.:Necessary and sufficient conditions of optimality for some classical scheduling problems. Eur. J. Oper. Res. 176(2), 809-818(2007)
[19] Hoogeveen, H., T'kindt, V.:Minimizing the number of late jobs when the start time of the machine is variable. Oper. Res. Lett. 40, 353-355(2012)