工件允许拆分加工的单机排序问题

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

数学季刊 ›› 2022, Vol. 37 ›› Issue (4): 412-421.doi: 10.13371/j.cnki.chin.q.j.m.2022.04.009

工件允许拆分加工的单机排序问题

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

收稿日期:2022-11-14 出版日期:2022-12-30 发布日期:2022-12-30
通讯作者: 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
作者简介: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 National Natural Science Foundation of China (Grant Nos. 12071442, 11971443, 12271491).

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

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.

关键词: Lot scheduling, The number of tardy jobs, Splitting jobs, Strongly NP-hard

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

中图分类号:

O187.1

申惠军, 耿志超. 工件允许拆分加工的单机排序问题[J]. 数学季刊, 2022, 37(4): 412-421.

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.

[1]	邹绵璐, 李强. 贝索夫空间中三维布辛涅斯克方程的一些新的正则性准则[J]. 数学季刊, 2024, 39(1): 73-81.
[2]	郭晋东. 关于两个两点Witten-Kontsevich关联子公式等价的一个注记[J]. 数学季刊, 2024, 39(1): 82-85.
[3]	刘功伟, 杨坤. 一类退化抛物方程高初始能量下解的有限时刻爆破及整体存在性[J]. 数学季刊, 2024, 39(1): 97-110.
[4]	唐忠华, 房少梅. 带分数阶Robin边界条件的时间-空间分数阶扩散方程的有限差分方法[J]. 数学季刊, 2024, 39(1): 18-30.
[5]	李鸿军. 凸复Finsler流形上的Hopf-Rinow定理[J]. 数学季刊, 2024, 39(1): 31-45.
[6]	洪勇, 赵茜. 两类加权空间间的积分算子与离散算子的有界性及算子范数估计[J]. 数学季刊, 2024, 39(1): 59-67.
[7]	王川, 乔炎. Korteweg-de Vries方程的Legendre时空谱配置方法[J]. 数学季刊, 2023, 38(4): 392-400.
[8]	许娜. 一类次线性基尔霍夫方程基态解的存在性[J]. 数学季刊, 2023, 38(4): 410-414.
[9]	杨亦松. 曲面上的曲率在理论物理中的一些应用[J]. 数学季刊, 2023, 38(3): 221-253.
[10]	徐晓濛. Stokes 现象与量子群的表示[J]. 数学季刊, 2023, 38(3): 311-330.
[11]	黄述亮. 带有对合的素环的微分恒等式[J]. 数学季刊, 2023, 38(2): 134-144.
[12]	马腾. 变指标中心Morrey空间上带Dini核的多线性C-Z算子[J]. 数学季刊, 2023, 38(2): 184-195.
[13]	梁艳霞. 带位势的基尔霍夫方程规范解的存在性[J]. 数学季刊, 2023, 38(2): 196-209.
[14]	白宏芳. 一类具有时滞的生态流行病模型的稳定性与 Hopf 分支[J]. 数学季刊, 2023, 38(2): 157-183.
[15]	杜玲珑, 韩晓岳, 于佳平, 周昕昀. 具有势场的随机Cucker-Smale系统[J]. 数学季刊, 0, (): 111-122.

工件允许拆分加工的单机排序问题

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

PDF (PC)

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

本文评价