Efficiency and Effectiveness of Normal Schedules on Three Dedicated Processors

A set of tasks has to be scheduled on three processors and each task requires that a set of the processors be available for a given processing time. The objective of the problem is to determine a nonpreemptive schedule with minimum makespan. The problem is known to be NP-hard in the strong sense. A normal schedule is such that all tasks requiring the same set of processors are scheduled consecutively. We show that, under a certain (uniform) probability distribution on the problem instances, in more than 95% of the instances the best normal schedule is optimal when the number of tasks grows to infinity. For the hard cases it is shown that the relative error produced by the best normal schedule is bounded by 5/4. This result improves the bound of 4/3 known in the literature and the improved bound is shown to be tight.