-
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
Research on the parallel–batch scheduling with linearly lookahead model
College of Science, Zhongyuan University of Technology, Zhengzhou, Henan 450007, China |
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} $.
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
[Back to Top]