运筹学学报 >
2022 , Vol. 26 >Issue 1: 134 - 140
DOI: https://doi.org/10.15960/j.cnki.issn.1007-6093.2022.01.010
单机上带有可变前瞻区间的分批在线排序问题
收稿日期: 2021-05-10
网络出版日期: 2022-03-14
基金资助
国家自然科学基金(11971443);国家自然科学基金(11771406)
Online scheduling on single batch machine with variable lookahead interval
Received date: 2021-05-10
Online published: 2022-03-14
本文研究单台无界平行批处理机上带有可变前瞻区间的在线排序问题。工件按时在线到达,目标是最小化时间表长。在时刻$t$,在线算法能够预见到$(t,t+\Delta(t)]$内到达工件的信息,这里前瞻区间的长度$\Delta(t)=\beta p_{\max}(t)$并非定长,其中$p_{\max}(t)$表示在$t$时刻及之前到达工件的最大加工时长,$\beta\in(0,1)$是常数。本文对于工件加工时长的一般情形,给出了当 0<β≤1/6 时最好可能的在线算法;对于工件加工时长被限制在一个区间的情形,给出了当 0<β<1 时最好可能的在线算法。
王利博, 李文华, 余丹 . 单机上带有可变前瞻区间的分批在线排序问题[J]. 运筹学学报, 2022 , 26(1) : 134 -140 . DOI: 10.15960/j.cnki.issn.1007-6093.2022.01.010
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
| 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. |
| 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. |
| 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. |
| 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. |
| 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. |
| 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. |
| 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. |
| 10 | Mandelbaum M , Shabtay D . Scheduling unit length jobs on parallel machines with lookahead information[J]. Journal of Scheduling, 2011, 14, 335- 350. |
| 11 | Chen C , Zhang H L , Xu Y F . Online machine minimization with lookahead[J]. Journal of Combinatorial Optimization, 2020, |
| 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. |
| 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. |
/
| 〈 |
|
〉 |