Online scheduling with chain precedence constraints of equal-length jobs on parallel machines to minimize makespan |
| |
Authors: | Xing Chai Wenhua Li |
| |
Institution: | 1.School of Mathematics and Statistics,Zhengzhou University,Zhengzhou,China;2.Hennan Key Laboratory of Financial Engineering,Zhengzhou,China |
| |
Abstract: | We study the online scheduling problem on m identical parallel machines to minimize makespan, i.e., the maximum completion time of the jobs, where m is given in advance and the jobs arrive online over time. We assume that the jobs, which arrive at some nonnegative real times, are of equal-length and are restricted by chain precedence constraints. Moreover, the jobs arriving at distinct times are independent, and so, only the jobs arriving at a common time are restricted by the chain precedence constraints. In the literature, a best possible online algorithm of a competitive ratio 1.3028 is given for the case \(m=2\). But the problem is unaddressed for \(m\ge 3\). In this paper, we present a best possible online algorithm for the problem with \(m\ge 3\), where the algorithm has a competitive ratio of 1.3028 for \(3\le m\le 5\) and 1.3146 for \(m\ge 6\). |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|