Research on the parallel–batch scheduling with linearly lookahead model

Previous Article
Incentive contract design for supplier switching with considering learning effect
JIMO Home
This Issue
Next Article
Continuity, differentiability and semismoothness of generalized tensor functions

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

Abstract
Full Text(HTML)
Related Papers
Under a Creative Commons license

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 and 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.
[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. 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.
[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.
[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.
[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. 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.
[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.
[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. 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.

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

[1]	Zhichao Geng, Jinjiang Yuan. Scheduling family jobs on an unbounded parallel-batch machine to minimize makespan and maximum flow time. Journal of Industrial and 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 and 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 and 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 and 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 and 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 and 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 and 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 and 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 and 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 and 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 and 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 and 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 and 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 and 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 and 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 and 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 and Management Optimization, 2014, 10 (2) : 613-620. doi: 10.3934/jimo.2014.10.613
[19]	Radu Ioan Boţ, Christopher Hendrich. Solving monotone inclusions involving parallel sums of linearly composed maximally monotone operators. Inverse Problems and Imaging, 2016, 10 (3) : 617-640. doi: 10.3934/ipi.2016014
[20]	Alireza Goli, Taha Keshavarz. Just-in-time scheduling in identical parallel machine sequence-dependent group scheduling problem. Journal of Industrial and Management Optimization, 2021 doi: 10.3934/jimo.2021124

2021 Impact Factor: 1.411

Tools

Metrics

Other articles
by authors

on AIMS
Chengwen Jiao Qi Feng
on Google Scholar
Chengwen Jiao Qi Feng

2021 Impact Factor: 1.411

Tools

Article outline

2021 Impact Factor: 1.411

Tools

Metrics

Other articles
by authors

on AIMS
Chengwen Jiao Qi Feng
on Google Scholar
Chengwen Jiao Qi Feng

[Back to Top]