On-line algorithms for incompatible job families on parallel  machines scheduling with lookahead

Expand
  • 1.School of Mathematics and Statistics, Zhengzhou University, Zhengzhou 450001,China; 2.College of Economics, Zhejiang University, Hangzhou 310027, China

Received date: 2014-12-01

  Online published: 2015-12-15

Abstract

 We consider the on-line scheduling of incompatible unit-length job families  on unbounded parallel-batch machines with lookahead when the number of
job families is equal to the number of machines. In this paper online means that jobs arrive over time. The objective is to minimize the makespan. In the lookahead model, at a time instant  t , an on-line algorithm can foresee the information of all jobs arriving in the time segment  (t,t+\beta). By incompatible job
families, we  mean that jobs from different families cannot be assigned together in the same batch. When \beta \geq 1, we provide an optimal online algorithm; When 0\leq \beta < 1, we give a best possible online algorithm of competitive ratio 1+\alpha, where \alpha is the positive root of the equation \alpha^{2}+(1+\beta) \alpha+\beta-1=0.  We also provide a new lower bound on the competitive ratio for dense-algorithms, and present a best possible dense-algorithm matching this lower bound.

Cite this article

LI Wenhua, CHAI Xing, YUAN Hang, YANG Sufang . On-line algorithms for incompatible job families on parallel  machines scheduling with lookahead[J]. Operations Research Transactions, 2015 , 19(4) : 121 -126 . DOI: 10.15960/j.cnki.issn.1007-6093.2015.04.012

References

Fu R Y, Tian J, Yuan J J. On-line scheduling on an unbounded parallel batch machine to minimize makespan of two families of jobs [J].  Journal of Scheduling, 2009, 12: 91-97.


Fu R Y, Cheng T C E,  Ng C T, et al. An optimal online algorithm for single parallel-batch machine scheduling with incompatible job families to minimize makespan [J].  Operations Research Letters, 2013, 41: 216-219.

Tian J, Cheng T C E, Ng C T, et al. Online scheduling on unbounded parallel-batch machines with incompatible job families [J]. Theoretical Computer Science, 2011,  412: 2380-2386.
 
Li W J, Yuan J J, Cao J F, et al. Online scheduling of unit length jobs on a batching machine to maximize the number of early jobs with
lookahead [J].  Theoretical Computer Science, 2009,  410: 5182-5187.
 
Zheng F F, Xu Y F, Zhang E. How much can lookahead help in online single machine scheduling [J].  Information Processing Letters, 2008, 106: 70-74.

Li W H, Zhang Z K, Yang S F. Online algorithms for scheduling unit length jobs on parallel-batch machines with lookahead [J].  Information Processing Letters, 2012,  112: 292-297.

Li W H, Yuan J J, Yang S F. Online scheduling of incompatible unit-length job families with lookahead [J]. Theoretical Computer Science,2014, 543: 120-125.

Zhang G C, Cai X Q, Wong C K, Online algorithms for minimizing makespan on batch processing machines [J]. Naval Research Logistics, 2001, 48:241-258.

 
Outlines

/