Operations Research Transactions >
2022 , Vol. 26 >Issue 1: 134 - 140
DOI: https://doi.org/10.15960/j.cnki.issn.1007-6093.2022.01.010
Online scheduling on single batch machine with variable lookahead interval
Received date: 2021-05-10
Online published: 2022-03-14
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
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 . DOI: 10.15960/j.cnki.issn.1007-6093.2022.01.010
| 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. |
/
| 〈 |
|
〉 |