# American Institute of Mathematical Sciences

doi: 10.3934/mfc.2022024
Online First

Online First articles are published articles within a journal that have not yet been assigned to a formal issue. This means they do not yet have a volume number, issue number, or page numbers assigned to them, however, they can still be found and cited using their DOI (Digital Object Identifier). Online First publication benefits the research community by making new scientific discoveries known as quickly as possible.

Readers can access Online First articles via the “Online First” tab for the selected journal.

## 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

Received  February 2022 Revised  May 2022 Early access July 2022

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

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).

Citation: Jie Gao, Juan Zou, Xiaoxuan Cheng. Machine scheduling with job rejection and DeJong's learning effect. Mathematical Foundations of Computing, doi: 10.3934/mfc.2022024
##### 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.

show all references

##### 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.
 [1] Hongtruong Pham, Xiwen Lu. The inverse parallel machine scheduling problem with minimum total completion time. Journal of Industrial and Management Optimization, 2014, 10 (2) : 613-620. doi: 10.3934/jimo.2014.10.613 [2] Muberra Allahverdi, Ali Allahverdi. Minimizing total completion time in a two-machine no-wait flowshop with uncertain and bounded setup times. Journal of Industrial and Management Optimization, 2020, 16 (5) : 2439-2457. doi: 10.3934/jimo.2019062 [3] Ran Ma, Jiping Tao. An improved 2.11-competitive algorithm for online scheduling on parallel machines to minimize total weighted completion time. Journal of Industrial and Management Optimization, 2018, 14 (2) : 497-510. doi: 10.3934/jimo.2017057 [4] Jinjiang Yuan, Weiping Shang. A PTAS for the p-batch scheduling with pj = p to minimize total weighted completion time. Journal of Industrial and Management Optimization, 2005, 1 (3) : 353-358. doi: 10.3934/jimo.2005.1.353 [5] P. Liu, Xiwen Lu. Online scheduling of two uniform machines to minimize total completion times. Journal of Industrial and Management Optimization, 2009, 5 (1) : 95-102. doi: 10.3934/jimo.2009.5.95 [6] Kaixin Gao, Zheng-Hai Huang, Xiaolei Liu. Enhancing low-rank tensor completion via first-order and second-order total variation regularizations. Journal of Industrial and Management Optimization, 2022  doi: 10.3934/jimo.2022136 [7] Zhichao Geng, Jinjiang Yuan. Scheduling family jobs on an unbounded parallel-batch machine to minimize makespan and maximum flow time. Journal of Industrial and Management Optimization, 2018, 14 (4) : 1479-1500. doi: 10.3934/jimo.2018017 [8] J. J. Morgan, Hong-Ming Yin. On Maxwell's system with a thermal effect. Discrete and Continuous Dynamical Systems - B, 2001, 1 (4) : 485-494. doi: 10.3934/dcdsb.2001.1.485 [9] Ta-Wei Hung, Ping-Ting Chen. On the optimal replenishment in a finite planning horizon with learning effect of setup costs. Journal of Industrial and Management Optimization, 2010, 6 (2) : 425-433. doi: 10.3934/jimo.2010.6.425 [10] Mingbao Cheng, Shuxian Xiao, Guosheng Liu. Single-machine rescheduling problems with learning effect under disruptions. Journal of Industrial and Management Optimization, 2018, 14 (3) : 967-980. doi: 10.3934/jimo.2017085 [11] Shuang Zhao. Resource allocation flowshop scheduling with learning effect and slack due window assignment. Journal of Industrial and Management Optimization, 2021, 17 (5) : 2817-2835. doi: 10.3934/jimo.2020096 [12] Qian Wei, Jianxiong Zhang, Xiaojie Sun. Incentive contract design for supplier switching with considering learning effect. Journal of Industrial and Management Optimization, 2021, 17 (6) : 3559-3580. doi: 10.3934/jimo.2020133 [13] Marion Darbas, Jérémy Heleine, Stephanie Lohrengel. Numerical resolution by the quasi-reversibility method of a data completion problem for Maxwell's equations. Inverse Problems and Imaging, 2020, 14 (6) : 1107-1133. doi: 10.3934/ipi.2020056 [14] Hyeong-Ohk Bae, Seung Yeon Cho, Jane Yoo, Seok-Bae Yun. Effect of time delay on flocking dynamics. Networks and Heterogeneous Media, 2022, 17 (5) : 803-825. doi: 10.3934/nhm.2022027 [15] Anarina L. Murillo, Muntaser Safan, Carlos Castillo-Chavez, Elizabeth D. Capaldi Phillips, Devina Wadhera. Modeling eating behaviors: The role of environment and positive food association learning via a Ratatouille effect. Mathematical Biosciences & Engineering, 2016, 13 (4) : 841-855. doi: 10.3934/mbe.2016020 [16] Mehmet Duran Toksari, Emel Kizilkaya Aydogan, Berrin Atalay, Saziye Sari. Some scheduling problems with sum of logarithm processing times based learning effect and exponential past sequence dependent delivery times. Journal of Industrial and Management Optimization, 2022, 18 (3) : 1795-1807. doi: 10.3934/jimo.2021044 [17] Si-Han Wang, Dan-Yang Lv, Ji-Bo Wang. Research on position-dependent weights scheduling with delivery times and truncated sum-of-processing-times-based learning effect. Journal of Industrial and Management Optimization, 2022  doi: 10.3934/jimo.2022066 [18] Ran Ma, Lu Zhang, Yuzhong Zhang. A best possible algorithm for an online scheduling problem with position-based learning effect. Journal of Industrial and Management Optimization, 2022, 18 (6) : 3989-4010. doi: 10.3934/jimo.2021144 [19] Christopher M. Kribs-Zaleta, Melanie Lee, Christine Román, Shari Wiley, Carlos M. Hernández-Suárez. The Effect of the HIV/AIDS Epidemic on Africa's Truck Drivers. Mathematical Biosciences & Engineering, 2005, 2 (4) : 771-788. doi: 10.3934/mbe.2005.2.771 [20] Alexei Pokrovskii, Dmitrii Rachinskii. Effect of positive feedback on Devil's staircase input-output relationship. Discrete and Continuous Dynamical Systems - S, 2013, 6 (4) : 1095-1112. doi: 10.3934/dcdss.2013.6.1095

Impact Factor: