加工时间与运输时间具有一致性的单机NDP约束在线排序问题研究

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

运筹学学报（中英文） ›› 2024, Vol. 28 ›› Issue (4): 18-28.doi: 10.15960/j.cnki.issn.1007-6093.2024.04.002

加工时间与运输时间具有一致性的单机NDP约束在线排序问题研究

李文杰¹^,*(), 杜智慧¹, 苏孟龙¹

1. 洛阳师范学院数学科学学院, 河南洛阳 471934

收稿日期:2022-03-30 出版日期:2024-12-15 发布日期:2024-12-20
通讯作者: 李文杰 E-mail:liwenjie0521@163.com
基金资助:
河南省自然科学基金(222300420503);河南省高校重点基础研究基金(22A110015);河南省高校青年骨干教师培养计划基金(2019GGJS202);河南省高校青年骨干教师培养计划基金(2018XJGGJS-10)

Research on the NDP-constraint online scheduling of jobs have agreeable processing times and delivery times

Wenjie LI¹^,*(), Zhihui DU¹, Menglong SU¹

1. School of Mathematical Sciences, Luoyang Normal University, Luoyang 471934, Henan, China

Received:2022-03-30 Online:2024-12-15 Published:2024-12-20
Contact: Wenjie LI E-mail:liwenjie0521@163.com

摘要/Abstract

摘要：

本文研究NDP约束下的最小化最大运输完工时间单机在线排序问题。这里的“NDP约束”是指当有工件到达时, 则空闲机器必须立刻选择工件加工, 即工件不能被强制推迟加工。本文讨论所有工件的加工时间与运输时间均具有一致性的排序模型, 即若工件$J_{i}$和$J_{j}$的加工时间满足$p_{i}\geq p_{j}$, 则其运输时间满足$q_{i}\geq q_{j}$。我们首先给出NDP约束下该排序问题的下界为4/3, 其次设计出一个竞争比是1.382的在线算法。

关键词: 在线排序, 在线算法, NDP约束, 一致性, 运输完工时间

Abstract:

This paper studies the single-machine online schedule under the NDP-constraint to minimize the maximum delivery completion time. Here "NDP-constraint" means that the idle machine must schedule the available jobs at any time, i.e., the available jobs cannot be delayed for processing. In this paper, we study the restricted version in which the jobs have agreeable processing times and delivery times (if $p_{i}\geq p_{j}$, then $p_{i}\geq p_{j}$). we first present a lower bound of 4/3 and then design an online algorithm with the competitive ratio of 1.382.

Key words: online scheduling, online algorithm, NDP-constraint, agreeable, delivery completion time

中图分类号:

O221.7

李文杰, 杜智慧, 苏孟龙. 加工时间与运输时间具有一致性的单机NDP约束在线排序问题研究[J]. 运筹学学报（中英文）, 2024, 28(4): 18-28.

Wenjie LI, Zhihui DU, Menglong SU. Research on the NDP-constraint online scheduling of jobs have agreeable processing times and delivery times[J]. Operations Research Transactions, 2024, 28(4): 18-28.

参考文献 15

1	唐国春, 张峰, 罗守成, 等. 现代排序论[M]. 上海: 上海科学普及出版社, 2003.
2	万国华. 排序与调度的理论、模型和算法[M]. 北京: 清华大学出版社, 2019.
3	Blazewicz J , Ecker K , Pesch E , et al. Handbook on Scheduling-From Theory to Practice[M]. Switzerland: Springer Nature, 2019.
4	Yuan J J , Ng C T , Cheng T C E . Scheduling with release dates and preemption to minimize multiple max-form objective functions[J]. European Journal of Operational Research, 2020, 280, 860- 875. doi: 10.1016/j.ejor.2019.07.072
5	Baker K R . Introduction to Sequencing and Scheduling[M]. New York: John Wiley & Sons, 1974.
6	Hoogeveen H , Potts C N , Woeginger G J . Online scheduling on a single machine: Maximizing the number of early jobs[J]. Operations Research Letters, 2000, 27, 193- 196. doi: 10.1016/S0167-6377(00)00061-4
7	Keskinocak P. Online algorithms with lookahead: A survey [Z]. ISYE working paper, 1999.
8	Ma R , Guo S N , Miao C X . A semi-online algorithm and its competitive analysis for parallel-machine scheduling problem with rejection[J]. Applied Mathematics and Computation, 2021, 392, 125670. doi: 10.1016/j.amc.2020.125670
9	Li W J , Yuan J J . Single-machine online scheduling of jobs with non-delayed processing constraint[J]. Journal of Combinatorial Optimization, 2021, 41, 830- 843. doi: 10.1007/s10878-021-00722-4
10	Graham R L , Lawer E L , Lenstra J K . Optimization and approximation in deterministic sequencing and scheduling[J]. Annals of Discrete Mathematics, 1979, 5, 287- 326.
11	胡觉亮, 张玮虹, 蒋义伟. 生产和运输时间具有一致性的单机在线最优算法[J]. 浙江理工大学学报, 2010, 27, 830- 834.
12	Liu H L , Lu X W , Li W J . A best possible online algorithm for parallel batch scheduling with delivery times and limited restart[J]. Optimization Letters, 2021, 15, 1155- 1173. doi: 10.1007/s11590-020-01618-8
13	Hoogeveen H , Vestjens A P A . A best possible deterministic on-line algorithm for minimizing maximum delivery time on a single machine[J]. SIAM Journal on Discrete Mathematics, 2000, 13, 56- 63. doi: 10.1137/S0895480196296823
14	Tian J , Fu R Y , Yuan J J . A best on-line algorithm for single machine scheduling with small delivery times[J]. Theoretical Computer Science, 2008, 393, 287- 293. doi: 10.1016/j.tcs.2007.11.006
15	Liu M , Chu C B , Xu Y F , et al. An optimal online algorithm for single machine scheduling with bounded delivery times[J]. European Journal of Operational Research, 2010, 201, 693- 700. doi: 10.1016/j.ejor.2009.03.028

[1]	焦成文. 具有线性前瞻区间的单机平行批在线排序[J]. 运筹学学报（中英文）, 2024, 28(4): 111-116.
[2]	徐娟年, 马冉, 韩雯雯, 张玉忠. 工件权重带限制的最小化最大加权完工时间的单机在线排序问题[J]. 运筹学学报（中英文）, 2024, 28(2): 71-80.
[3]	代宇波, 段懿红, 刘龙城, 王子豪. 一类一维在线单位聚类问题的随机近似算法[J]. 运筹学学报, 2022, 26(3): 143-150.
[4]	李文杰, 李钰晶, 刘海玲. 工件的释放时间和加工时间具有一致性的单机在线排序问题研究[J]. 运筹学学报, 2022, 26(2): 55-63.
[5]	王银玲, 韩鑫, 邵欣欣. 关于带运输的单机调度在线问题的研究[J]. 运筹学学报, 2022, 26(1): 125-133.
[6]	王利博, 李文华, 余丹. 单机上带有可变前瞻区间的分批在线排序问题[J]. 运筹学学报, 2022, 26(1): 134-140.
[7]	姜晓燕, 帅天平. 两台恒速机上的MapReduce排序算法研究[J]. 运筹学学报, 2020, 24(3): 57-66.
[8]	张玉忠. 工件可拒绝排序问题综述[J]. 运筹学学报, 2020, 24(2): 111-130.
[9]	刘明熹, 甘国华, 程郁琨, 肖琳, 刘帅, 房勇. 区块链共识机制的发展现状与展望[J]. 运筹学学报, 2020, 24(1): 23-39.
[10]	李文华, 翟威娜, 柴幸, 高超. 具有两个不相容工件族单位工件的有界分批在线排序问题[J]. 运筹学学报, 2019, 23(4): 105-110.
[11]	薛娟, 高红伟, 姜辉, 周允旭. 基于时隙ALOHA协议的数据传输二人随机博弈模型[J]. 运筹学学报, 2019, 23(4): 45-58.
[12]	张国川, 陈林. 负载均衡问题[J]. 运筹学学报, 2019, 23(3): 1-14.
[13]	彭南南, 张玉忠, 柏庆国, 王成飞. 工件满足一致性的同类机在线分批排序问题[J]. 运筹学学报, 2019, 23(1): 111-118.
[14]	闵啸，朱俊蕾，刘静. 两台带服务等级的可拒绝同型机排序问题的在线算法[J]. 运筹学学报, 2018, 22(3): 117-124.
[15]	唐静静, 田英杰. 基于间隔迁移的多视角支持向量机[J]. 运筹学学报, 2018, 22(3): 1-14.

加工时间与运输时间具有一致性的单机NDP约束在线排序问题研究

Research on the NDP-constraint online scheduling of jobs have agreeable processing times and delivery times

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献 15

相关文章 15

编辑推荐

Metrics

本文评价