Scheduling Unrelated Machines by Randomized Rounding.
We present a new class of randomized approximation algorithms for unrelated parallel machine scheduling problems with the average weighted completion time objective. The key idea is to assign jobs randomly to machines with probabilities derived from an optimal solution to a linear programming (LP) relaxation in time-indexed variables. Our main results are a $(2+\varepsilon)$-approximation algorithm for the model with individual job release dates and a $(3/2+\varepsilon)$-approximation algorithm if all jobs are released simultaneously. We obtain corresponding bounds on the quality of the LP relaxation.  It is an interesting implication for identical parallel machine scheduling that jobs are randomly assigned to machines, in which each machine is equally likely. In addition, in this case the algorithm has running time O(n log n) and performance guarantee 2.  Moreover, the approximation result for identical parallel machine scheduling applies to the on-line setting in which jobs arrive over time as well, with no difference in performance guarantee.
Introduction
It is by now well-known that randomization can help in the design of algorithms, cf., e. g., [27, 26]. One way
of guiding randomness is the use of linear programs (LPs). In this paper, we give LP-based approximation algorithms
for problems which are particularly well-known for the difficulties to obtain good lower bounds: machine
(or processor) scheduling problems. Because of the random choices involved, our algorithms are rather randomized
approximation algorithms. A randomized r-approximation algorithm is a polynomial-time algorithm that
produces a feasible solution whose expected value is within a factor of r of the optimum; r is also called the
(expected) performance guarantee of the algorithm. Actually, most often we compare the output of an algorithm
with a lower bound given by an optimum solution to a certain LP relaxation. Hence, at the same time we obtain an
analysis of the quality of the respective LP. All our off-line algorithms can be derandomized with no difference in
performance guarantee, but at the cost of increased (but still polynomial) running times.
We consider the following model. We are given a set J of n jobs (or tasks) and m unrelated parallel machines.
Each job j has a positive integral processing requirement which depends on the machine i job j will be processed
on. Each job j must be processed for the respective amount of time on one of the m machines, and may
be assigned to any of them. Every machine can process at most one job at a time. In preemptive schedules, a job
may repeatedly be interrupted and continued later on another (or the same) machine. In nonpreemptive schedules,
a job must be processed in an uninterrupted fashion. Each job j has an integral release date r j ? 0 before which
Parts of this paper appeared in a preliminary form in [36, 35]
# M.I.T., Sloan School of Management and Operations Research Center, E53-361,
Fachbereich Mathematik, MA 6-1, Technische Universitat Berlin, Strae des 17. Juni 136, D-10623 Berlin, Germany, skutella@math.tu-
berlin.de
it cannot be processed. We denote the completion time of job j in a schedule S by C S
or C j , if no confusion is
possible. We seek to minimize the total weighted completion time: a weight w associated with each job j
and the goal is to find a schedule S that minimizes  j2J w j C j . In scheduling, it is quite convenient to refer to the
respective problems using the standard classification scheme of Graham, Lawler, Lenstra, and Rinnooy Kan [17].
The nonpreemptive problem R j r just described, is strongly NP-hard [23].
Scheduling to minimize the total weighted completion time (or, equivalently, the average weighted completion
time) has recently achieved a great deal of attention, partly because of its importance as a fundamental problem
in scheduling, and also because of new applications, for instance, in compiler optimization [5] or in parallel
computing [3]. There has been significant progress in the design of approximation algorithms for this kind of
problems which led to the development of the first constant worst-case bounds in a number of settings. This
progress essentially follows on the one hand from the use of preemptive schedules to construct nonpreemptive
ones [31, 4, 7, 14, 16]. On the other hand, one solves an LP relaxation and then a schedule is constructed by list
scheduling in a natural order dictated by the LP solution [31, 19, 34, 18, 25, 14, 8, 28, 37].
In this paper, we utilize a different idea: random assignments of jobs to machines. To be more precise, we
exploit an LP relaxation in time-indexed variables for the problem R j r and we then show that a certain
variant of randomized rounding leads to a e)-approximation algorithm, for any e ? 0. In the absence of
nontrivial release dates, the performance guarantee can be improved to 3=2 e. At the same moment, the corresponding
LP is a respectively, i. e., the true optimum is always within this
factor of the optimal value of the LP relaxation. Our algorithm improves upon a 16=3-approximation algorithm of
Hall, Shmoys, and Wein [19] that is also based on time-indexed variables which have a different meaning, how-
ever. In contrast to their approach, our algorithm does not rely on Shmoys and Tardos' rounding technique for
the generalized assignment problem [39]. We rather exploit the LP by interpreting LP values as probabilities with
which jobs are assigned to machines. For an introduction to and the application of randomized rounding to other
combinatorial optimization problems, the reader is referred to [33, 26].
Using a different approach, the second author has subsequently developed slightly improved approximation
results for the problems under consideration. For the problem R he gives a 3=2-approximation algorithm
[41] that is based on a convex quadratic programming relaxation in assignment variables, which is inspired by the
time-indexed LP relaxation presented in this paper. Only recently, this approach has been generalized to the
problem with release dates for which it yields performance guarantee 2 [42].
For the special case of identical parallel machines, i. e., for each job j and all machines i we have
Chakrabarti et al. [4] obtained a (2:89 + e)-approximation by refining an online greedy framework of Hall et al.
[19]. The former best known LP-based algorithm, however, relies on an LP relaxation solely in completion time
variables which is weaker than the one we propose. It has performance guarantee (4 \Gamma 1=m) (see [18] for the
details). For the LP we use here, an optimum solution can greedily be obtained by a certain preemptive schedule
on a virtual single machine which is m times as fast as any of the original machines. The idea of using a preemptive
relaxation on such a virtual machine was employed before by Chekuri, Motwani, Natarajan, and Stein [7]. They
show that any preemptive schedule on such a machine can be converted into a nonpreemptive schedule on the
identical parallel machines such that, for each job j, its completion time in the nonpreemptive schedule is at
most (3 \Gamma 1=m) times its preemptive completion time. For the problem to minimize the average completion time,
they refine this to a 2:85-approximation algorithm.
For the algorithm we propose delivers in time O(nlogn) a solution that is expected to be within
a factor of 2 of the optimum. Since the LP relaxation we use is even a relaxation of the corresponding preemptive
problem, our algorithm is also a 2-approximation for which improves upon a 3-approximation
algorithm due to Hall, Schulz, Shmoys, and Wein [18]. In particular, our result implies that the value of an optimal
nonpreemptive schedule is at most a factor 2 the value of an optimal preemptive schedule. For the problem without
release dates, our algorithm achieves performance guarantee 3=2. Since an optimum solution to
the LP relaxation can be obtained greedily, our algorithm also works in the corresponding online setting where
jobs continually arrive to be processed and, for each time t, we must construct the schedule until time t without
any knowledge of the jobs that will arrive afterwards; the algorithm achieves competitive ratio 2 for both the
nonpreemptive and the preemptive variant of this setting.
Recently, Skutella and Woeginger [43] developed a polynomial-time approximation scheme for the problem
which improves upon the previously best known (1
2)=2-approximation algorithm due to
Kawaguchi and Kyan [22]. Subsequently, Chekuri, Karger, Khanna, Skutella, and Stein [6] gave polynomial-time
approximation schemes for the problem its preemptive variant also for the
corresponding problems on a constant number of unrelated machines, Rm j r
On the other hand, it has been shown by Hoogeveen, Schuurman, and Woeginger [20] that the problems R j r
are MAXSNP-hard and therefore do not have a polynomial time approximation scheme, unless
P=NP.
The rest of the paper is organized as follows. In Section 2, we start with the discussion of our main result:
the algorithm with performance guarantee 2 in the general context of unrelated parallel machine scheduling. In
the next section, we give combinatorial approximation algorithms for identical parallel machine scheduling. We
also show how to use these algorithms in an online setting. Then, in Section 4, we discuss the derandomization
of the previously given randomized algorithms. Finally, in Section 5 we give the technical details of turning the
pseudo-polynomial algorithm of Section 2 into a polynomial-time algorithm with performance guarantee
We conclude by pointing out some open problems in Section 6.
Unrelated Parallel Machine Scheduling with Release Dates
In this section, we consider the problem R j r As in [30, 19, 18, 42], we will actually discuss a slightly
more general problem in which the release date of every job j may also depend on the machine. The release
date of job j on machine i is thus denoted by r i j . Machine-dependent release dates are relevant to model network
scheduling in which parallel machines are connected by a network, each job is located at a given machine at time
0, and cannot be started on another machine until sufficient time elapses to allow the job to be transmitted to its
new machine. This model has been introduced in [9, 1].
The problem R j r is well-known to be strongly NP-hard; in fact, already P2
strongly NP-hard, see [2, 23]. The first nontrivial approximation algorithm for this problem was
given by Phillips, Stein, and Wein [30]. It has performance guarantee O(log 2 n). Subsequently, Hall et al. [19]
gave a 16=3-approximation algorithm which relies on a time-indexed LP relaxation whose optimum value serves
as a surrogate for the true optimum in their estimations. We use a somewhat similar LP relaxation, but whereas
Hall et al. invoke the deterministic rounding technique of Shmoys and Tardos [39] to construct a feasible schedule
we randomly round LP solutions to feasible schedules.
be the time horizon, and introduce for every job j 2 J, every machine
m, and every point which represents the time job j is processed on
machine i within the time interval (t; t Equivalently, one can say that a y i jt =p i j -fraction of job j is being
processed on machine i within the time interval (t; t 1]. The LP, which is an extension of a single machine LP
relaxation of Dyer and Wolsey [10], is as follows:
minimize
subject to
for all
Equations (1) ensure that the whole processing requirement of every job is satisfied. The machine capacity constraints
(2) simply express that each machine can process at most one job at a time. Now, for (3), consider an
arbitrary feasible schedule S where job j is being continuously processed between time C S
on machine
h. Then, the expression for C LP
in (3) corresponds to the real completion time C S
j of j if we assign the values
to the LP variables y i jt as defined above, i. e., y
wise. The right-hand side of (4) equals the processing time p h j of job j in the schedule S, and is therefore a lower
bound on its completion time C S
. Finally, constraints (5) ensure that no job is processed before its release date.
Hence, (LP R ) is a relaxation of the scheduling problem R j r In fact, note that even the corresponding
mixed-integer program, where the y-variables are forced to be binary, is only a relaxation.
The following algorithm takes an optimum LP solution, and then constructs a feasible schedule by using a kind
of randomized rounding.
Algorithm LP ROUNDING
Compute an optimum solution y to (LP R ).
Assign each job j to a machine-time pair (i; t) independently at random with probability y i jt
draw t j from the chosen time interval (t; t +1] independently at random with uniform distribution.
Schedule on each machine i the jobs that were assigned to it nonpreemptively as early as possible
in order of nondecreasing t j .
In the last step ties can be broken arbitrarily; they occur with probability zero. For the analysis of the algorithm it
will be sufficient to assume that the random decisions for different jobs are pairwise independent.
Remark 2.1. The reader might wonder whether the seemingly artificial random choice of the t j 's in Algorithm LP
ROUNDING is really necessary. Indeed, it is not, which also implies that we could work with a discrete probability
space: The following results are still true if we simply set t is assigned to a machine-time pair (i; t);
ties are broken randomly or even arbitrarily. We mainly chose this presentation for the sake of giving a different
interpretation in terms of so-called a-points in Section 3.
The following lemma illuminates the intuition in Algorithm LP ROUNDING by relating the implications of the
second step to the solution y of (LP R ). For the analysis of the algorithm, however, we will only make use of the
second part of the Lemma. Its first part is a generalization of a result due to Goemans [14] for the single machine
case.
Lemma 2.2. Let y be the optimum solution to (LP R ) in the first step of Algorithm LP ROUNDING. Then, for each
J the following holds:
a) The expected value of t j is equal to  m
y jt
b) The expected processing time of job j in the schedule constructed by Algorithm LP ROUNDING is equal to
Proof. First, we fix a machine-time pair (i; t) job j has been assigned to. Then, the expected processing time
of j under this condition is p i j . Moreover, the conditional expectation of t j is equal to t
. By adding these
conditional expectations over all machines and time intervals, weighted by the corresponding probabilities y jt
, we
get the claimed results.
Note that the lemma remains true if we start with an arbitrary, not necessarily optimal solution y to (LP R ) in
the first step of Algorithm LP ROUNDING. This is also true for the following results. The optimality of the LP
solution will only be needed to get a lower bound on the value of an optimal schedule.
Lemma 2.3. The expected completion time of each job j in the schedule constructed by Algorithm LP
ROUNDING can be bounded by
this bound is even true if t j is set to t in the second step of the algorithm and ties are broken arbitrarily, see
Remark 2.1. In the absence of nontrivial release dates the following stronger bound holds:
this bound also holds if t j is set to t in the second step of the algorithm and ties are broken uniformly at random.
Proof. We consider an arbitrary, but fixed job j 2 J. To analyze the expected completion time of job j, we first
also consider a fixed assignment of j to a machine-time pair (i; t). Then, the expected starting time of job j under
these conditions precisely is the conditional expected idle time plus the conditional expected amount of processing
of jobs that come before j on machine i.
Observe that there is no idle time on machine i between the maximum release date of jobs on machine i which
start no later than j and the starting time of job j. It follows from the ordering of jobs and constraints (5) that this
maximum release date and therefore the idle time of machine i before the starting time of j is bounded from above
by t. In the absence of nontrivial release dates there is no need for idle time at all.
On the other hand, we get the following bound on the conditional expected processing time on machine i before
the start of j:
y ik'
y ik'
The last inequality follows from the machine capacity constraints (2). However, if t j is set to t in the second step of
the algorithm and ties are broken arbitrarily, we have to replace E[t by 1 on the right-hand side and get a weaker
bound of t +1. Putting the observations together we get an upper bound of 2
2 ) for the conditional expectation
of the starting time of j. In the absence of nontrivial release dates it can be bounded by t
. Unconditioning the
expectation by the formula of total expectation together with Lemma 2.2 b) yields the result.
Theorem 2.4. For instances of R j r the expected value of the schedule constructed by Algorithm LP
ROUNDING is bounded by twice the value of an optimal solution.
Proof. By Lemma 2.3 and constraints (3) the expected completion time of each job is bounded by twice its LP
completion time C LP
. Since the optimal LP value is a lower bound on the value of an optimal schedule and the
weights are nonnegative, the result follows by linearity of expectations.
Note that Theorem 2.4 still holds if we use the weaker LP relaxation where constraints (4) are missing. How-
ever, this is not true for the following result.
Theorem 2.5. For instances of R the expected value of the schedule constructed by Algorithm LP
ROUNDING is bounded by 3=2 times the value of an optimal solution.
Proof. The result follows from Lemma 2.3 and the LP constraints (3) and (4).
Independently, the result in Theorem 2.5 has also been obtained by Fabian A. Chudak (communicated to us by
David B. Shmoys, March 1997) after reading a preliminary version of the paper on hand which only contained the
bound of 2 for R j r Theorem 2.4. In the absence of nontrivial release dates, Algorithm LP ROUNDING
can be improved and simplified:
Corollary 2.6. For instances of R the approximation result of Theorem 2.5 also holds for the following
improved and simplified variant of Algorithm LP ROUNDING: In the second step we assign each job j independently
at random with probability  T
to machine i. In the last step we apply Smith's ratio rule [44] on each
machine, i. e., we schedule the jobs that have been assigned to machine i in order of nonincreasing ratios w
Proof. Notice that the random assignment of jobs to machines remains unchanged in the described variant of
Algorithm LP ROUNDING. However, for a fixed assignment of jobs to machines, sequencing the jobs according
to Smith's ratio rule on each machine is optimal. In particular, it improves upon the random sequence used in the
final step of Algorithm LP ROUNDING.
In the analysis of Algorithm LP ROUNDING we have always compared the value of the computed solution to
the optimal LP value which is itself a lower bound on the value of an optimal solution. Therefore we can state the
following result on the quality of the LP relaxation:
Corollary 2.7. The linear program (LP R ) is a 2-relaxation for R j r (even without constraints (4)) and a2 -relaxation for R
We show in the following section that (LP R ) without constraints (4) is not better than a 2-relaxation, even for
instances of P . On the other hand, the relaxation can be strengthened by adding the constraints
These constraints ensure that in each time period no job can use the capacity of more than one machine. Unfor-
tunately, we do not know how to use these constraints to get provably stronger results on the quality of the LP
relaxation and better performance guarantees for Algorithm LP ROUNDING.
Notice that the results in Theorem 2.4 and Theorem 2.5 do not directly lead to approximation algorithms for
the considered scheduling problems. The reason is that we cannot solve (LP R ) in polynomial time due to the
exponentially many variables. However, we can overcome this drawback by introducing new variables which are
not associated with exponentially many time intervals of length 1, but rather with a polynomial number of intervals
of geometrically increasing size. In order to get polynomial-time approximation algorithms in this way, we have
to pay for with a slightly worse performance guarantee. For any constant e ? 0 we get approximation algorithms
with performance guarantee 2+ e and 3=2+ e for the scheduling problems under consideration. We elaborate on
this in Section 5.
It is shown in [40] that the ideas and techniques presented in this section and Section 5 can be modified to
construct approximation algorithms for the corresponding preemptive scheduling problems. Notice that, although
the LP relaxation (LP R ) allows preemptions of jobs, it is not a relaxation of R j r it is shown in
[40, Example 2.10.8.] that the right-hand side of (3) can in fact overestimate the actual completion time of a job
in the preemptive schedule corresponding to a solution of (LP R ). However, one can construct an LP relaxation
for the preemptive scheduling problem by replacing (3) with a slightly weaker constraint. This leads to a (3
approximation algorithm for R j r e)-approximation algorithm for R j pmtn j w j C j .
These results can again be slightly improved by using convex quadratic programming relaxations, see [42].
Scheduling with Release Dates
We now consider the special case of m identical parallel machines. The processing requirement and the release
date of job j no longer depend on the machine job j is processed on and are thus denoted by p j and r j , respectively.
As mentioned above, already the problem P2
In this setting, Algorithm LP ROUNDING can be turned into a purely combinatorial algorithm. Taking up an
idea that has been used earlier, e. g., by Chekuri et al. [7], we reduce the identical parallel machine instance to
a single machine instance. However, the single machine is assumed to be m times as fast as each of the original
machines, i. e., the virtual processing time of job j on this virtual single machine is p 0
without loss of generality that p j is a multiple of m). Its weight and its release date remain the same. The crucial
idea for our algorithm is to assign jobs uniformly at random to machines. Then, on each machine, we sequence the
assigned jobs in order of random a-points with respect to a preemptive schedule on the fast single machine.
For 1, the a-point C S
j (a) of job j with respect to a given preemptive schedule S on the fast single
machine is the first point in time when an a-fraction of job j has been completed, i. e., when j has been processed
for a
time units. In particular, C S
j and for
j (0) to be the starting time of job j.
Slightly varying notions of a-points were considered in [31, 19], but their full potential was only revealed when
Chekuri et al. [7] as well as Goemans [14] chose the parameter a at random. The following algorithm may be seen
as an extension of their single machine techniques to identical parallel machines.
Algorithm: RANDOM ASSIGNMENT
Construct a preemptive schedule S on the virtual single machine by scheduling at any point in
time among the available jobs the one with largest w j =p 0
ratio.
For each job j 2 J, draw a j independently at random and uniformly distributed from [0; 1] and
assign j uniformly at random to one of the m machines.
Schedule on each machine i the jobs that were assigned to it nonpreemptively as early as possible
in nondecreasing order of C S
Notice that in the first step whenever a job is released, the job being processed (if any) will be preempted if the
released job has a larger
ratio. An illustration of Algorithm RANDOM ASSIGNMENT can be found in the


Appendix

. The running time of this algorithm is dominated by the effort to compute the preemptive schedule in
the first step. Goemans observed that this can be done in O(nlogn) time using a priority queue [14].
In the following we will show that Algorithm RANDOM ASSIGNMENT can be interpreted as a reformulation of
Algorithm LP ROUNDING for the special case of identical parallel machines. One crucial insight for the analysis
is that the above preemptive schedule on the virtual single machine corresponds to an optimum solution to an LP
relaxation which is equivalent to (LP R ). We introduce a variable y jt for every job j and every time period (t; t +1]
that is set to 1=m if job j is being processed on one of the m machines in this period and to 0 otherwise. Notice
that in contrast to the unrelated parallel machine case we do not need machine dependent variables since there is
no necessity to distinguish between the identical parallel machines. We can express the new variables y jt in the old
variables y i jt by setting
This leads to the following simplified LP (ignoring constraints (4) of (LP R )):
minimize
subject to
y jt
for all
For the special case was introduced by Dyer and Wolsey [10]. They also indicated that it follows
from the work of Posner [32] that the program can be solved in O(nlogn) time. Goemans [13] showed (also for the
case m= 1) that the preemptive schedule that is constructed in the first step of Algorithm RANDOM ASSIGNMENT
defines an optimum solution to (LP P ). This result as well as its proof can be easily generalized to an arbitrary
number of identical parallel machines:
Lemma 3.1. For instances of the problems the relaxation (LP P ) can be solved in O(nlogn) time
and the preemptive schedule on the fast single machine in the first step of Algorithm RANDOM ASSIGNMENT
corresponds to an optimum solution.
Theorem 3.2. Algorithm RANDOM ASSIGNMENT is a randomized 2-approximation algorithm for
Proof. We show that Algorithm RANDOM ASSIGNMENT can be interpreted as a special case of Algorithm LP
ROUNDING. The result then follows from its polynomial running time and Theorem 2.4.
Lemma 3.1 implies that in the first step of Algorithm RANDOM ASSIGNMENT we simply compute an optimum
solution to the LP relaxation (LP P ) which is equivalent to (LP R ) without constraints (4). In particular, the corresponding
solution to (LP R ) is symmetric with regard to the m machines. Therefore, in Algorithm LP ROUNDING
each job is assigned uniformly at random to one of the machines. The symmetry also yields that for each job j the
choice of t j is not correlated with the choice of i in Algorithm LP ROUNDING.
It can easily be seen that the probability distribution of the random variable t j in Algorithm LP ROUNDING
exactly equals the probability distribution of C S
Algorithm RANDOM ASSIGNMENT. For this, observe that
the probability that C S
equals the fraction y jt =p 0
j of job j that is being processed in
this time interval. Moreover, since a j is uniformly distributed in (0;1] each point in (t; t + 1] is equally likely
to be obtained for C S
Therefore, the random choice of C S
Algorithm RANDOM ASSIGNMENT is
an alternative way of choosing t j as it is done in Algorithm LP ROUNDING. Consequently, the two algorithms
coincide for the identical parallel machine case. In particular, the expected completion time of each job is bounded
from above by twice its LP completion time and the result follows by linearity of expectations.
At this point, let us briefly compare the approximation results of this section for the single machine case
related results. If we only work with one a for all jobs instead of individual and independent a j 's
and if we draw a uniformly from [0; 1], then RANDOM ASSIGNMENT precisely becomes Goemans' randomized
2-approximation algorithm RANDOM a for 1jr j j w j C j [14]. Goemans, Queyranne, Schulz, Skutella, and Wang
have improved this result to performance guarantee 1:6853 by using job-dependent a j 's as in Algorithm RANDOM
ASSIGNMENT together with a nonuniform choice of the a j 's [15]. The same idea can also be applied in the
parallel machine setting to get a performance guarantee better than 2 for Algorithm RANDOM ASSIGNMENT. This
improvement, however, depends on m. We refer the reader to the single machine case for details. A comprehensive
treatment and a detailed overview of the concept of a-points for machine scheduling problems can be found in
[40, Chapter 2].
We have already argued in the last section that (LP R ) and thus (LP P ) is a 2-relaxation of the scheduling problem
under consideration:
Corollary 3.3. The relaxation (LP P ) is a 2-relaxation of the scheduling problem and this bound is
tight, even for
Proof. The positive result follows from Corollary 2.7. For the tightness, consider an instance with m machines
and one job of length m and unit weight. The optimum LP completion time is (m+ 1)=2, whereas the optimum
completion time is m. When m goes to infinity, the ratio of the two values converges to 2.
Our approximation result for identical parallel machine scheduling can be directly generalized to the corresponding
preemptive scheduling problem. In preemptive schedules a job may repeatedly be interrupted and
continued later on another (or the same) machine. It follows from the work of McNaughton [24] that already
is NP-hard since there always exists an optimal nonpreemptive schedule and the corresponding
nonpreemptive problem is NP-hard. We make use of the following observation:
Lemma 3.4. The linear program (LP P ) is also a relaxation of the preemptive problem
Proof. Since all release dates and processing times are integral, there exists an optimal preemptive schedule where
preemptions only occur at integral points in time. Take such an optimal schedule S and construct the corresponding
feasible solution to (LP P ) by setting y being processed on one of the m machines within the time
interval (t; t +1] and y It is an easy observation that C LP
j and equality holds if and only if job
j is continuously processed in the time interval (C S
Thus, the value of the constructed solution to (LP P )
is a lower bound on the value of an optimal schedule.
This observation leads to the following results which generalize Theorem 3.2 and Corollary 3.3.
Corollary 3.5. The value of the (nonpreemptive) schedule constructed by Algorithm RANDOM ASSIGNMENT
is not worse than twice the value of an optimum preemptive schedule. Moreover, the relaxation (LP P ) is a 2-
relaxation of the scheduling problem and this bound is tight.
The 2-approximation algorithm in Corollary 3.5 improves upon a performance guarantee of 3 due to Hall,
Schulz, Shmoys, and Wein [18]. Another consequence of our considerations is the following result on the power
of preemption:
Corollary 3.6. For identical parallel machine scheduling with release dates so as to minimize the weighted sum
of completion times, the value of an optimal nonpreemptive schedule is at most twice as large as the value of an
optimal preemptive one.
Moreover, the techniques in Algorithm LP ROUNDING can be used to convert an arbitrary preemptive schedule
into a nonpreemptive one such that the value increases at most by a factor of 2: for a given preemptive schedule,
construct the corresponding solution to (LP P ) or (LP R ), respectively. The value of this feasible solution to the LP
relaxation is a lower bound on the value of the given preemptive schedule. Using Algorithm LP ROUNDING, the
solution to (LP R ) can be turned into a nonpreemptive schedule whose expected value is bounded by twice the value
of the LP solution, and thus by twice the value of the preemptive schedule we started with. This improves upon a
bound of 7=3 due to Phillips et al. [29].
Algorithm RANDOM ASSIGNMENT can easily be turned into an online algorithm. There are several different
online paradigms that have been studied in the area of scheduling, see [38] for a survey. We consider the setting
where jobs continually arrive over time and, for each time t, we must construct the schedule until time t without
any knowledge of the jobs that will arrive afterwards. In particular, the characteristics of a job, i. e., its processing
time and its weight become only known at its release date.
In order to apply Algorithm RANDOM ASSIGNMENT in the online setting, note that for each job j its random
variable a j can be drawn immediately when the job is released since there is no interdependency with any other
decisions of the randomized algorithm. The same holds for the random machine assignments. Moreover, the
preemptive schedule in the first step can be constructed until time t without the need of any knowledge of jobs that
are released afterwards. Furthermore, it follows from the analysis in the proof of Lemma 2.3 that we get the same
performance guarantee if job j is not started before time t j (respectively C S
Thus, in the online variant of
Algorithm RANDOM ASSIGNMENT we schedule the jobs as early as possible in order of nondecreasing C S
with the additional constraint that no job j may start before time C S
The following result improves upon the
competitive ratio 2:89
Corollary 3.7. The online variant of Algorithm RANDOM ASSIGNMENT achieves competitive ratio 2.
The perhaps most appealing aspect of Algorithm RANDOM ASSIGNMENT is that the assignment of jobs to
machines does not depend on job characteristics; any job is put with probability 1=m to any of the machines. This
technique also proves useful for the problem without (nontrivial) release dates:
Theorem 3.8. Assigning jobs independently and uniformly at random to the machines and then applying Smith's
ratio rule on each machine is a 3=2-approximation algorithm for P There exist instances for which this
bound is asymptotically tight.
Proof. First notice that the described algorithm exactly coincides with Algorithm RANDOM ASSIGNMENT (LP
ROUNDING, respectively). Because of the negative result in Corollary 3.3, we cannot derive the bound 3=2 by
comparing the expected value of the computed solution to the optimal value of (LP P ). Remember that we used a
stronger relaxation including constraints (4) in order to derive this bound in the unrelated parallel machine setting.
However, as a result of Lemma 2.3 we get
since the second term on the right-hand side of (6) is equal to p j for the case of identical parallel machines. Since
both
are lower bounds on the value of an optimal solution, the result follows.
In order to show that the performance guarantee 3=2 is tight, we consider instances with m identical parallel
machines and m jobs of unit length and weight. We get an optimal schedule with value m by assigning one job
to each machine. On the other hand we can show that the expected completion time of a job in the schedule
constructed by random machine assignment is 3=2 \Gamma 1=2m which converges to 3=2 for increasing m. Since the
jobs, we can without loss of generality schedule on each machine the jobs that were
assigned to it in a random order. Consider a fixed job j and the machine i it has been assigned to. The probability
that a job k 6= j was assigned to the same machine is 1=m. In this case k is processed before j on the machine with
probability 1=2. We therefore get E[C j
2m .
Quite interestingly, the derandomized variant of this algorithm precisely coincides with the WSPT-rule for
which Kawaguchi and Kyan proved performance guarantee (1
2)=2  1:21 [22]: list the jobs according to
nonincreasing ratios w j =p j and schedule the next job whenever a machine becomes available. Details for the
derandomization are given in Section 4. While the proof given by Kawaguchi and Kyan is somewhat complicated,
our simpler randomized analysis yields performance guarantee 3=2 for their algorithm. However, this weaker
result also follows from the work of Eastman, Even, and Isaacs [11] who gave a combinatorial lower bound for
which coincides with the lower bound given by (LP P ). The latter observation is due to Uma and Wein
[48] and Williamson [50].
Derandomization
Up to now we have presented randomized algorithms that compute a feasible schedule the expected value of which
can be bounded from above in terms of the optimum solution to the scheduling problem under consideration. This
means that our algorithms will perform well on average; however, we cannot give a firm guarantee for the performance
of any single execution. From a theoretical point of view it is perhaps more desirable to have (deterministic)
algorithms that obtain a certain performance in all cases.
One of the most important techniques for derandomization is the method of conditional probabilities. This
method is implicitly contained in a paper of Erdos and Selfridge [12] and has been developed in a more general
context by Spencer [45]. The idea is to consider the random decisions in a randomized algorithm one after another
and to always choose the most promising alternative. This is done by assuming that all of the remaining decisions
will be made randomly. Thus, an alternative is said to be most promising if the corresponding conditional
expectation for the value of the solution is as small as possible.
The randomized algorithms in this paper can be derandomized by the method of conditional probabilities. We
demonstrate this technique for the most general problem R j r Algorithm LP ROUNDING. Making
use of Remark 2.1 and Lemma 2.3 we consider the variant of this algorithm where we set t being
assigned to the machine-time pair (i; t) (ties are broken by prefering jobs with smaller indices). Thus, we have to
construct a deterministic assignment of jobs to machine-time pairs.
Our analysis of Algorithm LP ROUNDING in the proof of Lemma 2.3 does not give a precise expression for
the expected value of the computed solution but only an upper bound. Hence, for the sake of a more accessible
derandomization, we modify Algorithm LP ROUNDING by replacing its last step with the following variant:
3') Schedule on each machine i the jobs that were assigned to it nonpreemptively in nondecreasing
order of t j , where ties are broken by preferring jobs with smaller indices. At the starting time of
job j the amount of idle time on its machine has to be exactly t j .
for each job j that has been assigned to machine i and t j 6 t k if job k is scheduled after job j, Step 3'
defines a feasible schedule. In the proof of Lemma 2.3 we have bounded the idle time before the start of job j
on its machine from above by t j . Thus, the analysis still works for the modified Algorithm LP ROUNDING. The
main advantage of the modification of Step 3 is that we can now give precise expressions for the expectations and
conditional expectations of completion times.
Let y be the optimum solution we started with in the first step of Algorithm LP ROUNDING. Using the same
arguments as in the proof of Lemma 2.3 we get the following expected completion time of job j in the schedule
constructed by our modified Algorithm LP ROUNDING
y ikt
Moreover, we are also interested in the conditional expectation of j's completion time if some of the jobs have
already been assigned to a machine-time pair. Let K ' J be such a subset of jobs. For each job k 2 K the 0=1-
variable x ikt for t ? r ik indicates whether k has been assigned to the machine-time pair (i; t) not
enables us to give the following expressions for the conditional expectation of j's completion time.
If j 62 K we get
y ikt
and, if j 2 K, we get
where (i; t) is the machine-time pair job j has been assigned to, i. e., x 1. The following lemma is the most
important part of the derandomization of Algorithm LP ROUNDING.
Lemma 4.1. Let y be the optimum solution we started with in the first step of Algorithm LP ROUNDING, K ' J,
and x a fixed assignment of the jobs in K to machine-time pairs. Furthermore let j 2 J nK. Then, there exists an
assignment of j to a machine-time pair (i; t) (i. e., x i t such that
6 EK;x
Proof. Using the formula of total expectation, the conditional expectation on the right-hand side of (11) can be
written as a convex combination of conditional expectations E K[f jg;x
\Theta

over all possible assignments of
job j to machine-time pairs (i; t) with coefficients y i jt
We therefore get a derandomized version of Algorithm LP ROUNDING if we replace the second step by
0; x:=0; for all j 2 J do
i) for all possible assignments of job j to machine-time pairs (i; t) (i. e., x i
\Theta

ii) determine the machine-time pair (i; t) that minimizes the conditional expectation in i);
set K := K[f jg; x
Notice that we have replaced Step 3 of Algorithm LP ROUNDING by 3' only to give a more accessible analysis
of its derandomization. Since the value of the schedule constructed in Step 3 is always at least as good as the one
constructed in Step 3', the following theorem can be formulated for Algorithm LP ROUNDING with the original
Step 3.
Theorem 4.2. If we replace Step 2 in Algorithm LP ROUNDING with 2' we get a deterministic algorithm whose
performance guarantee is at least as good as the expected performance guarantee of the randomized algorithm.
Moreover, the running time of this algorithm is polynomially bounded in the number of variables of the LP relaxation

Proof. The result follows by an inductive use of Lemma 4.1. The computation of (9) and (10) is polynomially
bounded in the number of variables. Therefore, the running time of each of the n iterations in Step 2' is polynomially
bounded in this number.
The same derandomization also works for the polynomial time algorithms that are based on interval-indexed LP
relaxations described in Section 5. Since these LP relaxations only contain a polynomial number of variables, the
running time of the derandomized algorithms is also bounded by a polynomial in the input size of the scheduling
problem. Notice that, in contrast to the situation for the randomized algorithms, we can no longer give job-by-job
bounds for the derandomized algorithms.
An interesting application of the method of conditional probabilities is the derandomization of Algorithm
RANDOM ASSIGNMENT in the absence of release dates. We have already discussed this matter at the end of
Section 3. It essentially follows from the considerations above that the derandomized version of this algorithm
always assigns a job to the machine with the smallest load so far if we consider the jobs in order of nonincreasing
. Thus, the resulting algorithm coincides with the WSPT-rule analyzed by Kawaguchi and Kyan [22].
5 Interval-Indexed LP Relaxations
As mentioned earlier, our LP-based algorithms for unrelated parallel machine scheduling suffer from the exponential
number of variables in the corresponding LP relaxation (LP R ). However, we can overcome this drawback by
using new variables which are not associated with exponentially many time intervals of length 1, but rather with
a polynomial number of intervals of geometrically increasing size. This idea was earlier introduced by Hall et al.
[19]. We show how Algorithm LP ROUNDING can be turned into a polynomial time algorithm for R j r
at the cost of an increase in the performance guarantee to 2 e. The same technique can be used to derive a
e)-approximation algorithm for R
For a given h ? 0, L is chosen to be the smallest integer such that (1 Consequently, L is
polynomially bounded in the input size of the considered scheduling problem. Let I
\Theta
and for 1 6 ' 6 L let
I

. We denote with jI ' j the length of the '-th interval, i. e., jI '
To simplify notation we define (1 +h) '\Gamma1 to be 1
with the following interpretation: y is the time job j is processed on machine i within time
interval I ' , or, equivalently: (y i j' \Delta jI ' j)=p i j is the fraction of job j that is being processed on machine i within I ' .
Consider the following linear program in these interval-indexed variables:
minimize
subject to
for all
Consider a feasible schedule and assign the values to the variables y i j' as defined above. This solution is
clearly feasible: Constraints (12) are satisfied since a job j consumes units if it is processed on machine
constraints (13) are satisfied since the total amount of processing on machine i of jobs that are processed within
the interval I ' cannot exceed its size. Finally, if job j is continuously being processed between C
machine h, then the right-hand side of equation (14) is a lower bound on the real completion time. Thus, (LP h
R ) is
a relaxation of the scheduling problem R j r
Since (LP
R ) is of polynomial size, an optimum solution can be computed in polynomial time. We rewrite
Algorithm LP ROUNDING for the new LP:
Algorithm: LP ROUNDING
Compute an optimum solution y to (LP h
Assign each job j to a machine-interval pair (i; I ' ) independently at random with probability
from the chosen time interval I ' independently at random with uniform
distribution.
On each machine i schedule the jobs that were assigned to it in order of nondecreasing t j .
The following lemma is a reformulation of Lemma 2.2 b) for the new situation and can be proved analogously.
Lemma 5.1. The expected processing time of each job j 2 J in the schedule constructed by Algorithm LP ROUNDING
is equal to  m
Theorem 5.2. The expected completion time of each job j in the schedule constructed by Algorithm LP ROUNDING
is at most 2 \Delta (1 +h) \Delta C LP
.
Proof. We argue almost exactly as in the proof of Lemma 2.3, but use Lemma 5.1 instead of Lemma 2.2 b). We
consider an arbitrary, but fixed job j 2 J. We also consider a fixed assignment of j to machine i and time interval I ' .
Again, the conditional expectation of j's starting time equals the expected idle time plus the expected processing
time on machine i before j is started.
With similar arguments as in the proof of Lemma 2.3, we can bound the sum of the idle time plus the processing
time by 2 This, together with Lemma 5.1 and (14) yields the theorem.
For any given e ? 0 we can choose e)-approximation
algorithm for the problem R j r
R ) is a
6 Concluding Remarks and Open Problems
In this paper, we have developed LP-based approximation algorithms for different scheduling problems and in
doing so we have also gained some insight of the quality of the employed time-indexed LPs. A number of open
problems arises from this and related research, and in the following wrap up we distinguish between the off-line
and the on-line setting.
Our central off-line result is the (2+e)-approximation for R j r there exist instances which show
that the underlying LP relaxation ((LP R ) without inequalities (4)) is indeed not better than a 2-relaxation. However,
it is open whether the quality of (LP R ) (with (4) and/or (7)) is better than 2 and therefore also whether it can be
used to derive an approximation algorithm with performance guarantee strictly less than 2. On the negative side,
In other words, the best known approximation algorithm for R j r
performance guarantee 2 (we proved 2+ e here and [42] gets rid of the e using a convex quadratic relaxation), but
the only known limit to its approximation is the non-existence of a polynomial-time approximation scheme, unless
NP. The situation for R j j w j C j is similar. (LP R ) is a 3=2-relaxation, the quality of (LP R ) together with (7) is
unknown, the 3=2-approximation given in [41] (improving upon the (3=2+e)-approximation in Section 2) is best
known, and again there cannot be a PTAS, unless As far as identical parallel machines are concerned,
one important property of our 2-approximation algorithm for is that it runs in time O(nlogn). The
running time of the recent PTAS is O
[6]. The other important feature of the O(nlogn)
algorithm is that it is capable of working in an on-line context as well, which brings us to the second set of open
problems.
If jobs arrive over time and if the performance of algorithms is measured in terms of their competitiveness
to optimal off-line algorithms, it is theoretically of the utmost importance to distinguish between deterministic
and randomized algorithms. For identical parallel machine scheduling to minimize total weighted completion
time, there is a significant gap between the best-known deterministic lower bound and the competitive ratio of
the best-known deterministic algorithm. The lower bound of 2 follows from the fact that for on-line single machine
scheduling to minimize total completion time no deterministic algorithm can have competitive ratio less
than 2 [21, 46]. A (4 e)-competitive algorithm emerges from a more general framework [19, 18]. For randomized
algorithms, our understanding seems slightly better. The best-known randomized lower bound of e=(e \Gamma 1) is
again inherited from the single machine case [47, 49], and there is a randomized 2-competitive algorithm given in
the paper in hand.

Acknowledgements

.
The authors are grateful to Chandra S. Chekuri, Michel X. Goemans, and David B. Shmoys for helpful comments
on an earlier version of this paper [36].



--R

Competitive distributed job scheduling

Resource scheduling for parallel database and scientific applications
Improved scheduling algorithms for minsum criteria

Approximation schemes for minimizing average weighted completion time with release dates.
Approximation techniques for average completion time scheduling
Approximation algorithms for precedence-constrained scheduling problems on parallel machines that run at different speeds
Deterministic load balancing in computer networks
Formulating the single machine sequencing problem with release dates as a mixed integer program
Bounds for the optimal scheduling of n jobs on m processors

A supermodular relaxation for scheduling with release dates

Single machine scheduling with release dates.

RINNOOY KAN
Scheduling to minimize average completion time: Off-line and on-line approximation algorithms
Scheduling to minimize average completion time: Off-line and on-line algorithms

Optimal on-line algorithms for single-machine schedul- ing
Worst case bound of an LRF schedule for the mean weighted flow-time problem
RINNOOY KAN
Management Science

Randomized approximation algorithms in combinatorial opti- mization
Randomized Algorithms
Approximation bounds for a general class of precedence constrained parallel machine scheduling problems
Improved bounds on relaxations of a parallel machine scheduling problem
Task scheduling in networks

A sequencing problem with release dates and clustered jobs
A technique for provably good algorithms and algorithmic proofs
Scheduling to minimize total weighted completion time: Performance guarantees of LP-based heuristics and lower bounds
New approximations and LP lower bounds



An approximation algorithm for the generalized assignment problem
Approximation and Randomization in Scheduling


A PTAS for minimizing the weighted sum of job completion times on parallel machines
Various optimizers for single-stage production
Ten Lectures on the Probabilistic Method
Cited as personal communication in
How low can't you go?
On the relationship between combinatorial and LP-based approaches to NP-hard scheduling problems
PhD thesis
Cited as personal communication in
--TR

--CTR
Feng Lu , Dan C. Marinescu, An R || Cmax Quantum Scheduling Algorithm, Quantum Information Processing, v.6 n.3, p.159-178, June      2007
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
Martin Skutella, Convex quadratic and semidefinite programming relaxations in scheduling, Journal of the ACM (JACM), v.48 n.2, p.206-242, March 2001
on-line algorithm;scheduling;linear programming relaxation;randomized rounding;approximation algorithm