Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
6876183 | Theoretical Computer Science | 2014 | 11 Pages |
Abstract
We consider the online scheduling of incompatible unit-length job families on an unbounded parallel-batch machine with lookahead. In this paper online means that jobs arrive over time. The objective is to mininize the makespan. In the lookahead model, at a time instant t, an online algorithm can foresee the information of all jobs arriving in the time segment (t,t+β]. Incompatible job families mean 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+αf for 0â¤Î²<1, where αf is the positive root of the equation fâ
αf2+(1+β)αf+βâf=0 and f is the number of job families which is known in advance.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Wenhua Li, Jinjiang Yuan, Sufang Yang,