Machine scheduling with job rejection and DeJong's learning effect

Jie Gao; Juan Zou; Xiaoxuan Cheng

doi:10.3934/mfc.2022024

Article Contents

2023, Volume 6, Issue 2: 253-267. Doi: 10.3934/mfc.2022024

This issue Previous Article Some structures of submatrices in solution to the paire of matrix equations

$ AX = C $

$ XB = D $

Next Article A Lévy risk model with ratcheting and barrier dividend strategies

Machine scheduling with job rejection and DeJong's learning effect

School of Mathematical Sciences, Qufu Normal University, Qufu Shandong 273165, China

^* Corresponding author: Juan Zou
^* Corresponding author: Juan Zou

Received: February 2022

Revised: May 2022

Early access: July 2022

Published: May 2023

The authors were supported by National Natural Science Foundation of China (11801310)

Abstract / Introduction Full Text(HTML) Related Papers Cited by

Abstract

This paper mainly discusses machine scheduling problems with job rejection and DeJong's learning effect. The goal is to determine the job sequence of the accepted jobs so as to minimize the scheduling cost of the accepted jobs plus the total rejection penalty of the rejected jobs. The scheduling costs of the accepted jobs are the makespan and the total completion time. For the single-machine setting, we show that both of the objectives can be optimally solved in polynomial time. For the parallel-machine setting, we show that minimizing the total completion time of the accepted jobs plus the total rejection penalty of the rejected jobs is still polynomially solvable, whereas the other problem is $ NP $-hard, for which we provide a fully polynomial-time approximation scheme (FPTAS).

Keywords:

Mathematics Subject Classification: Primary: 90B35; Secondary: 90C27.

Citation:

Full Text(HTML)

Related Papers

Cited by

References

[1]	A. Azzouz, M. Ennigrou and L. B. Said, Scheduling problems under learning effects: Classification and cartography, International Journal of Production Research, 56 (2018), 1642-1661.
[2]	M. Bai and Y. Zhao, A fully polynomial-time approximation scheme for total completion time minimization on a single machine with DeJong's learning effect and an availability constraint, Eng. Optim., 52 (2020), 1313-1322. doi: 10.1080/0305215X.2019.1650922.
[3]	Y. Bartal, S. Leonardi, A. Marchetti-Spaccamela, J. Sgall and L. Stougie, Multiprocessor scheduling with rejection, SIAM J. Discrete Math., 13 (2000), 64-78. doi: 10.1137/S0895480196300522.
[4]	D. Biskup, Single-machine scheduling with learning considerations, European Journal of Operational Research, 115 (1999), 173-178.
[5]	P. Brucker, Scheduling Algorithms, 5$^{th}$ edition, Springer-Verlag, Berlin, 2004. doi: 10.1007/978-3-540-24804-0.
[6]	T. C. E. Cheng and G. Wang, Single machine scheduling with learning effect considerations, Ann. Oper. Res., 98 (2000), 273-290. doi: 10.1023/A:1019216726076.
[7]	J. R. DeJong, The effects of increasing skill on cycle time and its consequences for time standards, Ergonomics, 1 (1957), 51-60.
[8]	D. W. Engels, D. R. Karger, S. G. Kolliopoulos, S. Sengupta, R. N. Uma and J. Wein, Techniques for scheduling with rejection, J. Algorithms, 49 (2003), 175-191. doi: 10.1016/S0196-6774(03)00078-6.
[9]	R. L. Graham, E. L. Lawler, J. K. Lenstra and A. H. G. Rinnooy Kan, Optimization and approximation in deterministic sequencing and scheduling: A survey, Ann. Discrete Math., 5 (1979), 287-326.
[10]	M. Jemmali and L. Hidri, Bounding schemes for the parallel machine scheduling problem with DeJong's learning effect, J. Parallel and Distributed Computing, 156 (2021), 101-118.
[11]	M. Ji, S. Hu, Y. Zhang, T. C. E. Cheng and Y. Jiang, Parallel-machine scheduling with identical machine resource capacity limits and DeJong's learning effect, International Journal of Production Research, 1 (2021), 1-13.
[12]	M. Ji, X. Tang, X. Zhang and T. C. E. Cheng, Machine scheduling with deteriorating jobs and DeJong's learning effect, Computers & Industrial Engineering, 91 (2016), 42-47.
[13]	M. Ji, D. Yao, Q. Yang and T. C. E. Cheng, Machine scheduling with DeJong's learning effect, Computers & Industrial Engineering, 80 (2015), 195-200.
[14]	C. Koulamas and G. Steiner, New results for scheduling to minimize tardiness on one machine with rejection and related problems, J. Sched., 24 (2021), 27-34. doi: 10.1007/s10951-020-00671-6.
[15]	M. Y. Kovalyov and W. Kubiak, A fully polynomial approximation scheme for minimizing makespan of deteriorating jobs, J. Heuristics, 3 (1998), 287-297.
[16]	M. Y. Kovalyov and W. Kubiak, A fully polynomial approximation scheme for the weighted earliness-tardiness problem, Oper. Res., 47 (1999), 757-761. doi: 10.1287/opre.47.5.757.
[17]	S. Li and R. Chen, Scheduling with rejection and a deteriorating maintenance activity on a single machine, Asia-Pac. J. Oper. Res., 34 (2017), 1750010. doi: 10.1142/S0217595917500105.
[18]	S. Li, D. Qian and R. Chen, Proportionate flow shop scheduling with rejection, Asia-Pac. J. Oper. Res., 34 (2017), 1750015. doi: 10.1142/S0217595917500154.
[19]	P. Liu and X. Lu, New approximation algorithms for machine scheduling with rejection on single and parallel machine, J. Comb. Optim., 40 (2020), 929-952. doi: 10.1007/s10878-020-00642-9.
[20]	B. Mor, G. Mosheiov and D. Shapira, Flowshop scheduling with learning effect and job rejection, J. Sched., 23 (2020), 631-641. doi: 10.1007/s10951-019-00612-y.
[21]	D. Okolowski and S. Gawiejnowicz, Exact and heuristic algorithms for parallel-machine scheduling with DeJong's learning effect, Computers & Industrial Engineering, 59 (2010), 272-279.
[22]	D. Shabtay, N. Gasper and M. Kaspi, A survey on offline scheduling with rejection, J. Sched., 16 (2013), 3-28. doi: 10.1007/s10951-012-0303-z.
[23]	J. Wang, Single machine scheduling with learning effect and deteriorating jobs, Computers & Industrial Engineering, 57 (2009), 1452-1456.
[24]	T. P. Wright, Factors affecting the cost of airplanes, J. Aeronautical Sciences, 3 (1936), 122-128.
[25]	L. Zhang and L. Lu, Parallel-machine scheduling with release dates and rejection, 4OR, 14 (2016), 165-172. doi: 10.1007/s10288-016-0304-4.
[26]	C. Zhao, J. Fang, T. C. E. Cheng and M. Ji, A note on the time complexity of machine scheduling with DeJong's learning effect, Computers & Industrial Engineering, 112 (2017), 447–449.
[27]	X. Zhong and J. Ou, Improved approximation algorithms for parallel machine scheduling with release dates and job rejection, 4OR, 15 (2017), 387-406. doi: 10.1007/s10288-016-0339-6.