关于带运输的单机调度在线问题的研究

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

运筹学学报 ›› 2022, Vol. 26 ›› Issue (1): 125-133.doi: 10.15960/j.cnki.issn.1007-6093.2022.01.009

所属专题：机器学习与优化专辑

关于带运输的单机调度在线问题的研究

王银玲^1*^,*(), 韩鑫², 邵欣欣³

1. 大连理工大学数学科学学院, 辽宁大连, 116024
2. 大连理工大学软件学院, 辽宁大连, 116024
3. 大连东软信息学院软件学院, 辽宁大连, 116023

收稿日期:2021-06-04 出版日期:2022-03-15 发布日期:2022-03-14
通讯作者: 王银玲 E-mail:yinling_wang@foxmail.com
作者简介:王银铃 E-mail: yinling_wang@foxmail.com
基金资助:
国家自然科学基金青年基金(11701062)

Online single machine scheduling problem with transportation

Yinling WANG^1*^,*(), Xin HAN², Xinxin SHAO³

1. School of Mathematical Sciences, Dalian University of Technology, Dalian 116024, Liaoning, China
2. School of Software Technology, Dalian University of Technology, Dalian 116024, Liaoning, China
3. School of Software, Dalian Neusoft University of Information, Dalian 116023, Liaoning, China

Received:2021-06-04 Online:2022-03-15 Published:2022-03-14
Contact: Yinling WANG E-mail:yinling_wang@foxmail.com

摘要/Abstract

摘要：

本文研究了带运输机的单机在线调度问题。问题假设工件实时在线到达，系统中有一台运输机，该运输机每次最多运输$k$个工件，每个工件需要先在单机上完成加工，然后再被运输机运往目的地，问题的优化目标为最小化完工时间，即所有工件被加工完并且运往目的地的时间最短。针对该问题，作者研究了工件满足一致性条件的模型，并且基于贪心思想给出了竞争比为$\frac{\sqrt{5}+1}{2}$的在线算法，并且证明该算法是最优在线算法。

关键词: 运输机, 单机调度, 在线算法

Abstract:

This paper studies the single machine online scheduling problem with transporters. The problem assumes that the jobs arrive online over time, and there is only a single transporter in the system, which transports up to $k$ jobs each time. Each job needs to be processed on a single machine, and then transported to the destination by the transporter. The objective of the problem is to minimize the makespan, that is, the shortest time for all jobs to be processed and transported to the destination. For this problem, this paper studies the agreeable model, and proposes an online algorithm with the competitive ratio of $\frac{\sqrt{5}+1}{2}$ based on the greedy strategy, in the end, the algorithm is proved to be the optimal online algorithm.

Key words: transporter, single machine scheduling, online algorithm

中图分类号:

O157

王银玲, 韩鑫, 邵欣欣. 关于带运输的单机调度在线问题的研究[J]. 运筹学学报, 2022, 26(1): 125-133.

Yinling WANG, Xin HAN, Xinxin SHAO. Online single machine scheduling problem with transportation[J]. Operations Research Transactions, 2022, 26(1): 125-133.

1	Potts C N . Analysis of a Heuristic for one machine sequencing with release dates and delivery times[J]. Operations Research, 1980, 28 (6): 1436- 1441. doi: 10.1287/opre.28.6.1436
2	Hall L A , Shmoys D B . Jackson's rule for one-machine scheduling: making a good heuristic better[J]. Mathematics of Operations Research, 1992, 17 (1): 22- 35. doi: 10.1287/moor.17.1.22
3	Woeginger G J . Heuristics for parallel machine scheduling with delivery times[J]. ACTA Informatica, 1994, 31 (6): 503- 512. doi: 10.1007/BF01213203
4	Chen Z . Scheduling and common due date assignment with earliness-tardiness penalties and batch delivery costs[J]. European Journal of Operational Research, 1996, 93 (1): 49- 60. doi: 10.1016/0377-2217(95)00133-6
5	Cheng T , Gordon V S , Kovalyov M Y . Single machine scheduling with batch deliveries[J]. European Journal of Operational Research, 1996, 94 (2): 277- 283. doi: 10.1016/0377-2217(96)00127-0
6	Herrmann J W , Lee C Y . On scheduling to minimize earliness-tardiness and batch delivery costs with a common due date[J]. European Journal of Operational Research, 1993, 70 (3): 272- 288. doi: 10.1016/0377-2217(93)90239-J
7	Yuan J . A note on the complexity of single-machine scheduling with a common due date, earliness-tardiness, and batch delivery costs[J]. European Journal of Operational Research, 1996, 94 (1): 203- 205. doi: 10.1016/0377-2217(95)00168-9
8	Lee C Y , Chen Z . Machine scheduling with transportation considerations[J]. Journal of Scheduling, 2001, 4 (1): 3- 24. doi: 10.1002/1099-1425(200101/02)4:1<3::AID-JOS57>3.0.CO;2-D
9	Chang Y C , Lee C Y . Machine scheduling with job delivery coordination[J]. European Journal of Operational Research, 2004, 158 (2): 470- 487. doi: 10.1016/S0377-2217(03)00364-3
10	Lu L , Yuan J . Single machine scheduling with job delivery to minimize makespan[J]. Asia Pacific Journal of Operational Research, 2008, 25 (1): 1- 10. doi: 10.1142/S0217595908001596
11	Li G , Lu X . Approximation algorithms for the single-machine scheduling with a period of maintenance[J]. Optimization Letters, 2016, 10 (3): 543- 562. doi: 10.1007/s11590-015-0881-8
12	Hoogeveen J A , Vestjens A . Optimal on-line algorithms for single-machine scheduling[J]. Lecture Notes in Computer Science, 1999, 1084, 404- 414.
13	Anderson E J , Potts C N . Online scheduling of a single machine to minimize total weighted completion time[J]. Mathmatics of Operations Research, 2004, 29, 686- 697. doi: 10.1287/moor.1040.0092
14	Deng X , Poon C K , Zhang Y . Approximation Algorithms in Batch Processing[M]. Berlin: Springer, 2003.
15	Hoogeveen J A , Vestjens 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 (1): 56- 63. doi: 10.1137/S0895480196296823
16	Zhang G , Cai X , Wong C K . Online algorithms for minimizing makespan on batch processing machines[J]. Naval Research Logistics, 2010, 48 (3): 241- 258.
17	Lee C Y , Uzsoy R . Minimizing makespan on a single batch processing machine with dynamic job arrivals[J]. International Journal of Production Research, 1999, 37 (1): 219- 236. doi: 10.1080/002075499192020
18	Liu Z , Yu W . Scheduling one batch processor subject to job release dates[J]. Discrete Applied Mathematics, 2000, 103 (1-3): 129- 136.
19	Liu H , Yuan J , W Li . Online scheduling of equal length jobs on unbounded parallel batch processing machines with limited restart[J]. Journal of Combinatorial Optimization, 2016, 31 (4): 1609- 1622. doi: 10.1007/s10878-015-9844-3
20	Lu L , Zhang L . Competitive project scheduling on two unbounded parallel batch machines[J]. Journal of the Operations Research Society of China, 2017, 6 (3): 473- 483.
21	李文杰, 马冉. 最大化接收工件个数的在线分批排序问题研究[J]. 郑州大学学报(理学版), 2016, 2016 (2): 24- 28.
22	Lucier B, Menache I, Naor J, et al. Efficient online scheduling for deadline-sensitive jobs: extended abstract[C]//Proceedings of the ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2013: 305-314.
23	Azar Y, Kalp S I, Lucier B, et al. Truthful online scheduling with commitments[C]//Proceedings of the ACM Symposium on Economics and Computations (EC), 2015: 715-732.
24	Bansal N, Chan H L, Pruhs K. Competitive algorithms for due date scheduling[C]//Proceedings of the International Colloquium on Automata, Languages and Programming (ICALP), 2007: 28-39.
25	Baruah S K , Haritsa J R . Scheduling for over load in real time systems[J]. IEEE Transactions on Computers, 1997, 46 (9): 1034- 1039. doi: 10.1109/12.620484
26	Baruah S K, Haritsa J R, Sharma N. On-line scheduling to maximize task completions[C]//Proceedings of the IEEE Real-Time Systems Symposium (RTSS), 1994: 228-236.
27	Garay J A, Naor J, Yener B, Zhao P. On-line admission control and packet scheduling with interleaving[C]//Proceedings of the IEEE International Conference on Computer Communi cations (INFOCOM), 2002: 94-103.
28	Georgiadis L , Guerin R , Parekh A K . Optimal multiplexing on a single link: delay and buffer requirements[J]. IEEE Transactions on Information Theory, 1997, 43 (5): 1518- 1535. doi: 10.1109/18.623149
29	Goldwasser M H. Patience is a virtue: the effect of slack on competitiveness for admission control[C]//Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA), 1999: 396-405.
30	Im S, Moseley B. General profit scheduling and the power of migration on heterogeneous ma chines[C]//Proceedings of the ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2016: 165-173.
31	Liebeherr J , Wrege D E , Fer-rari D . Exact admission control for networks with a bounded delay service[J]. IEEE/ACM Transactions on Networking, 1996, 4 (6): 885- 901. doi: 10.1109/90.556345
32	Lucier B, Menache I, Naor J, et al. Efficient online scheduling for deadline-sensitive jobs: extended abstract[C]//Proceedings of the ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2013: 305-314.
33	Pruhs K, Stein C. How to schedule when you have to buy your energy[C]//Proceedings of the International Conference on Approximation Algorithms for Combinatorial Optimization Problems (APPROX), 2010: 352-365.
34	Schwiegelshohn C, Schwiegelshohn U. The power of migration for online slack scheduling[C]//Proceedings of the European Symposium of Algorithms (ESA), 2016: 1-17.
35	Chen L , Eberle F , Megow N . A general framework for handling commitment in online through put maximization[J]. Mathematical Programming, 2020, 183 (9): 215- 247.

[1]	靳凯媛, 郑斐峰, 刘明. 考虑订单类型和准备时间的批处理机在线调度模型研究[J]. 运筹学学报（中英文）, 2025, 29(4): 231-240.
[2]	夏倩, 张新功. 具有前瞻区间和不相容工件族的两台流水车间在线排序问题[J]. 运筹学学报（中英文）, 2025, 29(4): 103-111.
[3]	李娜, 马冉, 李龙, 张玉忠. 具有学习效应的预制构件生产调度研究[J]. 运筹学学报（中英文）, 2025, 29(1): 19-30.
[4]	李文杰, 杜智慧, 苏孟龙. 加工时间与运输时间具有一致性的单机NDP约束在线排序问题研究[J]. 运筹学学报（中英文）, 2024, 28(4): 18-28.
[5]	吴琼, 王长军. 基于拉格朗日松弛的产能共享讨价还价研究[J]. 运筹学学报（中英文）, 2024, 28(2): 93-102.
[6]	徐娟年, 马冉, 韩雯雯, 张玉忠. 工件权重带限制的最小化最大加权完工时间的单机在线排序问题[J]. 运筹学学报（中英文）, 2024, 28(2): 71-80.
[7]	代宇波, 段懿红, 刘龙城, 王子豪. 一类一维在线单位聚类问题的随机近似算法[J]. 运筹学学报, 2022, 26(3): 143-150.
[8]	李文杰, 李钰晶, 刘海玲. 工件的释放时间和加工时间具有一致性的单机在线排序问题研究[J]. 运筹学学报, 2022, 26(2): 55-63.
[9]	王利博, 李文华, 余丹. 单机上带有可变前瞻区间的分批在线排序问题[J]. 运筹学学报, 2022, 26(1): 134-140.
[10]	张国川, 陈林. 负载均衡问题[J]. 运筹学学报, 2019, 23(3): 1-14.
[11]	彭南南, 张玉忠, 柏庆国, 王成飞. 工件满足一致性的同类机在线分批排序问题[J]. 运筹学学报, 2019, 23(1): 111-118.
[12]	王成飞, 张玉忠. 提前预知信息的在线分批排序问题[J]. 运筹学学报, 2016, 20(1): 84-90.
[13]	高强, 鲁习文. 带有拒绝的单机和同型机排序问题[J]. 运筹学学报, 2014, 18(4): 1-10.
[14]	王成飞, 张玉忠, 柏庆国. 具有线性恶化效应的在线分批排序问题[J]. 运筹学学报, 2011, 15(3): 107-114.

关于带运输的单机调度在线问题的研究

Online single machine scheduling problem with transportation

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

相关文章 14

编辑推荐

Metrics

本文评价