When jobs have to be processed on a set of identical parallel machines
so as to minimize the makespan of the schedule, list scheduling rules
form a popular class of heuristics. The order in which jobs appear on
the list is assumed here to be determined by the relative size of the
ir processing times; well-known special cases are the LPT rule and the
SPT rule, in which the jobs are ordered according to non-increasing a
nd non-decreasing processing time respectively. When all processing ti
mes are exactly known, a given list scheduling rule will generate a un
ique assignment of jobs to machines. However, when there exists a prio
ri uncertainty with respect to one of the processing times, then there
will be, in general, several possibilities for the assignment that wi
ll be generated once the processing time is known. This number of poss
ible assignments may be viewed as a measure of the sensitivity of the
list scheduling rule that is applied. We derive bounds on the maximum
number of possible assignments for several list scheduling heuristics,
and we also study the makespan associated with these assignments. In
this way we obtain analytical support for the intuitively plausible no
tion that the sensitivity of a list scheduling rule increases with the
quality of the schedule produced.