LAUSR

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$$m=2. But the problem is unaddressed for $$m\ge 3$$m≥3. In this paper, we present a best possible online algorithm for the problem with $$m\ge 3$$m≥3, where the algorithm has a competitive ratio of 1.3028 for $$3\le m\le 5$$3≤m≤5 and 1.3146 for $$m\ge 6$$m≥6.