Online scheduling with chain precedence constraints of equal-length jobs on parallel machines to minimize makespan

摘要

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 . But the problem is unaddressed for . In this paper, we present a best possible online algorithm for the problem with , where the algorithm has a competitive ratio of 1.3028 for and 1.3146 for .