Next: MINIMUM PREEMPTIVE SCHEDULING WITH
Up: Multiprocessor Scheduling
Previous: MINIMUM PRECEDENCE CONSTRAINED SCHEDULING
  Index
- INSTANCE:
Set T of tasks each having length l(t), number m of processors, number
r of resources, resource bounds
,
,
and resource
requirement
,
,
for each task t and
resource i.
- SOLUTION:
An m processor schedule for T that obeys the resource constraints, i.e., a
function
such that for all
,
if S(u) is
the set
of tasks t for which
,
then
and for
each resource i
- MEASURE:
The makespan of the schedule, i.e.,
.
- Good News:
Approximable within 2 [181].
- Comment:
Note that the restriction in which there is only one resource, i.e.,
the available processors, is identical to minimizing the makespan of
the schedule of parallel tasks on m processors. In this case,
minimizing the average response time, i.e.,
is approximable within 32 [454].
The further variation in which each task can be executed by any number
of processors and the length of a task is a function of the number of
processors allotted to it is also approximable [363].
Variation in which every task is of length 1 and has an integer
ready-time, which means that it cannot be processed before its
ready-time, is approximable [448].
- Garey and Johnson: SS10
Next: MINIMUM PREEMPTIVE SCHEDULING WITH
Up: Multiprocessor Scheduling
Previous: MINIMUM PRECEDENCE CONSTRAINED SCHEDULING
  Index
Viggo Kann
2000-03-20