• Previous Article
    New M-eigenvalue intervals and application to the strong ellipticity of fourth-order partially symmetric tensors
  • JIMO Home
  • This Issue
  • Next Article
    Alliance strategy of construction and demolition waste recycling based on the modified shapley value under government regulation
doi: 10.3934/jimo.2020132

Research on the parallel–batch scheduling with linearly lookahead model

College of Science, Zhongyuan University of Technology, Zhengzhou, Henan 450007, China

* Corresponding author: Chengwen Jiao

Received  April 2020 Revised  June 2020 Published  August 2020

Fund Project: The author is supported by NSFC under grant number 11701595

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} $.

Citation: Chengwen Jiao, Qi Feng. Research on the parallel–batch scheduling with linearly lookahead model. Journal of Industrial & Management Optimization, doi: 10.3934/jimo.2020132
References:
[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.  Google Scholar

[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.  Google Scholar

[3]

P. Keskinocak, Online algorithms with lookahead: A survey, ISYE working paper, 1999. Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.   Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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. Google Scholar

[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.  Google Scholar

show all references

References:
[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.  Google Scholar

[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.  Google Scholar

[3]

P. Keskinocak, Online algorithms with lookahead: A survey, ISYE working paper, 1999. Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.   Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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. Google Scholar

[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.  Google Scholar

[1]

Yu Zhou, Xinfeng Dong, Yongzhuang Wei, Fengrong Zhang. A note on the Signal-to-noise ratio of $ (n, m) $-functions. Advances in Mathematics of Communications, 2020  doi: 10.3934/amc.2020117

[2]

Marco Ghimenti, Anna Maria Micheletti. Compactness results for linearly perturbed Yamabe problem on manifolds with boundary. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020453

[3]

Giuseppina Guatteri, Federica Masiero. Stochastic maximum principle for problems with delay with dependence on the past through general measures. Mathematical Control & Related Fields, 2020  doi: 10.3934/mcrf.2020048

[4]

Youming Guo, Tingting Li. Optimal control strategies for an online game addiction model with low and high risk exposure. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020347

[5]

Sihem Guerarra. Maximum and minimum ranks and inertias of the Hermitian parts of the least rank solution of the matrix equation AXB = C. Numerical Algebra, Control & Optimization, 2021, 11 (1) : 75-86. doi: 10.3934/naco.2020016

2019 Impact Factor: 1.366

Article outline

[Back to Top]