A PTAS for Minimizing the Total Weighted Completion Time on Identical Parallel Machines.
We consider the problem of scheduling a set ofn jobs onm identical parallel machines so as to minimize the weighted sum of job completion times. This problem is NP-hard in the strong sense. The best approximation result known so far was a 1/2 (1 2)-approximation algorithm that has been derived by Kawaguchi and Kyan back in 1986. The contribution of this paper is a polynomial time approximation scheme for this setting, which settles a problem that was open for a long time. Moreover, our result constitutes the =rst known approximation scheme for a strongly NP-hard scheduling problem with minsum objective.
Introduction
The problem. We consider the following machine scheduling model. We are given a set J of n independent
jobs that have to be scheduled on m identical parallel machines or processors. Each job
is specified by its positive processing requirement p j and by its positive weight w j . In a feasible schedule
for J , every job j 2 J is processed for p j time units on one of the m machines in an uninterrupted
fashion. Every machine can process at most one job at a time, and every job can be processed on at
most one machine at a time. The completion time of job j in some schedule is denoted by C j . The goal
is to minimize the total weighted completion time
. In the standard classification scheme of
Graham, Lawler, Lenstra, & Rinnooy Kan 1979, this scheduling problem is denoted by P
m part of the input, and by Pm
Complexity of the problem. For the special case of only one machine (i. e., the problem
can be solved in polynomial time by Smith's Ratio Rule: process the jobs in order of nonincreasing
. Thus, for the single machine case, the 'importance' of a job is measured by its ratio. For
a constant number m - 2 of machines, the problem is NP-hard in the ordinary sense and solvable
in pseudopolynomial time. For m part of the input, the problem is NP-hard in the strong sense; see
problem SS13 in Garey & Johnson 1979. The special case P j j
solvable in polynomial time by sorting, see Conway, Maxwell, & Miller 1967.
An extended abstract will appear in the Proceedings of the 31st Annual ACM Symposium on Theory of Computing
(STOC'99).
y Technische Universit?t Berlin, Fachbereich Mathematik, MA 6-1, Stra-e des 17. Juni 136, D-10623 Berlin, Germany,
E-mail skutella@math.tu-berlin.de. Part of this research was done while the first author was visiting C.O.R.E., Louvain-
la-Neuve, Belgium.
z Technische Universit?t Graz, Institut f?r Mathematik, Steyrergasse 30, A-8010 Graz, Austria, E-mail
gwoegi@opt.math.tu-graz.ac.at. Supported by the START program Y43-MAT of the Austrian Ministry of Science.
Approximation algorithms. In this paper we are interested in how close one can approach an optimum
solution to these NP-hard scheduling problems in polynomial time. Thus, our research focuses on
approximation algorithms which efficiently construct schedules whose values are within a constant factor
of the optimum solution value. The number ff is called performance guarantee or performance
ratio of the approximation algorithm. A family of polynomial time approximation algorithms with performance
called a polynomial time approximation scheme (PTAS). If
the running times of the approximation algorithms are even bounded by a polynomial in the input size
and 1
" , then these algorithms build a fully polynomial time approximation scheme (FPTAS). It is known
that unless P=NP, a strongly NP-hard optimization problem cannot possess an FPTAS, see Garey &
Johnson 1979.
Known approximation results. Sahni (1976) gives a FPTAS for the weakly NP-hard scheduling
problem
fixed m. Kawaguchi & Kyan (1986) analyze list scheduling in order of
nonincreasing ratios w j
on identical parallel machines. They prove a performance ratio 1
for the
strongly NP-hard problem
Till now, this was the best approximation result for this problem.
Alon, Azar, Woeginger, & Yadid (1998) study scheduling problems on identical parallel machines with
various objective functions that solely depend on the machine completion times. In particular, they give
a polynomial time approximation scheme for the problem of minimizing
denotes the
finishing time of machine i. By rewriting the objective function in an appropriate way, this result implies
a PTAS for the problem of minimizing the weighted sum of job completion times if all job ratios w j
are equal.
Generally speaking, the approximability of scheduling problems with total job completion time objective
(so-called minsum scheduling problems) is not well-understood. Some minsum problems can
be solved in polynomial time using straightforward algorithms (like the single machine version of the
problem
weakly NP-hard minsum problems allow an FPTAS based on dynamic
programming formulations (see, e. g., Sahni 1976 and Woeginger 1998). Some minsum problems do not
have a PTAS unless P=NP (Hoogeveen, Schuurman, & Woeginger 1998). Some of these problems cannot
even be approximated in polynomial time within a constant factor (like minimizing total flow time,
see Kellerer, Tautenhahn, & Woeginger 1996 and Leonardi & Raz 1997). Some minsum problems have
constant factor approximation algorithms that are based on rounding and/or transforming and/or manipulating
the solutions of preemptive relaxations or relaxations of integer programming formulations
(see, e. g., Phillips, Stein, & Wein 1995, Hall, Schulz, Shmoys, & Wein 1997, or Skutella 1998); due to the
integrality gap, these approaches can never yield a PTAS. However, there is not a single PTAS known
for a strongly NP-hard minsum scheduling problem.
Contribution of this paper. Our contribution is a polynomial time approximation scheme for the
general problem
of minimizing the total weighted completion time on identical parallel
machines. This result is derived in two steps. In the first step, we derive a PTAS for the special case
where the largest job ratio is only a constant factor away from the smallest job ratio. This result is
derived by modifying and by generalizing a technique of Alon et al. 1998. In the second step, we derive a
in its full generality. The main idea is to partition the jobs into subsets according
to their ratios such that near optimal schedules can be computed for all subsets; the key observation is
that these schedules can be concatenated without too much loss in the overall performance guarantee.
Our result yields the first polynomial time approximation scheme for a strongly NP-hard scheduling
problem with minsum objective. It confirms a conjecture of Hoogeveen, Schuurman, & Woeginger 1998,
it solves an open problem posed in Alon et al. 1998, and it finally improves on the ancient result by
Only very recently, several groups announced independently from each other approximation schemes
for the strongly NP-hard problem 1j r j j
even for more general scheduling problems, cf. Chekuri
et al. 1999.
Organization of the paper. Section 2 contains preliminaries which will be used throughout the paper.
In Section 3 we give an approximation scheme for the special case that the ratios of jobs are within a
constant range. Finally, in Section 4 we present the approximation scheme for arbitrary instances of
Preliminaries
By Smith's Ratio Rule, it is locally optimal to schedule the jobs that have been assigned to a machine
in order of nonincreasing ratios w j
; the proof is a simple exchange argument. Throughout the paper, we
will restrict to schedules meeting this property. For a given schedule
that
Notice that the second term on the right hand side is nonnegative and does not depend on the specific
schedule. Therefore, for each " ? 0, a (1 ")-approximation algorithm for the problem to minimize
the function
")-approximation algorithm for minimizing the total weighted
completion time. In fact, in Section 3 it will be more convenient to consider the objective function
and we will give a polynomial time approximation scheme for the problem to minimize this
function there.
We use the following notation: For a subset of jobs J
denote the total
processing time of the jobs in J 0 . Moreover, denote the average machine load caused by the jobs in J 0
by
use the simpler notation L := L(J). We start with the following
observation: Consider a subset of jobs J
ae for all the jobs in J 0 are consecutively
scheduled on a machine in an arbitrary order starting at time - , their contribution to the objective function
is given by
This observation together with Smith's Ratio Rule leads to the following lemma which generalizes a result
of Eastman, Even, & Isaacs 1964.
Lemma 2.1. Let ae 1 denote the different job ratios w j
let J h :=
g. For a given schedule, denote the subset of J h that is being assigned to
machine i by J h;i . Then, the value of the schedule is given by
ae h
ae '
Proof. On each machine i and for each 1 - q, the jobs in J ';i are scheduled consecutively starting at
time
h=1 p(J h;i ). The result thus follows from (2).
Notice that the right hand side of (3) only depends on the total processing times of the sets J h;i , but
not on the structure of these sets. In the analysis of the approximation scheme we will make use of the
following lower bound on the value of an optimal schedule:
Lemma 2.2. Using the same notation as in Lemma 2.1, the value of an arbitrary schedule is bounded
from below by
Proof. By (1) and Lemma 2.1 we get
ae h
The second inequality follows from the convexity of the function (a 1 ; a
3 The approximation scheme for a constant range of ratios
In this section we consider the problem to minimize
give a polynomial time approximation
scheme for instances with bounded weight to length ratios of jobs, i. e., where for all job ratios w j
for an arbitrary R ? 0 and a real constant that does not depend on the input. First notice
that by rescaling the weights of jobs we can restrict to the case R = 1.
3.1 Structural insights
be an arbitrary real constant and choose a corresponding constant \Delta 2 N with ffi \Delta+1 - ae.
If we round up the weights of jobs such that the ratio of each job attains the nearest integer power of ffi,
the value of an optimal schedule increases at most by a factor 1
. Since the constant can be chosen
arbitrarily close to 1, we may restrict to instances of P
are of the form
\Deltag. We use the following notation in this section: For
by J h the class of all jobs
. The completion time of machine i in some schedule is
denoted by M i .
Lemma 3.1. Let f
in an optimal schedule M i ? fM i 0 for a pair of machines
machine i processes exactly one job.
Proof. Let j denote the last job on machine i. Observe that j must start at or before time
moving j to the end of machine i 0 would decrease \Gamma j and hence the value of the schedule. Thus, we get
. By contradiction, assume that j is not the first job on machine i; denote the first job by k.
Let W i and W i 0 denote the sum of the weights of jobs scheduled on machine i and i 0 , respectively. Since
since the weight to length
ratios of all jobs are at most 1. Thus, removing job k from machine i and inserting it at the beginning
of machine i 0 changes the value of the schedule by p k (W contradicting optimality.
For the following corollary notice that there is at least one machine i with M i - L in every schedule.
Corollary 3.2. If a job j has size p j - fL, then j occupies a machine of its own in any optimal schedule.
If no job has size greater than fL, then the completion time of each machine is at most fL in any optimal
schedule.
As a result of Corollary 3.2, we can iteratively reduce a given instance: as long as a job j of size
remove it from the set of jobs J , assign it to a machine of its own, and decrease the
number of machines by one. In the following we can thus restrict to instances of the following form:
Assumption 3.3. The processing time p j of each job j as well as the completion time M i of any machine
i in an optimal schedule are bounded from above by fL.
3.2 Rounding the instance
We define a simplified, rounded version of the input for which we can compute an optimal schedule in
polynomial time. Moreover, under some assumption that we will specify later, an optimal solution to the
rounded instance will lead to a near optimal solution to the original instance. The rounding is based on
the positive integral constant - which will later be chosen to be 'sufficiently large'.
The rounding is done for every class J h , 0 - h - \Delta, separately. We will replace the jobs in J h by new
jobs, with slightly different processing times; however, the length to weight ratio will stay at ffi h .
ffl Every 'big' job j in the original instance with
- , is replaced by a corresponding rounded job
whose processing time
rounded up to the next integer multiple of L
. The weight
j of the rounded job equals
. Note that for the rounded processing time
holds.
ffl Denote by S h the total processing time of the 'small' jobs in J h whose processing times are not
greater than L
- . Denote by S #
h the value of S h rounded up to the next integer multiple of L
- . Then
the rounded instance contains S #
new jobs, each of length L
- . The weight of every new job equals
Note that the total number of jobs in the rounded instance is bounded by n. By construction we get the
following lemma.
Lemma 3.4. By replacing the rounded jobs with their unrounded counterparts, an arbitrary schedule for
the transformed instance induces a schedule of smaller or equal value for the original instance.
The rounded instance can be solved in polynomial time, e. g., by dynamic programming. However, we
use a generalization of an alternative approach of Alon, Azar, Woeginger, & Yadid 1998; we formulate
the problem as an integer linear program whose dimension is bounded by a constant. By Assumption 3.3
and by construction, the size p #
j of each job j is bounded by
Therefore, since all job sizes are integer multiples of 1
there is at most a constant number \Pi of possible
Moreover, since the number of possible length to weight ratios is bounded by
the constant \Delta + 1, the total number of different types of jobs is bounded by the constant
For denote the number of jobs of size k L
define the vector n := (n 1;0 ; n An assignment of jobs to one machine is given by a vector
is the number of jobs of size k L
that are assigned to
the machine. The completion time of the machine is given by
h=0
let c(u) denote the contribution to the objective function of a machine that is scheduled according to u.
j denote the average machine load for the transformed instance; observe that by
construction
Thus, by Assumption 3.3 we can bound the completion time of each machine by f -+\Delta+2
L. Denote by
U the set of vectors u with M(u) - f -+\Delta+2
- L. For a vector u 2 U , each entry u k;h is bounded by a
number that only depends on the constants -, \Delta, f and is thus independent of the imput. Therefore the
set U is of constant size.
We can now formulate the problem of finding an optimal schedule as an integer linear program with
a constant number of variables. For each vector u 2 U we introduce a variable xu which denotes the
number of machines that are assigned jobs according to u. An optimal schedule is then given by the
following program:
min
u2U
subject to
u2U
u2U
It has been shown by Lenstra (1983) that an integer linear program in constant dimension can be solved
in polynomial time.
3.3 Proving near optimality
By Lemma 3.4 it remains to show that the value of an optimal schedule for the rounded instance is at
most a factor of (1 above the optimal objective value of the original instance. We will prove this
under the following assumption on the original instance, and afterwards we will demonstrate how to get
rid of the assumption:
Assumption 3.5. There exists an optimal schedule of the following form: The completion time M i of
every machine i fulfills the inequality L
In order to achieve the desired precision, we now choose the integer - sufficiently large to fulfill the
inequality
Since \Delta, ffi, f , and " are constants that do not depend on the input, also - is constant and independent
of the input.
Lemma 3.6. Under Assumption 3.5, the optimal objective value of the rounded instance is at most a
factor of (1 above the optimal objective value of the original instance.
Proof. Take an optimal schedule for the original instance as described in Assumption 3.5. Consider some
fixed machine i with finishing time M i in this optimal schedule. For
h denote the
subset of J h processed on machine i and let J
h denote the set of all jobs processed on machine
i. Note that
By Lemma 2.1, the contribution of machine i to the objective function is given by
Replace every big job j by its corresponding rounded big job j # . This may increase every p(J 0
a multiplicative factor of at most -+1
- . For every J 0
h , denote by s h the total size of its small jobs. Round
s h up to the next integer multiple of L
- and replace it by an appropriate number of rounded small jobs
with length to weight ratio ffi h . This may increase p(J 0
h ) by an additive factor of at most L
- . Note that
by repeating this replacement procedure for all machines, one can accommodate all jobs in the rounded
instance.
Denote by K h the resulting set of rounded jobs that are assigned to machine i and have length to
weight ratio ffi h . We have for
Now compare the first term on the right hand side of (6) for J 0
h to the corresponding term for the jobs
in K h :2
In the last inequality, we applied together with the second inequality in (5). In a similar way, we
compare the second term on the right hand side of (6) for J 0
h to the corresponding term for the jobs in
because of the first inequality in (5), we get that the right hand side of (6) fulfills:2
Putting this together with (7), (8), and (4), a short calculation shows that the objective value for the
rounded instance is at most a factor of (1 above the optimal objective value for the original instance.
Finally, we consider the case where Assumption 3.5 may be violated. By Assumption 3.3 we can
restrict to the case that only the lower bound 1
f L can be violated for some machine completion time. As
a result of Lemma 3.1 we get:
Corollary 3.7. If in an optimal schedule
f for some machine i, then every machine i 0 with
only one job; in particular, there exists a job j of size p j - L and every such job
occupies a machine of its own.
In the following we assume that there exists a job j of size p j - L; otherwise, Assumption 3.5 is true
by Corollary 3.7 and we are finished. Unfortunately, we do not know in advance whether or not M i ! L
f
for some machine i in an optimal schedule. Therefore we take both possibilities into account and compute
two schedules for the given instance such that the better one is guaranteed to be a (1 ")-approximation
by Corollary 3.7.
On the one hand, we compute an optimal schedule for the rounded instance and turn it into a feasible
schedule for the original instance as described in Lemma 3.4. On the other hand, we assign each job j with
to a machine, remove those jobs from the instance, and decrease the number of machines by the
number of removed jobs. For the reduced instance, we can recursively compute a (1 ")-approximation
by again taking the better of two schedules. Notice that in each recursion step the number of machines
is decreased by at least one; thus, after at most m \Gamma 1 steps we arrive at a trivial problem that can be
solved to optimality in polynomial time.
We can now state the main result of this section:
Theorem 3.8. There exists a PTAS for the special case of the problem P
are in a constant range [aeR; R] for an arbitrary R ? 0 and a real constant that does not depend
on the input.
4 The polynomial time approximation scheme
In this section we present the approximation scheme for arbitrary instances of P
. The main
idea for deriving this result is to partition the set of jobs into subsets according to their ratios w j
. The
ratios of all jobs in one subset are within a constant range such that for each subset a near optimal
schedule can be computed within arbitrary precision in polynomial time, see Theorem 3.8. In a second
step, these 'partial schedules' are concatenated in order of nonincreasing job ratios such that Smith's
Ratio Rule is obeyed on each machine.
For the sake of a more accessible analysis, we first present a randomized variant of the approximation
scheme and discuss its derandomization later. Throughout this section we assume that w j
all weights of jobs can be rescaled by the inverse of the maximal ratio.
4.1 The randomized approximation scheme
The partitioning step. Let \Delta be a positive integer and let ffi := 1
later we will choose \Delta large such
that ffi gets small. The partitioning of the set of jobs J is performed in two steps. The first step computes
a fine partition which is then randomly turned into a rougher partition in the second step.
1. For h 2 N let J(h) :=
\Psi .
2. Draw q uniformly at random from f1;
I q
s
J(h).
Notice that for fixed q the number of nonempty subsets J q
bounded by n. Of course, we
only take those subsets into consideration in the algorithm. The intuition for step 2 is to compensate
the undesired property of the fine partition computed in step 1 that jobs with similar ratio may lie in
different subsets of the computed partition. The random choice in step 2 assures that the probability for
those jobs to lie in different subsets of the rough partition is small, i. e., in O
Computing partial schedules. The quotient of the biggest and the smallest ratio of jobs in a subset
s is bounded by the constant ffi \Delta . Thus, by Theorem 3.8, we can compute in polynomial time for all
nonempty sets of jobs J q
s near optimal m-machine schedules of value Z q
s
, where Z q
s

denotes the value of an optimal schedule for J q
s .
The concatenation step. In the final step of the algorithm these partial schedules are concatenated.
One possibility is to do it machine-wise: On machine i, all jobs that have been assigned to i in the partial
schedules are processed according to Smith's Ratio Rule. However, this deterministic concatenation can
lead to an undesired unbalance of load on the machines. It might for example happen that each subset
of jobs J q
s consists of at most one job which is always assigned to machine 1 in the corresponding partial
schedule. Thus, concatenating the partial schedules as proposed above would leave all but one machine
idle.
Therefore, we first randomly and uniformly permute the numbering of machines in each partial schedule
and then apply the machine-wise concatenation described above. In this randomly generated schedule
the probability for two jobs from different subsets to be processed on the same machine is equal to 1
such that one can expect an appropriately balanced machine assignment.
4.2 The analysis of the randomized approximation scheme
The analysis is based on the observation that the value of the computed schedule is composed of the
sum of the values of the partial schedules plus the additional cost caused by the delay of jobs in the
concatenation step. It is easy to see that the sum of the values of the near optimal partial schedules
cannot substantially exceed the value of an optimal schedule.
The key insight for the analysis is that the delay of jobs in one subset caused by another subset in
the concatenation step can essentially be neglected. One reason is that the delayed jobs usually (i. e.,
with high probability) have much smaller ratio and are thus less important than the jobs which cause
the delay. On the other hand, if there are too many 'unimportant' jobs to be neglected, then the total
weighted completion time of the corresponding near optimal partial schedule must be large compared to
the delay caused by the important jobs.
The following lemma provides two lower bounds on the value of an optimal schedule Z   . To simplify
Lemma 4.1. For each q 2 \Deltag, the value Z   of an optimal schedule is bounded by
Z   -
Z q
s
and Z   - mX
Proof. Take an optimal schedule for the set of jobs J and denote the completion time of job j in this
schedule by C
j . This yields
s
Z q
s

since the completion times C
also define a feasible schedule for each subset of jobs J q
s . In order to prove
the second lower bound, first observe that the value of an optimal schedule decreases if we round the
weights of jobs j 2 J(h) to w N. The result then follows from Lemma 2.2.
The next step in the analysis is to determine an expression for the expected value of the computed
schedule.
Lemma 4.2. The expected value of the computed schedule is given by
Z q
s
min
Proof. We first keep q fixed and analyze the conditional expectation E q
\Theta P

. This conditional
expectation is equal to the sum of the values of the partial schedules
s plus the expected cost
caused by the delay of jobs in the concatenation step.
The expected delay of an arbitrary job j 2 J can be determined as follows. Let t 2 N 0 and k 2 I q
such that j 2 J(k) ' J q
t . Then, the expected delay of job j is equal to the expected load caused by
jobs from
s on the machine which job j is being processed on. Since the machines are permuted
uniformly at random in the concatenation step, the expected load is equal to the average load
s
lie in different sets of indices I q
As
a consequence, for fixed q, the conditional expectation of the total weighted completion time can be
as:
Z q
Notice that for randomly chosen q the expected value of j q
h;k is equal to the probability that h and k lie
in different sets of indices I q
By construction of the sets of indices I q
r , this probability is equal
to k\Gammah
\Delta. The result thus follows from (11).
The following theorem contains the main result of this subsection.
Theorem 4.3. For a given
\Upsilon
. Then, the expected value of the computed schedule
is bounded by times the value of an optimal solution, i. e.,
Proof. We compare the expected value given in Lemma 4.2 to the lower bounds on the value of an optimal
schedule given in Lemma 4.1. Since, by construction of the algorithm, Z q
s
, for each q, and
s
- Z   by Lemma 4.1, the first term on the right hand side of (10) can be bounded from above
by
Z q
s
In order to bound the second term on the right hand side of (10), first observe that for each k 2 N
Thus, the inequality for the geometric and the arithmetic mean yields:
Notice that (12) bounds the cost for the possible delay of jobs in J(k) caused by jobs in J(h) in terms
of the lower bounds on optimal schedules for J(h) and J(k) in (9). In particular, if then the
cost for the delay is small compared to the sum of the values of optimal schedules for J(h) and J(k). For
the cases 2, however, this cost may be too large to be neglected. This is the point
where we will make use of the random choice of q.
To be more precise, we divide the sum over all pairs h ! k in the second term of (10) into three
partial sums . The first partial sum \Sigma 1 takes all pairs with account and can
thus be bounded by
by (12)
The second partial sum \Sigma 2 takes all pairs with account and can be bounded using the
same arguments
by (12)
Finally, the third partial sum \Sigma 3 takes all pairs with k - h account. In this case we replace the
\Psi by 1 (i. e., we do not make use of the random choice of q) and get
h-k\Gamma3
h-k\Gamma3
Putting the results together, the expected value of the computed schedule is bounded by
The second inequality follows from the choice of ffi and a short calculation.
4.3 The deterministic approximation scheme
Up to now we have presented a randomized approximation scheme, i. e., we can efficiently compute schedules
whose expected values are arbitrarily close to the optimum. However, it might be more desirable to
have a deterministic approximation scheme which computes schedules with a firm performance guarantee
in all cases. Therefore we discuss the derandomization of the randomized approximation scheme.
Since the random variable q can only attain a constant number of different values, we can afford to
derandomize the partition step of the algorithm by trying all possible assignments of values to q. In
the following discussion we keep q fixed. The derandomization of the concatenation step is slightly more
complicated. We use the method of conditional probabilities, i. e., we consider the random decisions one
after another and always choose the most promising alternative assuming that all remaining decisions
will be made randomly.
Thus, starting with the partial schedule for J q
0 , we iteratively append the remaining partial schedules
for J q
to the current schedule. In each iteration t we use a locally optimal permutation of
the machines which is given in the following way. For denote the load or completion
time of machine i in the current schedule of the jobs in
s . Renumber the machines such that
the sum of the weights of jobs in J q
t that are processed
on machine i in the corresponding partial schedule. Renumber the machines in the partial schedule such
that . It is an easy observation, which can be proved by a simple exchange
argument, that appending the partial schedule machine-wise to the current schedule according to the
given numbering of machines minimizes the cost caused by the delay of jobs in J q
t . In particular, this
cost is smaller than the expected cost for the randomized variant of the algorithm which is given by
s
Moreover, the permutation of the machines chosen in iteration s does not influence the expected delay of
jobs considered in later iterations (since the expected delay is simply the average machine load).
As a result of the above discussion, the value of the schedule computed by the deterministic algorithm
is bounded from above by the expected value of the schedule computed by its randomized variant given
in Subsection 4.1. Thus, as a consequence of Theorem 4.3 we can state the following main result of this
paper.
Theorem 4.4. There exists a polynomial time approximation scheme for the problem P

Acknowledgements

The authors would like to thank the organizers of the Dagstuhl-Seminar 98301 on
'Graph Algorithms and Applications' during which the result presented in this paper has been achieved.



--R

Approximation schemes for scheduling on parallel machines.
Personal communication.
Theory of Scheduling.
Bounds for the optimal scheduling of n jobs on m processors.
Computers and Intractability: A Guide to the Theory of NP- Completeness
Rinnooy Kan.
Scheduling to minimize average completion time: Off-line and on-line approximation algorithms

Worst case bound of an LRF schedule for the mean weighted flow-time problem
Approximability and nonapproximability results for minimizing total flow time on a single machine.

Approximating total flow time on parallel machines.
Minimizing average completion time in the presence of release dates.
Algorithms for scheduling independent tasks.
Various optimizers for single-stage production
Semidefinite relaxations for parallel machine scheduling.
When does a dynamic programming formulation guarantee the existence of an FPTAS?
--TR

--CTR
Nicole Megow , Marc Uetz , Tjark Vredeveld, Models and Algorithms for Stochastic Online Scheduling, Mathematics of Operations Research, v.31 n.3, p.513-525, August 2006
Mark Scharbrodt , Thomas Schickinger , Angelika Steger, A new average case analysis for completion time scheduling, Journal of the ACM (JACM), v.53 n.1, p.121-146, January 2006
Martin Skutella, Convex quadratic and semidefinite programming relaxations in scheduling, Journal of the ACM (JACM), v.48 n.2, p.206-242, March 2001
approximation scheme;combinatorial optimization;worst-case ratio;scheduling theory;approximation algorithm