Some Results on Liu’s Conjecture

In 1972, Liu claimed that for any task systems to be scheduled on m 1 identical processors, the ratio of the optimal nonpreemptive schedule length versus the optimal preemptive schedule length is bounded above by $2m/( m + 1 )$. Furthermore, Liu showed that the bound is the best possible by giving a task system achieving the ratio. His upper bound proof was later found to be incorrect, and his claim has since remained a conjecture. In this paper, it is shown that Liu’s bound is valid for the unit execution time (UET) and tree-structured task systems. For two processors, it is shown that some other classes of task systems satisfy the 4/3 bound. Other results comparing the lengths of optimal list, nonpreemptive schedules, and preemptive schedules are also given.