PDD规则下最小化最大延误调度问题

doi:10.15960/j.cnki.issn.1007-6093.2022.04.006

运筹学学报 ›› 2022, Vol. 26 ›› Issue (4): 75-86.doi: 10.15960/j.cnki.issn.1007-6093.2022.04.006

PDD规则下最小化最大延误调度问题

万龙^*, 黄晓莉, 梅嘉杰

江西财经大学信息管理学院, 江西南昌 330013

收稿日期:2021-10-13 发布日期:2022-11-28
通讯作者: 万龙 E-mail:cocu3328@163.com
基金资助:
江西省教育厅科技项目(No. GJJ190250)

Scheduling with periodic due date to minimize the maximum tardiness

WAN Long^*, HUANG Xiaoli, MEI Jiajie

School of Information Management, Jiangxi University of Finance and Economics, Nanchang 330013, Jiangxi, China

Received:2021-10-13 Published:2022-11-28

摘要/Abstract

摘要： 本文研究机器环境分别为单机、同型机和开放作业机器三种不同环境下的新型调度问题。其中工期根据工件的具体完工时间确定，且连续工期之间的间隔是相等的，一般称这种工期为等间隔工期(PDD)。本文考虑的目标函数都是最小化最大延误。对于单机环境，给出了多项式时间最优算法；对于两台同型机环境，证明了该问题是NP-难的；对于一般同型机环境，证明了该问题是强NP-难的；对于两台开放作业机器环境，证明了该问题是强NP-难的。

关键词: 调度, 开放作业, 等间隔工期, 延误, NP-完全性

Abstract: In the paper, we consider novel scheduling problems under single-machine, parallel-machine and two-machine open-shop environment. The due date is assigned to a job according to its completion time and the intervals between consecutive due dates are identical. Generally, the due dates are referred as periodic due dates (PDD). The objectives we consider are all to minimize the maximum tardiness. For single machine environment, we give an optimal schedule in polynomial time; for two parallel-machine environment, we prove this problem is NP-hard; for parallel-machine environment, we prove this problem is strongly NP-hard; for two-machine open-shop environment, we prove this problem is strongly NP-hard.

Key words: scheduling, open shop, periodic due date, tardiness, NP-completeness

中图分类号:

O221.2

万龙, 黄晓莉, 梅嘉杰. PDD规则下最小化最大延误调度问题[J]. 运筹学学报, 2022, 26(4): 75-86.

WAN Long, HUANG Xiaoli, MEI Jiajie. Scheduling with periodic due date to minimize the maximum tardiness[J]. Operations Research Transactions, 2022, 26(4): 75-86.

[1] Hall N G. Scheduling problems with generalized due dates[J]. IIE Transactions, 1986, 18(2): 220-222.
[2] Sriskandarajah C. A note on the generalized due dates scheduling problem[J]. Naval Research Logistics, 1990, 37(4): 587-597.
[3] Gao Y, Yuan J J. Unary NP-hardness of minimizing total weighted tardiness with generalized due dates[J]. Operations Research Letters, 2016, 44(1): 92-95.
[4] Wan L, Yuan J J. Single-machine scheduling to minimize the total earliness and tardiness is strongly NP-hard[J]. Operations Research Letters, 2013, 41(4): 363-365.
[5] Qi X T, Yu G, Bard J F. Single machine scheduling with assignable due dates[J]. Discrete Applied Mathematics, 2002, 122(1-3): 211-233.
[6] Gao Y, Yuan J J. Unary NP-hardness of minimizing the total deviation with generalized or assignable due dates[J]. Discrete Applied Mathematics, 2015, 189(10): 49-52.
[7] Choi B C, Park M J. Just-in-time scheduling with generalized due dates and identical due date intervals[J]. Asia-Pacific Journal of Operational Research, 2018, 35(6): 1850046.1-1850046.13.
[8] Choi B C, Min Y, Park M J. Strong NP-hardness of minimizing total deviation with generalized and periodic due dates[J]. Operations Research Letters, 2019, 47(5): 433-437.
[9] Choi B C, Park M J. Single-machine scheduling with periodic due dates to minimize the total earliness and tardy penalty[J]. Journal of Combinatorial Optimization, 2021, 41(4): 781-793.
[10] Choi B C, Kim K M, Min Y, et al. Scheduling with generalized and periodic due dates under single-and two-machine environments[J]. Optimization Letters, 2021: 1-11.
[11] Garey M R, Johnson D S. Computers and Intractability: A Guide to The Theory of NP-Completeness[M]. San Francisco: W H Freeman and Company, 1979.
[12] Brucker P. Scheduling Algorithms[M]. Berlin Heidelberg: Springer-Verlag, 2007.

[1]	许可, 吉兰萍, 宫华, 刘鹏, 孙文娟. 基于拍卖算法的多代理并行机生产运输协调调度[J]. 运筹学学报（中英文）, 2026, 30(1): 121-136.
[2]	孟兰梦, 马冉, 张玉忠. 在NDP约束条件下考虑带退化效应的单机在线调度[J]. 运筹学学报（中英文）, 2026, 30(1): 179-187.
[3]	靳凯媛, 郑斐峰, 刘明. 考虑订单类型和准备时间的批处理机在线调度模型研究[J]. 运筹学学报（中英文）, 2025, 29(4): 231-240.
[4]	孙瑞卿, 张芮, 兰艳, 李伟东. 提前完工总量最大化问题的LPT算法[J]. 运筹学学报（中英文）, 2025, 29(4): 249-254.
[5]	万国华, 王杉, 黄腾方. 服务系统中的预约调度: 综述及扩展[J]. 运筹学学报（中英文）, 2025, 29(3): 61-76.
[6]	鲁炜, 卢星宇, 邹丁, 陈博晓, 周义涵, 张国川. 绿色计算下算力调度优化问题与技术研究[J]. 运筹学学报（中英文）, 2025, 29(3): 179-201.
[7]	郭思琦, 周萍, 蒋义伟, 季敏. 考虑碳排放成本的计件维护单机调度问题[J]. 运筹学学报（中英文）, 2025, 29(2): 68-79.
[8]	袁园, 兰艳, 韩鑫. 带有维护窗口的调度问题的综述[J]. 运筹学学报（中英文）, 2025, 29(1): 1-18.
[9]	李娜, 马冉, 李龙, 张玉忠. 具有学习效应的预制构件生产调度研究[J]. 运筹学学报（中英文）, 2025, 29(1): 19-30.
[10]	徐博, 马卫民, 柯华, 张浩. 基于秩2矩阵近似的飞机起降多目标调度模型与算法研究[J]. 运筹学学报（中英文）, 2024, 28(4): 29-43.
[11]	吴琼, 王长军. 基于拉格朗日松弛的产能共享讨价还价研究[J]. 运筹学学报（中英文）, 2024, 28(2): 93-102.
[12]	何胜学. 基于超级时空网络的公交车辆调度模型及3M进化算法[J]. 运筹学学报, 2023, 27(3): 68-82.
[13]	徐薇, 黄悦丰, 陈彩华. 考虑配置储能系统的电动公交充电站充放电调度策略[J]. 运筹学学报, 2023, 27(2): 95-109.
[14]	于静, 徐哲, 谢芳. 带有活动重叠的项目调度问题新算法: 分支定界法[J]. 运筹学学报, 2023, 27(1): 115-126.
[15]	张安, 陈永, 陈光亭, 陈占文, 舒巧君, 林国辉. 优先序约束的排序问题：基于最大匹配的近似算法[J]. 运筹学学报, 2022, 26(3): 57-74.

PDD规则下最小化最大延误调度问题

Scheduling with periodic due date to minimize the maximum tardiness

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

相关文章 15

编辑推荐

Metrics

本文评价