Online scheduling on single batch machine with variable lookahead interval

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

Received date: 2021-05-10

  Online published: 2022-03-14

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.

Cite this article

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

References

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.
Outlines

/