• 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]

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]

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

[12]

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

[13]

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

[14]

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

[15]

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

[16]

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

[17]

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

[18]

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

[19]

Omer Faruk Yilmaz, Mehmet Bulent Durmusoglu. A performance comparison and evaluation of metaheuristics for a batch scheduling problem in a multi-hybrid cell manufacturing system with skilled workforce assignment. Journal of Industrial & Management Optimization, 2018, 14 (3) : 1219-1249. doi: 10.3934/jimo.2018007

[20]

Tao Zhang, W. Art Chaovalitwongse, Yue-Jie Zhang, P. M. Pardalos. The hot-rolling batch scheduling method based on the prize collecting vehicle routing problem. Journal of Industrial & Management Optimization, 2009, 5 (4) : 749-765. doi: 10.3934/jimo.2009.5.749

2019 Impact Factor: 1.366

Metrics

  • PDF downloads (40)
  • HTML views (109)
  • Cited by (0)

Other articles
by authors

[Back to Top]