American Institute of Mathematical Sciences

Advanced
November  2021, 17(6): 3551-3558. doi: 10.3934/jimo.2020132

Research on the parallel–batch scheduling with linearly lookahead model

Chengwen Jiao , and  Qi Feng

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

* Corresponding author: Chengwen Jiao

Received  April 2020 Revised  June 2020 Published  November 2021 Early access  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} $.

Keywords: Online scheduling, parallel batch, linearly lookahead, makespan, maximum flowtime, competitive ratio.
Mathematics Subject Classification: Primary: 90B35; Secondary: 90B36.
Citation: Chengwen Jiao, Qi Feng. Research on the parallel–batch scheduling with linearly lookahead model. Journal of Industrial & Management Optimization, 2021, 17 (6) : 3551-3558. doi: 10.3934/jimo.2020132
References:
[1]

X. T. Deng, C. 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. Li, J. J. Yuan, J. 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. Li, Z. 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. Liu, X. 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. Tian, T. C. E. Cheng, C. 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. Zhang, X. 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. Zheng, Y. 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. Deng, C. 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. Li, J. J. Yuan, J. 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. Li, Z. 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. Liu, X. 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. Tian, T. C. E. Cheng, C. 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. Zhang, X. 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. Zheng, Y. 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]

Zhichao Geng, Jinjiang Yuan. Scheduling family jobs on an unbounded parallel-batch machine to minimize makespan and maximum flow time. Journal of Industrial & Management Optimization, 2018, 14 (4) : 1479-1500. doi: 10.3934/jimo.2018017
[2]

Ran Ma, Jiping Tao. An improved 2.11-competitive algorithm for online scheduling on parallel machines to minimize total weighted completion time. Journal of Industrial & Management Optimization, 2018, 14 (2) : 497-510. doi: 10.3934/jimo.2017057
[3]

Leiyang Wang, Zhaohui Liu. Heuristics for parallel machine scheduling with batch delivery consideration. Journal of Industrial & Management Optimization, 2014, 10 (1) : 259-273. doi: 10.3934/jimo.2014.10.259
[4]

Jiping Tao, Ronghuan Huang, Tundong Liu. A $2.28$-competitive algorithm for online scheduling on identical machines. Journal of Industrial & Management Optimization, 2015, 11 (1) : 185-198. doi: 10.3934/jimo.2015.11.185
[5]

Zhao-Hong Jia, Ting-Ting Wen, Joseph Y.-T. Leung, Kai Li. Effective heuristics for makespan minimization in parallel batch machines with non-identical capacities and job release times. Journal of Industrial & Management Optimization, 2017, 13 (2) : 977-993. doi: 10.3934/jimo.2016057
[6]

Chengxin Luo. Single machine batch scheduling problem to minimize makespan with controllable setup and jobs processing times. Numerical Algebra, Control & Optimization, 2015, 5 (1) : 71-77. doi: 10.3934/naco.2015.5.71
[7]

Jiping Tao, Zhijun Chao, Yugeng Xi. A semi-online algorithm and its competitive analysis for a single machine scheduling problem with bounded processing times. Journal of Industrial & Management Optimization, 2010, 6 (2) : 269-282. doi: 10.3934/jimo.2010.6.269
[8]

Yuzhong Zhang, Chunsong Bai, Qingguo Bai, Jianteng Xu. Duplicating in batch scheduling. Journal of Industrial & Management Optimization, 2007, 3 (4) : 685-692. doi: 10.3934/jimo.2007.3.685
[9]

Cuixia Miao, Yuzhong Zhang. Scheduling with step-deteriorating jobs to minimize the makespan. Journal of Industrial & Management Optimization, 2019, 15 (4) : 1955-1964. doi: 10.3934/jimo.2018131
[10]

Xianzhao Zhang, Dachuan Xu, Donglei Du, Cuixia Miao. Approximate algorithms for unrelated machine scheduling to minimize makespan. Journal of Industrial & Management Optimization, 2016, 12 (2) : 771-779. doi: 10.3934/jimo.2016.12.771
[11]

Ganggang Li, Xiwen Lu. Two-machine scheduling with periodic availability constraints to minimize makespan. Journal of Industrial & Management Optimization, 2015, 11 (2) : 685-700. doi: 10.3934/jimo.2015.11.685
[12]

Lili Ding, Xinmin Liu, Yinfeng Xu. Competitive risk management for online Bahncard problem. Journal of Industrial & Management Optimization, 2010, 6 (1) : 1-14. doi: 10.3934/jimo.2010.6.1
[13]

Min Ji, Xinna Ye, Fangyao Qian, T.C.E. Cheng, Yiwei Jiang. Parallel-machine scheduling in shared manufacturing. Journal of Industrial & Management Optimization, 2022, 18 (1) : 681-691. doi: 10.3934/jimo.2020174
[14]

Jiayu Shen, Yuanguo Zhu. An uncertain programming model for single machine scheduling problem with batch delivery. Journal of Industrial & Management Optimization, 2019, 15 (2) : 577-593. doi: 10.3934/jimo.2018058
[15]

P. Liu, Xiwen Lu. Online scheduling of two uniform machines to minimize total completion times. Journal of Industrial & Management Optimization, 2009, 5 (1) : 95-102. doi: 10.3934/jimo.2009.5.95
[16]

Donglei Du, Xiaoyue Jiang, Guochuan Zhang. Optimal preemptive online scheduling to minimize lp norm on two processors. Journal of Industrial & Management Optimization, 2005, 1 (3) : 345-351. doi: 10.3934/jimo.2005.1.345
[17]

Zhenhuan Yang, Yiming Ying, Qilong Min. Online optimization for residential PV-ESS energy system scheduling. Mathematical Foundations of Computing, 2019, 2 (1) : 55-71. doi: 10.3934/mfc.2019005
[18]

Hongtruong Pham, Xiwen Lu. The inverse parallel machine scheduling problem with minimum total completion time. Journal of Industrial & Management Optimization, 2014, 10 (2) : 613-620. doi: 10.3934/jimo.2014.10.613
[19]

Alireza Goli, Taha Keshavarz. Just-in-time scheduling in identical parallel machine sequence-dependent group scheduling problem. Journal of Industrial & Management Optimization, 2021  doi: 10.3934/jimo.2021124
[20]

Radu Ioan Boţ, Christopher Hendrich. Solving monotone inclusions involving parallel sums of linearly composed maximally monotone operators. Inverse Problems & Imaging, 2016, 10 (3) : 617-640. doi: 10.3934/ipi.2016014

2020 Impact Factor: 1.801

Tools

Metrics

  • PDF downloads (260)
  • HTML views (549)
  • Cited by (0)

Other articles
by authors

[Back to Top]

Copyright © 2022 American Institute of Mathematical Sciences | Privacy Policy