Online scheduling on a single parallel-batch machine with linear lookahead

Expand
  • 1. School of Mathematics and Information Science, Zhongyuan University of Technology, Zhengzhou 450007, Henan, China

Received date: 2024-01-24

  Online published: 2024-12-20

Copyright

, 2024, All rights reserved, without authorization

Abstract

The online scheduling with lookahead is a very important scheduling model, which has the character that at any time, it can foresee the information of some jobs that will coming in the near feature. The information can be the number of jobs that can foresee, or the jobs that will come in some time intervals. The $LK_\beta$ is one of the models, in which the length of the time interval that can foresee is fixed with value $\beta, \beta\geq0$. This paper considers the online scheduling on a single parallel-batch machine with linear lookahead. The main character of the linear lookahead model is that at any time $t$, one can foresee the jobs that will come in the time interval $(t, \lambda t+\beta]$ with $\lambda\geq1, \beta\geq0$. The length of the interval $(t, \lambda t+\beta]$ is changed as the time $t$ going on, having the tend of steady growth. When $\lambda=1$, it is in fact the $LK_\beta$ lookahead model. In this paper, the objective is to minimize the makespan. When the capacity of the batch is unbounded and the jobs arrive with no-decreasing processing times, for different values of $\lambda, \beta$, it gives optimal algorithm and best possible online algorithm, respectively.

Cite this article

Chengwen JIAO . Online scheduling on a single parallel-batch machine with linear lookahead[J]. Operations Research Transactions, 2024 , 28(4) : 111 -116 . DOI: 10.15960/j.cnki.issn.1007-6093.2024.04.010

References

1 MaoW,KincaidR K.A look-ahead heuristic for scheduling jobs with release dates on a single machine[J].Computers and Operations Research,1994,21,1041-1050.
2 MandelbaumM,ShabtayD.Scheduling unit length jobs on parallel machines with lookahead information[J].Journal of Scheduling,2011,14,335-350.
3 Coleman B, Mao W. Lookahead scheduling for unrelated machines[C]//Proceedings of the 7th International Conference on Computer Science and Informatics, 2003: 397-400.
4 ZhengF F,XuY F,ZhangE.How much can lookahead help in online single machine scheduling[J].Information Processing Letters,2008,106,70-74.
5 ZhengF F,ChengY X,LiuM,et al.Online interval scheduling on a single machine with finite lookahead[J].Computers and Operations Research,2013,40,180-191.
6 LiW J,YuanJ J.An improved online algorithm for the online preemptive scheduling of equal-length intervals on a single machine with lookahead[J].Asia-Pacific Journal of Operational Research,2015,32,15500471-9.
7 LiW J,YuanJ J,CaoJ F,et al.Online scheduling of unit length jobs on a batching machine to maximize the number of early jobs with lookahead[J].Theoretical Computer Science,2009,410,5182-5187.
8 LiW H,ZhangZ K,YangS F.Online algorithms for scheduling unit length jobs on parallel-batch machines with lookahead[J].Information Processing Letters,2012,112,292-297.
9 LiW H,YuanJ J,YangS F.Online scheduling of incompatible unit-length job families with lookahead[J].Theoretical Computer Science,2014,543,120-125.
10 JiaoC W,YuanJ J,FengQ.Online algorithms for scheduling unit length jobs on unbounded parallel-batch machines with linearly lookahead[J].Asia-Pacific Journal of Operational Research,2019,36(5):1950024-1-8.
Outlines

/