a release time
and a length
.
such that, for all
and for each processor
i
, if
S(u,i)
is the set of tasks
t
for which
and
, then
|S(u,i)| = 1
and for each task
t
,
.
.
where
n=|T|
[
252
].
for any
[
252
].
and it is not
approximable within
for any
[
213
]. In the preemptive case, that is, in the case a job
that is running can be preempted and continue later on any machine,
the problem is approximable within
and it is not
approximable within
where
[
252
].
Variation in which all speed factors are 1 and the load is measured using the
norm, i.e.
,
admits a PTAS for any
[
5
].
Viggo Kann