Operations Research Transactions ›› 2012, Vol. 16 ›› Issue (2): 115-120.

• Original Articles • Previous Articles     Next Articles

On-line scheduling on a machine of two families with lookahead

YANG  Sufang1, LI  Wenhua1   

  1. 1. Department of Mathematics, Zhengzhou University, Zhengzhou 450001, China
  • Received:2011-09-23 Revised:2011-11-09 Online:2012-06-15 Published:2012-06-15

Abstract: We consider on-line scheduling on a parallel batching machine of two incompatible families of unit-length jobs with lookahead where the batch capacity is unbounded. In this paper online means that jobs arrive over time. The objective is to mininize the makespan. In unbounded parallel batch scheduling, an infinite capacity machine can process many jobs simultaneously as a batch, the processing time of a batch is equal to the maximum processing time of jobs in the batch. 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]. Incompatible job families means that jobs which belong to different families cannot be assigned to the same batch. For this problem, we provide a best possible online algorithm of competitive ratio 1+\alpha for 0\leq \beta <1, where \alpha is the positive root of the equation 2\alpha^{2}+(\beta +1)\alpha +\beta -2=0.

Key words:  on-line scheduling, parallel batching, incompatible family, makespan, competitive ratio