• Previous Article
    Solutions and characterizations under multicriteria management systems
  • 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]

Jian Yang, Bendong Lou. Traveling wave solutions of competitive models with free boundaries. Discrete & Continuous Dynamical Systems - B, 2014, 19 (3) : 817-826. doi: 10.3934/dcdsb.2014.19.817

[2]

Marco Ghimenti, Anna Maria Micheletti. Compactness results for linearly perturbed Yamabe problem on manifolds with boundary. Discrete & Continuous Dynamical Systems - S, 2021, 14 (5) : 1757-1778. doi: 10.3934/dcdss.2020453

[3]

Shan-Shan Lin. Due-window assignment scheduling with learning and deterioration effects. Journal of Industrial & Management Optimization, 2021  doi: 10.3934/jimo.2021081

[4]

Jumpei Inoue, Kousuke Kuto. On the unboundedness of the ratio of species and resources for the diffusive logistic equation. Discrete & Continuous Dynamical Systems - B, 2021, 26 (5) : 2441-2450. doi: 10.3934/dcdsb.2020186

[5]

Muberra Allahverdi, Harun Aydilek, Asiye Aydilek, Ali Allahverdi. A better dominance relation and heuristics for Two-Machine No-Wait Flowshops with Maximum Lateness Performance Measure. Journal of Industrial & Management Optimization, 2021, 17 (4) : 1973-1991. doi: 10.3934/jimo.2020054

[6]

Xu Zhang, Xiang Li. Modeling and identification of dynamical system with Genetic Regulation in batch fermentation of glycerol. Numerical Algebra, Control & Optimization, 2015, 5 (4) : 393-403. doi: 10.3934/naco.2015.5.393

[7]

Xiaohong Li, Mingxin Sun, Zhaohua Gong, Enmin Feng. Multistage optimal control for microbial fed-batch fermentation process. Journal of Industrial & Management Optimization, 2021  doi: 10.3934/jimo.2021040

[8]

Yi Peng, Jinbiao Wu. Analysis of a batch arrival retrial queue with impatient customers subject to the server disasters. Journal of Industrial & Management Optimization, 2021, 17 (4) : 2243-2264. doi: 10.3934/jimo.2020067

[9]

Brandy Rapatski, James Yorke. Modeling HIV outbreaks: The male to female prevalence ratio in the core population. Mathematical Biosciences & Engineering, 2009, 6 (1) : 135-143. doi: 10.3934/mbe.2009.6.135

[10]

Mats Gyllenberg, Jifa Jiang, Lei Niu, Ping Yan. On the classification of generalized competitive Atkinson-Allen models via the dynamics on the boundary of the carrying simplex. Discrete & Continuous Dynamical Systems, 2018, 38 (2) : 615-650. doi: 10.3934/dcds.2018027

[11]

Mehmet Duran Toksari, Emel Kizilkaya Aydogan, Berrin Atalay, Saziye Sari. Some scheduling problems with sum of logarithm processing times based learning effect and exponential past sequence dependent delivery times. Journal of Industrial & Management Optimization, 2021  doi: 10.3934/jimo.2021044

[12]

Longxiang Fang, Narayanaswamy Balakrishnan, Wenyu Huang. Stochastic comparisons of parallel systems with scale proportional hazards components equipped with starting devices. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2021004

[13]

Xiaomao Deng, Xiao-Chuan Cai, Jun Zou. A parallel space-time domain decomposition method for unsteady source inversion problems. Inverse Problems & Imaging, 2015, 9 (4) : 1069-1091. doi: 10.3934/ipi.2015.9.1069

[14]

Saeed Assani, Muhammad Salman Mansoor, Faisal Asghar, Yongjun Li, Feng Yang. Efficiency, RTS, and marginal returns from salary on the performance of the NBA players: A parallel DEA network with shared inputs. Journal of Industrial & Management Optimization, 2021  doi: 10.3934/jimo.2021053

[15]

Wenjuan Zhao, Shunfu Jin, Wuyi Yue. A stochastic model and social optimization of a blockchain system based on a general limited batch service queue. Journal of Industrial & Management Optimization, 2021, 17 (4) : 1845-1861. doi: 10.3934/jimo.2020049

[16]

Wen-Bin Yang, Yan-Ling Li, Jianhua Wu, Hai-Xia Li. Dynamics of a food chain model with ratio-dependent and modified Leslie-Gower functional responses. Discrete & Continuous Dynamical Systems - B, 2015, 20 (7) : 2269-2290. doi: 10.3934/dcdsb.2015.20.2269

[17]

Qian Cao, Yongli Cai, Yong Luo. Nonconstant positive solutions to the ratio-dependent predator-prey system with prey-taxis in one dimension. Discrete & Continuous Dynamical Systems - B, 2021  doi: 10.3934/dcdsb.2021095

[18]

Prabir Panja, Soovoojeet Jana, Shyamal kumar Mondal. Dynamics of a stage structure prey-predator model with ratio-dependent functional response and anti-predator behavior of adult prey. Numerical Algebra, Control & Optimization, 2021, 11 (3) : 391-405. doi: 10.3934/naco.2020033

2019 Impact Factor: 1.366

Metrics

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

Other articles
by authors

[Back to Top]