In this paper, we consider the single-machine scheduling with step-deteriorating jobs and rejection. Each job is either rejected by paying a rejection penalty, or accepted and processed on the single machine, and the actual processing time of each accepted job is a step function of its starting time and the common deteriorating date. The objective is to minimize the makespan of the accepted jobs plus the total penalty of the rejected jobs. For the case of common deteriorating penalty, we first show that the problem is NP-hard in the ordinary sense. Then we present two pseudo-polynomial algorithms and a 2-approximation algorithm. Furthermore, we propose a fully polynomial time approximation scheme. For the case of common normal processing time, we present two pseudo-polynomial time algorithms, a 2-approximation algorithm and a fully polynomial time approximation scheme.
Fan-Yu Kong, Cui-Xia Miao, Yu-Jia Huo, Jia-Xin Song, Yu-Zhong Zhang
. Single-Machine Scheduling with Step-Deteriorating Jobs and Rejection[J]. Journal of the Operations Research Society of China, 2024
, 12(4)
: 1088
-1102
.
DOI: 10.1007/s40305-023-00481-5
[1] Cheng, T.C.E., Ding, Q.: Single machine scheduling with step-deteriorating processing times. Eur. J. Oper. Res. 134, 623-630(2001)
[2] Graham, R.L., Lawle, E.L., Lenstra, J.K., Kan, A.R.: Optimization and approximation in deterministic sequencing and scheduling: a survey. Ann. Discret. Math.
[3] Mosheiov, G.: Scheduling jobs with step-deterioration: minimizing makespan on a single and multimachine. Comput. Ind. Eng. 28, 869-879(1995)
[4] Sundararaghavan, P.S., Kunnathur, A.S.: Single machine scheduling with start time dependent processing times: some solvable cases. Eur. J. Oper. Res. 78, 394-403(1994)
[5] Jeng, A.A.K., Lin, B.M.T.: Minimizing the total completion time in single-machine scheduling with step-deteriorating jobs. Comput. Oper. Res. 32, 521-536(2005)
[6] Mor, B., Mosheiov, G.: Batch scheduling with step-deteriorating processing times to minimize flowtime. Nav. Res. Log. 59, 587-600(2012)
[7] Miao, C.X., Zhang, Y.Z.: Scheduling with step-deteriorating jobs to minimize the makespan. J. Ind. Manag. Optim. 15(4), 1955-1964(2019)
[8] Miao, C.X., Kong, F.Y., Zou, J., Ma, R., Huo, Y.J.: Parallel-machine scheduling with step-deteriorating jobs to minimize the total (weighted) completion time. Asia Pac. J. Oper. Res. (2022). https://doi.org/10.1142/S0217595922400115
[9] Bartal, Y., Leonardi, S., Marchetti-Spaccamela, A., Stougie, L.: Multiprocessor scheduling with rejection. SIAM J. Discret. Math. 13, 64-78(2000)
[10] Lu, L.F., Cheng, T.C.E., Yuan, J.J., Zhang, L.Q.: The unbounded parallel batch machine scheduling with release dates and rejection to minimize makespan. Theor. Comput. Sci. 396, 283-289(2008)
[11] Cheng, Y.S., Sun, S.T.: Scheduling linear deterirating jobs with rejection on a single machine. Eur. J. Oper. Res. 194, 18-27(2009)
[12] Shabtay, D., Gaspar, N., Kaspi, M.: A survey on offline scheduling with rejection. J. Sched. 16, 3-28(2013)
[13] Li, D.W., Lu, X.W.: Two-agent parallel-machine scheduling with rejection. Theor. Comput. Sci. 703, 66-75(2017)
[14] Zhang, L.Q., Lu, L.F., Yuan, J.J.: Single machine scheduling with release dates and rejection. Eur. J. Oper. Res. 198(3), 975-978(2009)
[15] Garey,M.R., Johnson,D.S.: Computers andIntractability:AGuide to the Theory ofNP-Completeness, vol. 5, pp. 287-326. Freeman, San Francisco (1979)
