List scheduling for jobs with arbitrary release times and similar lengths

This paper considers the problem of on-line scheduling a list of independent jobs in which each job has an arbitrary release time and length in [1, r] with r ≥ 1 on m parallel identical machines. For the list scheduling algorithm, we give an upper bound of the competitive ratio for any m ≥ 1 and show that the upper bound is tight when m = 1. When m = 2, we present a tight bound for r ≥ 4. For r < 4, we give a lower bound and show that 2 provides an upper bound.