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]. 运筹学学报, 2023, 27(1): 115-126.
[2]	张安, 陈永, 陈光亭, 陈占文, 舒巧君, 林国辉. 优先序约束的排序问题：基于最大匹配的近似算法[J]. 运筹学学报, 2022, 26(3): 57-74.
[3]	王银玲, 韩鑫, 邵欣欣. 关于带运输的单机调度在线问题的研究[J]. 运筹学学报, 2022, 26(1): 125-133.
[4]	徐晨, 徐寅峰, 郑斐峰. 考虑部分工件不可打扰的多任务调度问题研究[J]. 运筹学学报, 2021, 25(4): 91-100.
[5]	陈峰. 运筹学在整车物流智能调度决策支持系统中的研究与应用[J]. 运筹学学报, 2021, 25(3): 37-73.
[6]	余山杉, 金苗苗, 罗文昌. 工件延误和可拒绝下的单机重新排序问题的近似方案[J]. 运筹学学报, 2021, 25(2): 104-114.
[7]	沈吟东, 钱壮, 李媛媛. 公共交通驾驶员调度研究综述[J]. 运筹学学报, 2021, 25(1): 1-16.
[8]	黄基诞, 郑斐峰, 徐寅峰, 刘明. 安装时间具有退化效应的MapReduce模型下的平行机调度[J]. 运筹学学报, 2020, 24(4): 93-106.
[9]	张玉忠, 李曙光. 带树层次加工集约束的调度问题[J]. 运筹学学报, 2020, 24(4): 107-112.
[10]	陆书翔, 吕长虹, 秦涛. 集装箱码头桥机调度问题基于完工时间下界的算法[J]. 运筹学学报, 2020, 24(3): 67-76.
[11]	仲维亚, 施益媚. 不确定彩排时长下节目调度的鲁棒优化[J]. 运筹学学报, 2020, 24(3): 77-86.
[12]	王翼展, 张安, 陈永, 陈光亭. 堆取料机调度问题的一个近似算法[J]. 运筹学学报, 2020, 24(1): 147-154.
[13]	李英, 乔龙亮, 郑斐峰. 具有预知信息的集装箱码头泊位与岸桥联合调度在线模型[J]. 运筹学学报, 2018, 22(3): 28-36.
[14]	宁涛, 陈荣, 郭晨, 梁旭. 一种基于双链量子编码的动态车辆路径问题解决策略[J]. 运筹学学报, 2015, 19(2): 72-82.
[15]	许小艳, 慕运动, 郝~~赟. 基于重新排序的退化工件最小化总延误时间问题[J]. 运筹学学报, 2013, 17(4): 56-62.

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

Scheduling with periodic due date to minimize the maximum tardiness

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

本文评价