Advanced Search
Article Contents
Article Contents

Research on the parallel–batch scheduling with linearly lookahead model

  • * Corresponding author: Chengwen Jiao

    * Corresponding author: Chengwen Jiao 
The author is supported by NSFC under grant number 11701595
Abstract Full Text(HTML) Related Papers Cited by
  • In this paper, we consider the new online scheduling model with linear lookahead intervals, which has the character that at any time $ t $, one can foresee the jobs that will coming in the time interval $ (t, \lambda t+\beta ] $ with $ \lambda\geq1, \beta\geq 0 $. We consider online scheduling of unit length jobs on $ m $ identical parallel-batch machines under this new lookahead model to minimize the maximum flowtime and the makespan, respectively. We give some lower bounds for these problems with the batch capacity $ b = \infty $ and $ b<\infty $, respectively. And for the bounded model to minimize makespan, we give an online algorithm with competitive ratio $ 1+\alpha $ for $ 1\leq \lambda <4/3, 0\leq \beta\leq \frac{4-3\lambda}{6} $ and $ \frac{3}{2} $ for $ \lambda\geq1, 0\leq\beta<1 $, where $ \alpha $ is the positive root of $ \lambda\alpha^2+(\lambda+\beta)\alpha+\beta-1 = 0 $. The online algorithm is best possible when $ 1\leq \lambda <4/3, 0\leq \beta\leq \frac{4-3\lambda}{6} $.

    Mathematics Subject Classification: Primary: 90B35; Secondary: 90B36.


    \begin{equation} \\ \end{equation}
  • 加载中
  • [1] X. T. DengC. K. Poon and Y. Z. Zhang, Approximation algorithms in batch processing, Journal of Combinatorial Optimization, 7 (2003), 247-257.  doi: 10.1023/A:1027316504440.
    [2] C. W. Jiao, J. J. Yuan and Q. Feng, Online algorithms for scheduling unit length jobs on unbounded parallel-batch machines with linearly lookahead, Asia-Pacific Journal of Operational Research, 36 (2019), 1950024, 8 pp. doi: 10.1142/S0217595919500246.
    [3] P. Keskinocak, Online algorithms with lookahead: A survey, ISYE working paper, 1999.
    [4] W. J. LiJ. J. YuanJ. F. Cao and H. L. Bu, Online scheduling of unit length jobs on a batching machine to maximize the number of early jobs with lookahead, Theoretical Computer Science, 410 (2009), 5182-5187.  doi: 10.1016/j.tcs.2009.07.056.
    [5] W. H. LiZ. K. Zhang and S. F. Yang, Online algorithms for scheduling unit length jobs on parallel-batch machines with lookahead, Information Processing Letters, 112 (2012), 292-297.  doi: 10.1016/j.ipl.2012.01.002.
    [6] P. H. LiuX. W. Lu and Y. Fang, A best possible deterministic on-line algorithm for minimizing makespan on parallel batch machines, Journal of Scheduling, 15 (2012), 77-81.  doi: 10.1007/s10951-009-0154-4.
    [7] M. Mandelbaum and D. Shabtay, Scheduling unit length jobs on parallel machines with lookahead information, Journal of Scheduling, 14 (2011), 335-350.  doi: 10.1007/s10951-010-0192-y.
    [8] W. Mao and R. K. Kincaid, A lookahead heuristic for scheduling jobs with release dates on a single machine, Computers and Operations Research, 21 (1994), 1041-1050. 
    [9] C. K. Poon and W. C. Yu, On-line scheduling algorithms for a batch machine with finite capacity, Journal of Combinatorial Optimization, 9 (2005), 167-186.  doi: 10.1007/s10878-005-6855-5.
    [10] J. TianT. C. E. ChengC. T. Ng and J. J. Yuan, Online scheduling on unbound parallel-batch machines to minimize the makespan, Information Processing Letters, 109 (2009), 1211-1215.  doi: 10.1016/j.ipl.2009.08.008.
    [11] G. C. ZhangX. Q. Cai and C. K. Wong, Online algorithms for minimizing makespan on batch processing machines, Naval Research Logistics, 48 (2001), 241-258.  doi: 10.1002/nav.5.
    [12] G. C. Zhang, X. Q. Cai and C. K. Wong, Optimal online algorithms for scheduling on parallel batch processing machines, IIE Transactions, 35 (2003), 175-181.
    [13] F. F. ZhengY. F. Xu and E. Zhang, How much can lookahead help in online single machine scheduling, Information Processing Letters, 106 (2008), 70-74.  doi: 10.1016/j.ipl.2007.10.008.
  • 加载中
Open Access Under a Creative Commons license

Article Metrics

HTML views(1090) PDF downloads(360) Cited by(0)

Access History

Other Articles By Authors



    DownLoad:  Full-Size Img  PowerPoint