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

SHEN Hui-jun, GENG Zhi-chao

doi:10.13371/j.cnki.chin.q.j.m.2022.04.009

Chinese Quarterly Journal of Mathematics >

2022 , Vol. 37 >Issue 4: 412 - 421

DOI: https://doi.org/10.13371/j.cnki.chin.q.j.m.2022.04.009

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

Expand

School of Mathematics and Statistics, Zhengzhou University, Zhengzhou 450001, China

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.

Received date: 2022-11-14

Online published: 2022-12-30

Supported by

Supported by National Natural Science Foundation of China (Grant Nos. 12071442, 11971443, 12271491).

Fold

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

Cite this article

SHEN Hui-jun, GENG Zhi-chao . A Note on Single-Machine Lot Scheduling with Splittable Jobs to Minimize the Number of Tardy Jobs[J]. Chinese Quarterly Journal of Mathematics, 2022 , 37(4) : 412 -421 . DOI: 10.13371/j.cnki.chin.q.j.m.2022.04.009

Options

Outlines

模态框（Modal）标题

Abstract

Cite this article