单机上带有可变前瞻区间的分批在线排序问题

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

运筹学学报 ›› 2022, Vol. 26 ›› Issue (1): 134-140.doi: 10.15960/j.cnki.issn.1007-6093.2022.01.010

• • 上一篇

单机上带有可变前瞻区间的分批在线排序问题

王利博¹, 李文华¹^,*(), 余丹¹

1. 郑州大学数学与统计学院, 河南郑州 450001

收稿日期:2021-05-10 出版日期:2022-03-15 发布日期:2022-03-14
通讯作者: 李文华 E-mail:liwenhua@zzu.edu.cn
作者简介:李文华 E-mail: liwenhua@zzu.edu.cn
基金资助:
国家自然科学基金(11971443);国家自然科学基金(11771406)

Online scheduling on single batch machine with variable lookahead interval

Libo WANG¹, Wenhua LI¹^,*(), Dan YU¹

1. School of Mathematics and Statistics, Zhengzhou University, Zhengzhou 450001, Henan, China

Received:2021-05-10 Online:2022-03-15 Published:2022-03-14
Contact: Wenhua LI E-mail:liwenhua@zzu.edu.cn

摘要/Abstract

摘要：

本文研究单台无界平行批处理机上带有可变前瞻区间的在线排序问题。工件按时在线到达，目标是最小化时间表长。在时刻$t$，在线算法能够预见到$（t，t+\Delta（t）]$内到达工件的信息，这里前瞻区间的长度$\Delta（t）=\beta p_{\max}（t）$并非定长，其中$p_{\max}（t）$表示在$t$时刻及之前到达工件的最大加工时长，$\beta\in（0，1）$是常数。本文对于工件加工时长的一般情形，给出了当 0<β≤1/6 时最好可能的在线算法；对于工件加工时长被限制在一个区间的情形，给出了当 0<β<1 时最好可能的在线算法。

关键词: 分批排序, 在线算法, 前瞻区间, 时间表长, 竞争比

Abstract:

This paper investigates the online scheduling on an unbounded parallel-batch machine with variable lookahead interval to minimize makespan. Online means that jobs arrive over time. At any time $t$, an online algorithm can foresee the information of the jobs arriving in $(t, t+\Delta(t)]$, where $\Delta(t)=\beta p_{\max}(t)$ is the length of the lookahead interval which is not invariable, $p_{\max}(t)$ is the maximum processing time of the jobs arriving at or before $t$ and $\beta\in(0, 1)$ is a constant. On the general case of processing time, we give an online algorithm which is the best possible for 0<β≤1/6. When the processing times of all jobs are restricted in an interval, we give the best possible online algorithm for 0<β<1.

Key words: batch scheduling, online algorithm, lookahead interval, makespan, competitive ratio

中图分类号:

O221.2

王利博, 李文华, 余丹. 单机上带有可变前瞻区间的分批在线排序问题[J]. 运筹学学报, 2022, 26(1): 134-140.

Libo WANG, Wenhua LI, Dan YU. Online scheduling on single batch machine with variable lookahead interval[J]. Operations Research Transactions, 2022, 26(1): 134-140.

参考文献 13

1	Zhang G C , Cai X Q , Wong C K . On-line algorithms for minimizing makespan on batch processing machines[J]. Naval Research Logistics, 2001, 48, 241- 258. doi: 10.1002/nav.5
2	Tian J , Cheng T C E , Ng C T , et al. Online scheduling on unbounded parallel-batch machines to minimize the makespan[J]. Information Processing Letters, 2009, 109, 1211- 1215. doi: 10.1016/j.ipl.2009.08.008
3	Liu P H , Lu X W , Fang Y . A best possible deterministic on-line algorithm for minimizing makespan on parallel batch machines[J]. Journal of Scheduling, 2012, 15, 77- 81. doi: 10.1007/s10951-009-0154-4
4	Tian J , Fu R Y , Yuan J J . Online over time scheduling on parallel-batch machines: A survey[J]. Journal of the Operations Research Society of China, 2014, 2, 445- 454. doi: 10.1007/s40305-014-0060-0
5	Li W H , Zhang Z K , Yang S F . Online algorithms for scheduling unit length jobs on parallelbatch machines with lookahead[J]. Information Processing Letters, 2012, 112, 292- 297. doi: 10.1016/j.ipl.2012.01.002
6	杨素芳, 李文华. 具有前瞻区间的两个工件组单机在线排序问题[J]. 运筹学学报, 2012, 16, 115- 120.
7	Li W H , Yuan J J , Yang S F . Online scheduling of incompatible unit-length job families with lookahead[J]. Theoretical Computer Science, 2014, 543, 120- 125. doi: 10.1016/j.tcs.2014.05.024
8	李文华, 柴幸, 袁航, 等. 平行机上带有前瞻区间的不相容工件组在线排序问题[J]. 运筹学学报, 2015, 19, 121- 126.
9	Jiao C W , Yuan J J , Feng Q . Online algorithms for scheduling unit length jobs on unbounded parallel-batch machines with linearly lookahead[J]. Asia-Pacific Journal of Operational Research, 2019, 36, 1950024. doi: 10.1142/S0217595919500246
10	Mandelbaum M , Shabtay D . Scheduling unit length jobs on parallel machines with lookahead information[J]. Journal of Scheduling, 2011, 14, 335- 350. doi: 10.1007/s10951-010-0192-y
11	Chen C , Zhang H L , Xu Y F . Online machine minimization with lookahead[J]. Journal of Combinatorial Optimization, 2020, doi: 10.1007/s10878-020-00633-w
12	Poon C K , Yu W C . A flexible on-line scheduling algorithm for batch machine with infinite capacity[J]. Annals of Operations Research, 2005, 133, 175- 181. doi: 10.1007/s10479-004-5031-0
13	Fang Y , Liu P H , Lu X W . Optimal on-line algorithms for one batch machine with grouped processing time[J]. Journal of Combinatorial Optimization, 2011, 22, 509- 516. doi: 10.1007/s10878-010-9298-6

[1]	王银玲, 韩鑫, 邵欣欣. 关于带运输的单机调度在线问题的研究[J]. 运筹学学报, 2022, 26(1): 125-133.
[2]	姜晓燕, 帅天平. 两台恒速机上的MapReduce排序算法研究[J]. 运筹学学报, 2020, 24(3): 57-66.
[3]	张玉忠. 工件可拒绝排序问题综述[J]. 运筹学学报, 2020, 24(2): 111-130.
[4]	刘晓霞, 余山杉, 罗文昌. 工作有到达时间且拒绝工件总个数受限的单机平行分批排序问题的近似算法[J]. 运筹学学报, 2020, 24(1): 131-139.
[5]	李文华, 翟威娜, 柴幸, 高超. 具有两个不相容工件族单位工件的有界分批在线排序问题[J]. 运筹学学报, 2019, 23(4): 105-110.
[6]	张国川, 陈林. 负载均衡问题[J]. 运筹学学报, 2019, 23(3): 1-14.
[7]	彭南南, 张玉忠, 柏庆国, 王成飞. 工件满足一致性的同类机在线分批排序问题[J]. 运筹学学报, 2019, 23(1): 111-118.
[8]	赵晓成, 李大刚. 机器和工人都有加工资质约束的平行机排序问题研究[J]. 运筹学学报, 2018, 22(3): 99-108.
[9]	李英, 乔龙亮, 郑斐峰. 具有预知信息的集装箱码头泊位与岸桥联合调度在线模型[J]. 运筹学学报, 2018, 22(3): 28-36.
[10]	闵啸，朱俊蕾，刘静. 两台带服务等级的可拒绝同型机排序问题的在线算法[J]. 运筹学学报, 2018, 22(3): 117-124.
[11]	酒明珠, 高园, 原晋江. 工件可自由下线最小化总完工时间的平行分批排序问题[J]. 运筹学学报, 2018, 22(1): 32-41.
[12]	侯丽英. 具有服务等级的两台同型机实时在线排序[J]. 运筹学学报, 2016, 20(2): 49-58.
[13]	王成飞, 张玉忠. 提前预知信息的在线分批排序问题[J]. 运筹学学报, 2016, 20(1): 84-90.
[14]	李文华, 柴幸, 袁航, 杨素芳. 平行机上带有前瞻区间的不相容工件组在线排序问题[J]. 运筹学学报, 2015, 19(4): 121-126.
[15]	高强, 鲁习文. 带有拒绝的单机和同型机排序问题[J]. 运筹学学报, 2014, 18(4): 1-10.

单机上带有可变前瞻区间的分批在线排序问题

Online scheduling on single batch machine with variable lookahead interval

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献 13

相关文章 15

编辑推荐

Metrics

本文评价