Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
436595 | Theoretical Computer Science | 2014 | 11 Pages |
Abstract
In this paper, we consider two semi-online scheduling problems of parallel machines with two GoS (grade of service) levels and unit processing time, in which the objective is to minimize the makespan. Assume that the GoS levels of the first s machines are 2 and that of the last (m−s)(m−s) machines are 1 where m is the number of machines. The first problem is the lookahead version where an online algorithm is able to foresee the information of the next k jobs. The second problem is the buffer version where a buffer is available for storing at most g jobs. For the both versions, we prove that the lookahead ability or the buffer is useless for designing algorithm when k
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Taibo Luo, Yinfeng Xu, Li Luo, Changzheng He,