Chinese Quarterly Journal of Mathematics ›› 2022, Vol. 37 ›› Issue (4): 412-421.doi: 10.13371/j.cnki.chin.q.j.m.2022.04.009

Previous Articles     Next Articles

A Note on Single-Machine Lot Scheduling with Splittable Jobs to Minimize the Number of Tardy Jobs

  

  1. School of Mathematics and Statistics, Zhengzhou University, Zhengzhou 450001, China
  • Received:2022-11-14 Online:2022-12-30 Published:2022-12-30
  • Contact: GENG Zhi-chao (1981-), male, native of Zhengzhou, Henan, lecturer of Zhengzhou University, engages in scheduling and combinatorial optimization. E-mail:zcgeng@zzu.edu.cn
  • About author:SHEN Hui-jun (2000-), male, native of Zhengzhou, Henan, postgraduate of Zhengzhou University, engages in scheduling and combinatorial optimization; GENG Zhi-chao (1981-), male, native of Zhengzhou, Henan, lecturer of Zhengzhou University, engages in scheduling and combinatorial optimization.
  • Supported by:
    Supported by National Natural Science Foundation of China (Grant Nos. 12071442, 11971443, 12271491).

Abstract: The single-machine lot scheduling problem with splittable jobs to minimize the number of tardy jobs has been showed to be weakly NP-hard in the literature. In this paper, we show that a generalized version of this problem in which jobs have deadlines is strongly NP-hard, and also present the results of some related scheduling problems. 

Key words: Lot scheduling, The number of tardy jobs, Splitting jobs, Strongly NP-hard 

CLC Number: