Online scheduling on uniform machines with two hierarchies |
| |
| Authors: | Li-ying Hou Liying Kang |
| |
| Institution: | 1. Department of Mathematics, Nanjing Agricultural University, Nanjing, 210095, P.R. China
2. Department of Mathematics, Shanghai University, Shanghai, 200444, P.R. China
|
| |
| Abstract: | In this paper we study online scheduling problem on m parallel uniform machines with two hierarchies. The objective is to minimize the maximum completion time (makespan). Machines are provided with different capability. The machines with speed s can schedule all jobs, while the other machines with speed 1 can only process partial jobs. Online algorithms for any 0<s<∞ are provided in the paper. For the case of k=1 and m=2, and the case of some values of s, k=1 and m=3, the algorithms are the best possible, where k is the number of machines with hierarchy 1, and m is the number of machines. Lower bounds for some special cases are also presented. |
| |
| Keywords: | |
| 本文献已被 SpringerLink 等数据库收录！ |
|
