FACHBEREICH 3
MATHEMATIK
RANDOM–BASED SCHEDULING
by
ANDREAS S. SCHULZ MARTIN SKUTELLA
No. 549/1997
Random–Based Scheduling
New Approximations and LP Lower Bounds
(Extended Abstract)
Andreas S. Schulz and Martin Skutella
Technische Universit¨at Berlin,
Fachbereich Mathematik, MA 6–1,
Straße des 17. Juni 136, 10623 Berlin, Germany,
E-mail
schulz,skutella
@math.tu-berlin.de
Abstract. Three characteristics encountered frequently in real-world machine
scheduling are jobs released over time, precedence constraints between jobs, and
average performance optimization. Thegeneral constrained one-machine schedul-
ing problem to minimize the average weighted completion time not only captures
these features, but also isan important building block for more complex problems
involving multiple machines.
In this context, the conversion of preemptive to nonpreemptive schedules has
been established as a strong and useful tool for the design of approximation algo-
rithms. The preemptive problem is already NP-hard, but one can generate good
preemptive schedules from LP relaxations in time-indexed variables. However, a
straightforward combination of these two components does not directly lead to
improved approximations. By showing schedules in slow motion, we introduce a
new point of view on the generation of preemptive schedules from LP-solutions
which also enables us to give a better analysis.
Specifically, this leads to a randomized approximation algorithm for the general
constrained one-machine scheduling problem with expected performance guar-
antee e. This improves upon the best previously known worst-case bound of 3. In
the process, we also give randomized algorithms for related problems involving
precedences that asymptotically match the best previously known performance
guarantees.
In addition, by exploiting a different technique, we give a simple 3
2-approxima-
tion algorithm for unrelated parallel machine scheduling to minimize the average
weighted completion time. It relies on random machine assignments where these
random assignments are again guided by an optimum solution to an LP relax-
ation. For the special case of identical parallel machines, this algorithm is as
simple as the one of Kawaguchi and Kyan [KK86], but allows for a remarkably
simpler analysis. Interestingly, its derandomized version actually is the algorithm
of Kawaguchi and Kyan.
1 Introduction
The main results of this paper are twofold. First, we give an approximation algorithm
for the general constrained single machine scheduling problem to minimize the aver-
age weighted completion time. It has performance guarantee ewhereas the best previ-
ously known worst-case bound is 3 [Sch96]. Second, we present another approximation
algorithm for the model with unrelated parallel machines (but with independent jobs
without non-trivial release dates) that has performance guarantee 3
2. Previously, a 2–
approximationalgorithmwas known [SS97]. Our first contributionis based on and mo-
tivatedbyearlierwork ofHall, Shmoys, andWein [HSW96],Goemans[Goe96,Goe97],
and Chekuri, Motwani, Natarajan, and Stein [CMNS97]; the second one builds on ear-
lier research by the authors [SS97]. All this work was in turn initiated by a paper of
Phillips, Stein, and Wein [PSW95].
The clamp spanning our two main results is the use of randomness which in both
cases is guided by optimum solutions to related LP relaxations of these problems.
Hence, our algorithms actually are randomized approximation algorithms. A random-
ized ρ–approximationalgorithmis an algorithm that producesa feasible solution whose
expected value is within a factor of ρof the optimum; ρis also called the expected per-
formance guarantee of the algorithm. However, all algorithms given in this paper can
be derandomized with no difference in performance guarantee, but at the cost of in-
creased running times. For reasons of brevity, most often we omit the technical details
of derandomization.
In the first part, we consider the following model. We are given a set Jof njobs
(or tasks) and a disjunctive machine (or processor). Each job jhas a positive integral
processing time pjand an integral release date rj
0 before which it is not available.
In preemptive schedules, a job may repeatedly be interrupted and continued at a later
point in time. We generally assume that these preemptions only occur at integer points
in time. In nonpreemptive schedules, a job must be processed in an uninterrupted fash-
ion. We denote the completion time of job jin a schedule byCj. In addition,Cj
α
for
0
α
1 denotesthe earliest pointin time whenanα–fractionof jhasbeencompleted,
in particular, Cj
1
Cj;α–points were first used in the context of approximation by
[HSW96]. The starting time of jis denoted by Cj
0
. We also consider precedence
constraints between jobs. If j
kfor j
k
J, it is required that jis completed before
kcan start, i.e., Cj
Ck
0
. We seek to minimize the average weighted completion
time in this setting: a weight wj
0 is associated with each job jand the goal is to
minimize 1
n∑j
JwjCj, or, equivalently, ∑j
JwjCj. In scheduling, it is quite convenient
to refer to the respective problems using the standard classification scheme of Graham
et al. [GLLRK79]. Both problems 1
rj
prec
∑wjCjand 1
rj
pmtn
prec
∑wjCjjust
described are strongly NP-hard. In the second part of this paper, we are given munre-
lated parallel machines instead of a single machine. Each job jhas a positive integral
processing requirement pij which depends on the machine ijob jwill be processed
on. Each job jmust 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 standard notation, this NP-hard problem reads R
∑wjCj.
Chekuri, Motwani, Natarajan, and Stein [CMNS97] give a strong result about con-
verting preemptive schedules to nonpreemptive schedules on a single machine. Con-
sider any preemptive schedule with completion times Cj,j
1
n. Chekuri et al.
show that if αis selected at random in
0
1
with density function eα
e
1
, then the
expected completion time of job jin the schedule produced by sequencing the jobs in
nondecreasing order of α–points is at most e
e
1Cj. This is a deep and in a sense best
possible result. However,in order to get in this manner polynomial-timeapproximation
algorithms for nonpreemptive single machine scheduling problems, one relies on good
(exactor approximate)solutions to the respective preemptiveversion of the problem on
hand. The only case where this immediately led to an improvedperformanceguarantee
was single machine scheduling with release dates (no precedence constraints) to min-
imize the average completion time (unit weights). We therefore suggest to convert so-
calledfractionalschedulesobtainedfromcertainLPrelaxationstoobtainprovablygood
nonpreemptive schedules for problems with precedence constraints and arbitrary (non-
negative)weights. TheLPrelaxationwe exploitis weaker than theoneofHall,Shmoys,
and Wein [HSW96] which they used to derive the first constant-factor approximation
algorithm for 1
rj
prec
∑wjCj. In fact, in contrast to their LP, our LP already is a re-
laxation of the correspondingpreemptive problem1
rj
pmtn
prec
∑wjCj. Hence, we
are also able to give an approximation algorithm for the latter problem. In addition, we
can interpretan LP solutionas a preemptiveschedule,but withpreemptionsat fractional
points in time; schedules of this kind are called fractional. Our way of deriving and an-
alyzing good fractional schedules from LP solutions generalizes the techniques of Hall,
Shmoys, and Wein [HSW96] to this weaker LP relaxation. A somewhat intricate com-
bination of these techniques with the conversion procedure of Chekuri et al. leads then
to approximation algorithms for nonpreemptive single machine scheduling which im-
prove or asymptotically match the best previously known algorithms. Specifically, for
single machine scheduling with precedence constraints and release dates so as to mini-
mize the average weighted completion time, we obtain in this way an e–approximation
algorithm. The approximationalgorithm of Hall, Shmoys, and Wein [HSW96] has per-
formance guarantee 5
83. Inspired by the work of Hall et al., Schulz [Sch96] gave a
3–approximationalgorithm based on a different LP.
Our second technique exploits optimum solutions to LP relaxations of parallel ma-
chine problems in a different way. The key idea, which has been introduced in [SS97],
is to interpret the value of certain LP variables as the probability with which jobs are
assigned to machines. For the quite general model of unrelated parallel machines to
minimize the average weighted completion time, we show by giving an improved LP
relaxation that this leads to a 3
2–approximation algorithm. The first constant-factor
approximation algorithm for this model was also obtained by Hall, Shmoys, and Wein
[HSW96] and has performance guarantee 16
3. This was subsequently improved to 2
[SS97].Oneappealingaspectofthis techniqueisthatinthespecial case ofidenticalpar-
allel machines the derandomized version of our algorithm coincides with the algorithm
of Kawaguchi and Kyan [KK86]; we therefore get a simple proofthat list-scheduling in
order of nonincreasing ratios of weight to processing time is a 3
2–approximation.
The paperis organizedas follows.In Sect. 2, we present thefirst techniquein a quite
general framework. It is best understood by showing schedules in slow motion. Then,
in Sect. 3, we apply this to the general constrained one-machine scheduling problem.
Finally, in Sect. 4, we randomly assign jobs to parallel machines.
2 Showing Schedules in Slow Motion
In addition to the setting described above, we consider instances with soft precedence
constraints which will be denoted by
. For j
k
J,j
krequiresthatCj
α
Ck
α
for 0
α
1. That is, at each point in time the completed fraction of job kmust not be
larger than the completed fraction of its predecessor j.
Of course, if we consider a single machine, it only makes sense to talk about soft
precedence constraints if we allow preemption. However, even for the preemptive case
the step from strong to soft precedence constraints is not a true relaxation for a single
machine. This can be seen by considering the following algorithm:
Algorithm SOFT–TO–STRONG
Input
: fractional schedule Sthat obeys release dates and soft precedence constraints.
Output:
preemptiveschedulethatobeysreleasedatesandstrongprecedenceconstraints.
sort: Sort the jobs in order of nondecreasing completion times in the
given schedule S.
schedule: Construct a new schedule by scheduling at any point in time the
first available job in this list.
Notice that Algorithm SOFT–TO–STRONG usually producesa preemptiveschedule.
Whenever a job is released, the job being processed (if any) will be preempted if the
released job has smaller completion time in S. An example for Algorithm SOFT–TO–
STRONG is given in the last two rows of Fig. 2.
Lemma 1. Given a fractional schedule to an instance of 1
rj
pmtn
prec
∑wjCj, Al-
gorithm SOFT–TO–STRONG constructs in time O
nlogn
a preemptive schedule obey-
ing the corresponding strong precedence constraints and release dates with no increase
in completion times.
Proof. We suspect the lemma to belong to the folklore of this field; since we could not
explicitly find it in the literature, however, we providea proof for the sake of complete-
ness. The reasoning is quite similar to the one given in [HSSW96, Proof of Lemma 2.8]
for a rather different result. W.l.o.g., we assume rj
rkwhenever j
kfor j
k
J.
We denote the completion time of a job jin the given schedule Sby C
jand in the
constructed schedule byCj.
By construction, no job is processed before its release date in the new schedule.
Moreover,ajobisonlypreemptedif anotherjobis releasedatthattime.Therefore,since
all the release dates are integral, Algorithm SOFT–TO–STRONG creates preemptions
only at integral points in time.
Furthermore, for j
kthe feasibility of the given schedule yields C
j
C
k. Thus,
because of rj
rkand our ordering of jobs, kis not processed before jis completed
and the strong precedence constraints are obeyed.
It remains to show thatCj
C
jfor each job j
J. Let t
0 be the earliest point in
time such that there is no idle time in
t
Cj
and only jobs kwithC
k
C
jare processed
on the machine in the period from tto Cjin the new schedule. We denote the set of
these jobs by K. By construction rk
tfor all k
Kand thusC
j
t
∑k
Kpk. On the
other hand, the definition of Kimplies Cj
t
∑k
Kpkand thereforeCj
C
j.
Finally, the running time of Algorithm SOFT–TO–STRONG is dominated by the
sorting step and is therefore O
nlogn
.
If all the release dates are 0 the schedule constructed in Algorithm SOFT–TO–
STRONG is nonpreemptive.Thus, we get the following corollary.
Corollary 2. Given a fractional schedule to an instance of 1
pmtn
prec
∑wjCj, Al-
gorithm SOFT–TO–STRONG computes in time O
nlogn
a nonpreemptive schedule
obeying the precedence constraints with no increase in completion times.
It follows that the NP-hard problem 1
prec
∑wjCj[Law78] can be reduced to the
problem 1
pmtn
prec
∑wjCjwhich is therefore NP-hard, too. In order to develop
approximation algorithms for all these problems we now introduce an LP relaxation
of 1
rj
pmtn
prec
∑wjCjwhose optimum value serves as a surrogate for the true
optimum in our estimations. The LP relaxation is an immediate extension of a time-
indexed LP proposed by Dyer and Wolsey [DW90] for the problem without precedence
constraints. Here, time is discretized into the periods
t
t
1
,t
0
1
Twhere T
is the planning horizon, say T:
maxj
Jrj
∑j
Jpj
1. We have a variable yjt for
every job jand every time period
t
t
1
representing the fraction of this period that
is dedicated to the processing of job j.
minimize ∑
j
JwjCj
LP
subject to T
∑
t
rj
yjt
pjfor all j
J(1)
∑
j
Jyjt
1 for t
0
T(2)
1
pj
t
∑
rj
yj
1
pk
t
∑
rk
yk
for all j
kand t
0
T(3)
Cj
pj
2
1
pj
T
∑
t
0
yjt
t
1
2
for all j
J(4)
yjt
0 for all j
Jand t
0
rj
1 (5)
yjt
0 for all j
Jand t
rj
T(6)
Equations (1) say that all the fractions of a job, which are processed in accordance with
the release dates, must sum up to the whole job. Since the machine can process only
one job at a time, the machine capacity constraints (2) must be satisfied. Constraints (3)
say that at any pointt
1 in time the completed fraction of job kmust not be larger than
the completed fraction of its predecessor j.
Consideranarbitraryfeasibleschedule,where job jis being continuouslyprocessed
betweenCj
pjandCjon the machine. Then the expression for Cjin (4) corresponds
to the real completion time, if we assign the values to the LP variables yjt as defined
above, i.e., yjt
1 if jis being processed in the time interval
t
t
1
. If jis not being
continuously processed but preempted once or several times, the expression for Cjin
(4) is a lower bound for the real completion time. Hence,
LP
is a relaxation of the
scheduling problem under consideration.
On the other hand, we can interpret every feasible solution yto
LP
in a natural
way as a fractional schedule which, by (3), softly respects the precedence constraints:
take a linear extension of the precedence constraints and process in each time interval
t
t
1
the occurring jobs jfor time yjt each, in this order; see Fig. 1 for an example.
In the following, we always identify a feasible solution to
LP
with a corresponding
fractional schedule and vice versa. We mutually use the interpretation that seems more
suitable for our purposes.
!!!
!!!
!!!
"""""
"""""
"""""
"""""
"""""
#####
#####
#####
#####
#####
$$$
$$$
$$$
%%%
%%%
%%%
yjt
&
1
2
LP solution fractional schedule
t tt+1 t+2 t+1 t+2
Fig.1. Interpretation of an LP solution as a fractional schedule and vice versa
Thus, from the LP we get a fractional schedule that satisfies the soft precedence
constraints and a lower bound on its total weighted completion time. Of course, this
also is a lower bound for preemptive schedules obeying the precedence constraints,
and, in turn, of nonpreemptiveschedules respecting the precedence constraints. In other
words, the LP is a relaxation of 1
rj
pmtn
prec
∑wjCj, 1
rj
pmtn
prec
∑wjCj,
and 1
rj
prec
∑wjCj. The following example shows that it is not better than a 2–
relaxation for fractional scheduling (and therefore for the other cases as well) even if
all the release dates are 0 and all processing times are 1: let J
('
1
n
)
,wj
0 for
1
j
n
1, wn
1 and j
nfor 1
j
n
1. We get a feasible LP solution if we
schedule in every time interval
t
t
1
for 0
t
n
1 a 1
n–fraction of each job. This
yields the LP completion time
n
1
2 for job n, whereas its optimum completion
time is obviously n.
The following lemma highlights the relation between the LP completion time and
the completion time in the corresponding fractional schedule for a feasible solution to
LP
. The observation in part a) is due to Goemans [Goe97]; an analogous result to
part b) was already given in [HSW96, Lemma 2.1] for a somewhat different LP.
Lemma 3. Consider a feasible solution to
LP
and letCLP
jbe the LP completion time
of j defined in (4). Denote the real completion time in the corresponding fractional
schedule byCj. Then the following holds:
a)
*
1
0Cj
α
dα
CLP
j;
b) Cj
α
1
1
αCLP
jfor any constant α
0
1
and the given bound is tight.
Proof. In order to prove part a) we denote by αtthe fraction of job jthat is in the frac-
tional schedule completed at time t, for t
0
T
1. Thus
αt
T
1
t
0is a monotoni-
cally nondecreasing sequence with α0
0, αT
1
1 andCj
α
t
1 for α
αt
1.
We can therefore write
+
1
0Cj
α
dα
T
∑
t
0
+
αt
,
1
αtCj
α
dα
T
∑
t
0
αt
1
αt
t
1
1
pj
T
∑
t
0
yjt
t
1
1
2
1
pj
T
∑
t
0
yjt
t
1
2
CLP
j
The last equality follows from (1). As a consequence of part a) we get for 0
α
1
1
α
Cj
α
+
1
αCj
x
dx
+
1
0Cj
x
dx
CLP
j
In order to prove the tightness of this bound, we consider a job jwith pj
1, rj
0
and an LP solution satisfying yj0
α
εand yjT
1
α
ε, where ε
0. This yields
CLP
j
1
T
1
α
ε
and Cj
α
T. Thus, for εarbitrarily small and Tarbitrarily
large, the given bound gets tight.
As a consequence of Lemma 3 part b) we know that the value of the fractional
schedule given by an optimum LP solution can be arbitrarily bad compared to the LP
value.GivenanarbitraryLPsolutionandsomeβ
1,thefollowingalgorithmcomputes
a new schedule such that all the completion times of jobs are within a constant factor of
their LP completion times.
Algorithm SLOW–MOTION
Input
: fractional schedule Sobeying release dates and soft precedence constraints, and
a parameter β
1.
Output
: fractional schedule that obeys release dates and soft precedence constraints.
slow motion Consider the given schedule Sas a movie and display it β
times slower than in real time. Mathematically spoken, we
map every point tin time onto β
t. This defines in a natural
way a new schedule S
where job jis being processed for
β
pjtime units.
cut Let tjbe the earliest point in time when job jhas been pro-
cessedfor pjtime units in S
. ConvertS
to a feasibleschedule
S
by leaving the machineidle whenever it processedjob jaf-
ter tj.
The output of Algorithm SLOW–MOTION still allows fractional preemption and
only obeys the soft precedence constraints. But we can overcome these drawbacks if
we use Algorithm SOFT–TO–STRONG as a postprocessing step. Figure 2 shows the
action of Algorithm SLOW–MOTION and the postprocessing with Algorithm SOFT–
TO–STRONG for an example: we are given three jobs J
'
1
2
3
)
with p1
p2
p3
2, r1
0, r2
r3
1 and 2
3. The parameter βis set to 3
2in this example.
!!!!!
!!!!!
!!!!!
"""""
"""""
"""""
########
########
########
########
########
########
$$$$$$$$
$$$$$$$$
$$$$$$$$
$$$$$$$$
$$$$$$$$
$$$$$$$$
%%%%%%%%
%%%%%%%%
%%%%%%%%
%%%%%%%%
%%%%%%%%
%%%%%%%%
&&&&&&&&
&&&&&&&&
&&&&&&&&
&&&&&&&&
&&&&&&&&
&&&&&&&&
''''''''
''''''''
''''''''
((((((((
((((((((
((((((((
)))))
)))))
)))))
*****
*****
*****
+++
+++
+++
,,,
,,,
,,,
--
--
--
..
..
..
///
///
///
///
///
///
000
000
000
000
000
000
111111
111111
111111
111111
111111
111111
22222
22222
22222
22222
22222
22222
33333333333
33333333333
33333333333
44444444444
44444444444
44444444444
5555555
5555555
5555555
6666666
6666666
6666666
77777
77777
77777
77777
77777
77777
88888
88888
88888
88888
88888
88888
9
9
9
9
:
:
:
:
;
;
;
;
<
<
<
<
=
=
=
=
>
>
>
>
?
?
?
?
@
@
@
@
A
A
A
A
B
B
B
B
given schedule:
slow motion:
cut:
soft–to–strong:
0123456789
job 1
job 2
job 3
idle
Fig.2. The two steps in Algorithm SLOW–MOTION together with postprocessing by Algorithm
SOFT–TO–STRONG.
Lemma 4. Algorithm SLOW–MOTION with input β
1computes a feasible fractional
schedule. The completion time of job j equals β
Cj
1
β
whereCjis the completion time
of job j in the given schedule.
Proof. LetCβ
jdenote the completiontime of job jin the schedule constructed by Algo-
rithm SLOW–MOTION.ByconstructionCβ
j
α
β
Cj
α
β
for0
α
1.Inparticular
Cβ
j
0
β
Cj
0
β
rj
rjand Cβ
j
β
Cj
1
β
. Moreover, since Srespects the
soft precedence constraints we get
Cβ
j
α
β
Cj
α
β
β
Ck
α
β
Cβ
k
α
for j
kand 0
α
1. Thus the constructed schedule is feasible.
We would like to mention that Lemma 4 is related to Theorem 2.1 in [HSW96].
As an easy corollary of Lemma 1, Lemma 3 b), and Lemma 4, Algorithm SLOW–
MOTION followed by Algorithm SOFT–TO–STRONG has a performance guarantee of
β2
β
1
for the problem 1
rj
pmtn
prec
∑wjCj. An optimal choice seems to be
β
2 yielding the performance guarantee 4. But one can in fact do better by choosing
βrandomly:
Theorem 5. If one invokes Algorithm SLOW–MOTION with input βsuch that 1
βis
randomly drawn from
0
1
with density function f
x
2x, then the expected comple-
tion time of a job j in the resulting schedule is bounded from above by twice its LP
completion timeCLP
j.
Proof. By Lemma 3 a) and Lemma 4 the expected completion time of jis
+
1
0f
x
1
xCj
x
dx
2
+
1
0Cj
x
dx
2
CLP
j
Since the value of an optimum LP-solution is a lower bound on the value of any
feasible schedule, this randomized algorithm has performance guarantee 2 if we start
with an optimum LP-solution. Using Lemma 1 and Corollary 2 we have thus found
randomized 2–approximationalgorithms for the following problems:
1
rj
pmtn
prec
∑wjCj
1
rj
pmtn
prec
∑wjCj
and 1
prec
∑wjCj
Moreover,we have shown that
LP
is a 2–relaxationfor these problems and that this is
best possible for
LP
. For both problems 1
rj
pmtn
prec
∑wjCjand 1
prec
∑wjCj
2–approximation algorithms based on different LP relaxations and without any usage
of randomness were known before; see [HSSW96] for both algorithms. In addition,
Goemans [Goe96] applied the very same technique as in Theorem 5 to improve the 4–
approximation algorithm of Hall, Shmoys, and Wein [HSW96] for 1
prec
∑wjCjto a
2–approximationalgorithm.
Noticethatwecannotimmediatelysolve
LP
inpolynomialtimesincethereareex-
ponentiallymanyvariables yjt. Thus, up to now, we have onlygiven pseudo-polynomial
approximation algorithms. However, we can overcome this drawback by introducing
new variableswhich are not associated with exponentiallymany time intervals oflength
1, but rather with a polynomial number of intervals of geometrically increasing size.
This idea was introduced earlier by Hall, Shmoys, and Wein [HSW96] and since then
used in several settings, e.g., in [SS97].
However, in order to get polynomial-time approximationalgorithms in this way, we
have to pay for with a slightly worse performanceguarantee.For any constant ε
0 we
get polynomial-time approximation algorithms with performance guarantee 2
εfor
the scheduling problems listed above.
3 An e–Approximation Algorithm for the General Constrained
One–Machine Scheduling Problem
As mentioned earlier, the randomized conversion technique of [CMNS97] transforms
any preemptive schedule into a nonpreemptive one such that the expected completion
time of job jin the nonpreemptive schedule is at most a factor of e
e
1of its com-
pletion time in the preemptive schedule. In addition, it is easy to see that, if the pre-
emptive schedule obeys given precedence constraints the same holds for the produced
nonpreemptive schedule. Hence, if we first use SLOW–MOTION followed by SOFT–
TO–STRONG to get a 2–approximation for 1
rj
pmtn
prec
∑wjCjand then invoke
the conversion algorithm of Chekuri et al., we get a 2e
e
1–approximation algorithm for
1
rj
prec
∑wjCj. Unfortunately, this does not immediately lead to a better perfor-
mance guarantee than the 3–approximation algorithm known before [Sch96]. However,
when we combine both algorithms in a somewhat more intricate way we get a con-
siderably improved performance guarantee. The key idea is that instead of using the
algorithms independently we make the choice of the random variable in the algorithm
of Chekuri et al. dependent on the choice of βin Algorithm SLOW–MOTION.
Consider the following algorithm that makes use of density functions fand gβ
which are subsequently defined.
Algorithm: e–APPROXIMATION
Input
: Instance of 1
rj
prec
∑wjCj.
Output
: Feasible schedule.
1) Compute an optimumsolution to
LP
. Call the correspondingfractionalscheduleS.
2) Draw 1
βrandomly from
0
1
with density function f.
3) Let S
be the fractional schedule producedby SLOW–MOTION with input
S
β
.
4) Draw αrandomly from
0
1
with density function gβ.
5) Construct a nonpreemptive schedule by scheduling the jobs as early as possible in
nondecreasing order of C
j
α
.
Here,C
jis the completion time of job jin the schedule S
. Recall that SLOW–MOTION
guarantees thatC
j
α
C
k
α
for j
kand any α
0
1
. Consequently the schedule
produced by Algorithm e–APPROXIMATION is indeed feasible.
Lemma 6. Let β
1be a constant and gβ
x
1
β
e1
β
1
ex
β, for x
0
1
. Then, for
each job j
J, its expected completion time Eβ
Cj
in the schedule constructed by
e–APPROXIMATION is at most 1
β
e1
β
e1
β
1
C
j.
Proof. (Sketch.) Our analysis almost follows the analysis of [CMNS97] for their con-
version technique with the small, but crucial exception that we utilize the structure
of the fractional schedule S
produced by Algorithm SLOW–MOTION. In fact, as in
[CMNS97] and for the purpose of a more accessible analysis, we do not analyze the
schedule produced by e–APPROXIMATION but rather a more structured one which is,
however, not better than the output of e–APPROXIMATION. This schedule is obtained
by replacing Step 5 with the following procedure:
5’) Take the fractional schedule S
produced by Algorithm SLOW–MOTION. Consider
the jobs j
Jin nonincreasing order of C
j
α
and iteratively change the current
preemptive schedule by applying the following steps:
i) remove the α
pjunits of job jthat are processed before C
j
α
from the ma-
chine and leave it idle within the corresponding time intervals; we say that this
idle time is caused by job j;
ii) postpone the whole processing that is done later thanC
j
α
by pj;
iii) remove the remaining
1
α
–fraction of job jfrom the machine and shrink
the correspondingtime intervals;
iv) process job jin the released time interval
C
j
α
C
j
α
pj
.
Consider an arbitrarybut fixed α
0
1
and a job j. We denotewithCα
jits comple-
tion time in this new schedule. Let Kαbe the set of jobs that complete an α–fraction in
S
beforeC
j
α
, i.e., Kα
'
k
J:C
k
α
C
j
α
)
. Moreover,for a job k
Klet ηk
α
be the fraction of kthat is completed in S
by timeC
j
α
. Then, because of Step 5’, it is
not too difficult to see that
Cα
j
Tj
1
α
∑
k
Kα
pk
∑
k
Kα
ηk
α
pk
where Tjis the total idle time in the schedule S
before jcompletes. The factors α
and ηk
α
purely result from the idle time caused by the respective jobs. This is the
moment we can improve the analysis by exploiting the structure of S
. First, observe
that the necessity of idle time in the schedule is only caused by release dates. Second,
because of the slow motion, no job jstarts before time β
rjin S
. Consequently, we
may further modify the output of Step 5’ by reshrinking the idle time caused by job j
by a factor of β, for all j
J, without violating the feasibility. Therefore we get
Cα
j
Tj
1
α
β
∑
k
Kα
pk
∑
k
Kα
ηk
α
β
pk
Hence,
Eβ
Cj
+
1
0
Tj
1
α
β
∑
k
Kα
pk
∑
k
Kα
ηk
α
β
pk
gβ
α
dα(7)
and a similar argument as the one given by Chekuri et al. [CMNS97] gives the desired
bound.
Lemma 6 together with Lemma 4 yields the following upper bound on the ex-
pected completion time of any job jin the schedule produced by Algorithm e–
APPROXIMATION:
E
Cj
+
1
0f
x
ex
ex
1
CS
j
x
dx
where CS
jis the completion time of job jin schedule Sand 1
βis replaced by x. An
optimal choice of the density function fis f
x
e
1
e
x
. Hence,
E
Cj
e
+
1
0CS
j
x
dx
e
CLP
j
by Lemma 3 a). This eventually gives the following result.
Theorem 7. Algorithm e–APPROXIMATION is an e–approximation algorithm for sin-
gle machine scheduling subject to release dates and precedence constraints so as to
minimize the average weighted completion time.
To summarize where the improvement on 2e
e
1originates from, observe that the
bound (7) is the better the larger βis chosen since the idle time caused by jobs is
shrunken by the factor β. On the other hand, Lemma 4 and Lemma 3 b) show that the
bound on the completion time of any specific job increases as β
2 increases. It is the
balancing of these two effects that leads to the better approximation.
As a consequence of Lemma 4 we know that C
j
α
β
CS
j
α
β
. Hence, Algo-
rithm e–APPROXIMATION nonpreemptively schedules the jobs as early as possible in
nondecreasing order of CS
j
γ
where γ
α
βis randomly drawn from
0
1
with a
certain density function implicitly defined by fand gβ.
Finally, observe that
LP
therefore is an e–relaxation of 1
rj
prec
∑wjCj. Due
to the huge number of variables in this LP relaxation, e–APPROXIMATION also is only
a pseudo-polynomial algorithm. Again, however, we may replace this LP with a sim-
ilar one in interval-indexed variables and this results in a polynomial-time
e
ε
–
approximation algorithm for the general constrained one-machine scheduling problem
1
rj
prec
∑wjCj.
4 List Scheduling with Random Assignments to Parallel Machines
We consider the scheduling problem R
∑wjCj. That is, we are given mmachines and
the processing time of each job j
Jmay depend on the machine iit is processed on;
it is therefore denoted by pij. Each job must be processed on one of the machines, and
may be assigned to any of them. In contrast to [SS97], we use a tighter LP relaxation
in order to get a lower bound for the problem which we then use to give an improved
approximation algorithm. Independently, this improvement has also been derived by
Fabi´an A. Chudak (communicated to us by David B. Shmoys, March 1997) after read-
ing a preliminary version of [SS97] which contained a 2–approximation algorithm for
R
rij
∑wjCj.
Let T
∑j
Jmaxipij
1 and introduce for every job j
J, every machine i
1
m, and every point t
0
Tin time a variable yijt which represents the pro-
cessing time of job jon machine iwithin the time interval
t
t
1
. Equivalently, one
can say that a yijt
pij–fraction of job jis being processed on machine iwithin the time
interval
t
t
1
. The LP is as follows:
minimize ∑
j
JwjCj
LPR
subject to m
∑
i
1
T
∑
t
0
yijt
pij
1 for all j
J(8)
∑
j
Jyijt
1 for i
1
mand t
0
T(9)
Cj
m
∑
i
1
T
∑
t
0
yijt
pij
t
1
2
1
2yijt
for all j
J(10)
Cj
m
∑
i
1
T
∑
t
0yijt for all j
J(11)
yijt
0 for i
1
m,j
J,t
0
T(12)
Equations (8) say that all the fractions of a job must sum up to the processing re-
quirement of the whole job. Since each machine can process only one job at a time,
the machine capacity constraints (9) must be satisfied. Consider an arbitrary feasible
schedule, where job jis being continuously processed between Cj
phj andCjon ma-
chine h. Then the right hand side of (10) corresponds to the real completion time, if
we assign the values to the LP variables yijt as defined above, i.e., yijt
1 if i
h
and t
Cj
phj
Cj
1
, and yijt
0 otherwise. Moreover, the right hand side of (11)
equals the processing time phj of jon machine hin this case and is therefore a lower
bound on the completion time. Hence,
LPR
is a relaxation of the scheduling problem
under consideration.
We can divide the problem to construct a feasible schedule for a given instance into
two steps: in the first step we assign each job to a machine it should be processed on;
in the second step we decide in which order the jobs are processed on each of the m
machines. In fact, we only have to worry about the first step since the second step can
be solved optimally by Smith’s rule [Smi56]: sequence for each machine ithe jobs that
were assigned to it in order of nonincreasing wj
pij. So it remains to decide which job
should be processed on which machine. This is the point where we can make use of
an optimum solution to
LPR
. We may interpret the LP solution as follows: for job j
a fraction of it given by fij
1
pij ∑T
t
0yijt should be processed on machine i. By (8)
these fractions some up to 1 over all machines. Since we are not allowed to divide j
into fractions but have to process it continuously on one machine, we interpret the fij
as probabilities instead. This yields the following algorithm:
Algorithm RANDOM–ASSIGNMENT
Input
: Instance of R
∑wjCj.
Output
: Feasible schedule.
1) Compute an optimum solution to
LPR
.
2) For each job j
J, assign job jto machine iwith probability fij.
3) Schedule on each machine ithe jobs that were assigned to it in order of nonincreas-
ing wj
pij.
Theorem 8. Algorithm RANDOM–ASSIGNMENT has performance guarantee 3
2.
In order to prove Theorem 8 we in fact do not consider Algorithm RANDOM–
ASSIGNMENT but a modified version which is slightly more complicated, not better
than the original algorithm, but easier to analyze. We replace Steps 2 and 3 by
2’) Assign job jto a machine-time pair
i
t
with probability yijt
pij and set tj:
t.
3’) Schedule on each machineithe jobs that were assigned to it in order of nondecreas-
ing tj.
The random assignment of job jto one of the machines in Step 2’ is exactly the same
as in the original algorithm. In addition, we create a random order through the random
variablestj, ties are also broken randomly.Of course,thisrandomorder cannotbe better
than the optimum order given by Smith’s rule. Thus the modified algorithm cannot be
better than the original one and Theorem 8 is a corollary of the following lemma.
Lemma 9. The expected completion time of job j in the schedule constructed by the
modified algorithm is bounded from above by 3
2times the optimum LP completion time
CLP
j, for all j
J.
Proof. We first consider the conditional expectation of j’s completion time under the
assumption that jwas assigned to the machine-time pair
i
t
. We denote this condi-
tional expectation by Eit
Cj
and get
Eit
Cj
pij
∑
k
j
pik
Pr(kon ibefore j)
pij
∑
k
j
pik
t
1
∑
0
yik
pik
1
2
yikt
pik
pij
t
1
∑
0∑
k
j
yik
1
2∑
k
j
yikt
pij
t
1
2
The last inequality follows from the machine capacity constraints (9). Summing over
all possible assignments of jto intervals andmachines we finally boundthe expectation
of j’s completion time as follows:
E
Cj
m
∑
i
1
T
∑
t
0
yijt
pij
Eit
Cj
m
∑
i
1
T
∑
t
0
yijt
pij
t
1
2
yijt
m
∑
i
1
T
∑
t
0
yijt
pij
t
1
2
1
2yijt
1
2
m
∑
i
1
T
∑
t
0yijt
3
2
CLP
j
The last inequality follows from (10) and (11).
Again, we cannot directly solve
LPR
in polynomial time since there are exponen-
tiallymanyvariablesyijt. Thustherunningtime of AlgorithmRANDOM–ASSIGNMENT
is only pseudo-polynomial. However, once more we can overcome this difficulty by
replacing the time-indexed variables with interval-indexed variables. Hence, we get a
polynomial-time approximation algorithm with performance guarantee 3
2
εfor any
constant ε
0.
As a special case of the scheduling problemdiscussed above we now consider iden-
tical parallel machines: the processing time of job jdoes not depend on the machine
it is processed on and it is therefore denoted by pj. A generalization of Smith’s rule to
identical parallelmachinesis the following list schedulingalgorithm:sort the jobs in or-
der of nonincreasing wj
pj; whenever a machine becomes available, the list is scanned
for the first not yet executed job, which is then assigned to the machine. Kawaguchi
and Kyan [KK86] have shown that this simple algorithm has performance guarantee
2
1
2 and that this is best possible for the algorithm. Since their analysis is some-
what complicated we present here a randomized algorithm which is as simple as the
one of Kawaguchi and Kyan but much easier to analyze. Moreover, its derandomiza-
tion by the method of conditionalprobabilities is precisely the algorithm of Kawaguchi
and Kyan.
Algorithm RANDOM–KK
Input
: Instance of P
∑wjCj.
Output
: Feasible schedule.
1) Assign each job randomly (with probability 1
m) to one of the machines.
2) Scheduleoneachmachineithe jobs that wereassignedto iinorderof nonincreasing
wj
pj.
Theorem 10.
a) Algorithm RANDOM–KK has performance guarantee 3
2. Moreover, there exist in-
stances for which this bound is asymptotically tight.
b) Derandomization by the method of conditional probabilities precisely gives the al-
gorithm of Kawaguchi and Kyan.
Proof. Because of Theorem 8 and the construction of Algorithm RANDOM–
ASSIGNMENT it suffices to show that there exists an optimum solution to
LPR
such
that each of the mmachines processes an 1
mfraction of every job. This can be easily
seen in the following way: take an optimum solution yto
LPR
and construct a new
solution y
by setting y
ijt
1
m∑m
h
1yhjt for each i,jand t. This is obviously a feasible
solution to
LPR
with the same objective value and therefore optimal. If we choose this
solution in Step 1 of Algorithm RANDOM–ASSIGNMENT, it obviously does the same
as Algorithm RANDOM–KK.
In order to show that the performance guarantee 3
2is best possible, we consider
instances with midentical parallel machines and mjobs of unit length and weight. We
getanoptimalschedulewithvaluembyassigningonejobto eachmachine.On theother
handwecanshowthat the expectedcompletiontimeof a jobinthescheduleconstructed
by Algorithm RANDOM–KK is 3
2
1
2mwhich converges to 3
2for increasing m. Since
the fraction wj
pjequals 1 for all jobs, we can w.l.o.g. schedule on each machine the
jobs that were assigned to it in a random order. Consider a fixed job jand the machine
iit has been assigned to. The probability that a job k
jwas assigned to the same
machine is 1
m. In this case kis processed before jon the machine with probability 1
2.
We therefore get E
Cj
1
∑k
j1
2m
3
2
1
2m.
The derandomization of Algorithm RANDOM–KK by the method of conditional
probabilities yields: iteratively consider the jobs in order of nonincreasing wj
pjand
assign job jto the machinewith the smallest load so far. This is just anotherformulation
of Kawaguchi and Kyan’s algorithm. The smallest load is bounded from above by the
average load 1
m∑k
jpkwhere we sum over all jobs kthat we considered before j.
Thus the completion time of jis bounded by pj
1
m∑k
jpkwhich exactly equals the
expected completion time of jin Algorithm RANDOM–KK.
As a consequence of the tightness result in Theorem 10 a) we know that the bound
in Theorem 8 is also tight.
References
[CMNS97] C. Chekuri, R. Motwani, B. Natarajan, and C. Stein. Approximation techniques
for average completion time scheduling. In Proceedings of the 8th ACM–SIAM
Symposium on Discrete Algorithms, pages 609 – 618, 1997.
[DW90] M. E. Dyer and L. A. Wolsey. Formulating the single machine sequencing prob-
lem with release dates as a mixed integer program. Discrete Applied Mathematics,
26:255 – 270, 1990.
[GLLRK79] R. L. Graham, E. L. Lawler, J. K. Lenstra, and A. H. G. Rinnooy Kan. Optimization
and approximation in deterministic sequencing and scheduling: A survey. Annals of
Discrete Mathematics, 5:287 – 326, 1979.
[Goe96] M. X. Goemans, June 1996. Personal communication.
[Goe97] M. X. Goemans. Improved approximation algorithms for scheduling with release
dates. In Proceedings of the 8th ACM–SIAM Symposium on Discrete Algorithms,
pages 591 – 598, 1997.
[HSSW96] L. A. Hall, A. S. Schulz, D. B. Shmoys, and J. Wein. Scheduling to minimize av-
erage completion time: Off–line and on–line approximation algorithms. Preprint
516/1996, Department of Mathematics, Technical University of Berlin, Berlin, Ger-
many, 1996. To appear in Mathematics of Operations Research.
[HSW96] L. A. Hall, D. B. Shmoys, and J. Wein. Scheduling to minimize average comple-
tion time: Off–line and on–line algorithms. In Proceedings of the 7th ACM–SIAM
Symposium on Discrete Algorithms, pages 142 – 151, 1996.
[KK86] T. Kawaguchi and S. Kyan. Worst case bound of an LRF schedule for the mean
weighted flow–time problem. SIAM Journal on Computing, 15:1119 – 1129, 1986.
[Law78] E. L. Lawler. Sequencing jobs to minimize total weighted completion time subject
to precedence constraints. Annals of Discrete Mathematics, 2:75 – 90, 1978.
[PSW95] C. Phillips, C. Stein, and J. Wein. Scheduling jobs that arrive over time. In Pro-
ceedings of the Fourth Workshop on Algorithms and Data Structures, number 955 in
Lecture Notes in Computer Science, pages 86 – 97. Springer, Berlin, 1995.
[Sch96] A. S. Schulz. Scheduling to minimize total weighted completion time: Performance
guarantees of LP–based heuristics and lower bounds. In W. H. Cunningham, S. T.
McCormick, and M. Queyranne, editors, Integer Programming and Combinatorial
Optimization, number 1084 in Lecture Notes in Computer Science, pages 301 – 315.
Springer, Berlin, 1996. Proceedings of the 5th International IPCO Conference.
[Smi56] W. E. Smith. Various optimizers for single–stage production. Naval Research and
Logistics Quarterly, 3:59 – 66, 1956.
[SS97] A. S. Schulz and M. Skutella. Scheduling–LPs bear probabilities: Randomized ap-
proximations for min–sum criteria. Preprint 533/1996, Department of Mathematics,
Technical University of Berlin, Berlin, Germany, November 1996; revised March
1997.
Reports from the group
“Algorithmic Discrete Mathematics”
of the Department of Mathematics, TU Berlin
554/1997 Rolf H. M¨
ohring and Matthias M¨
uller–Hannemann: Complexity and Mod-
eling Aspects of Mesh Refinement into Quadrilaterals
551/1997 Hans Bodlaender, Jens Gustedt and Jan Arne Telle: Linear-Time Register
Allocation for a Fixed Number of Registers and no Stack Variables
549/1997 Andreas S. Schulz and Martin Skutella: Random-Based Scheduling: New
Approximations and LP Lower Bounds
536/1996 CynthiaA.Phillips,AndreasS.Schulz,DavidB.Shmoys,CliffStein,andJoel
Wein: Improved Bounds on Relaxations of a Parallel Machine Scheduling Problem
535/1996 Rainer Schrader, Andreas S. Schulz, and Georg Wambach: Base Polytopes
of Series-Parallel Posets: Linear Description and Optimization
533/1996 Andreas S. Schulz and Martin Skutella: Scheduling–LPs Bear Probabilities:
Randomized Approximations for Min–Sum Criteria
530/1996 Ulrich H. Kortenkamp, J¨
urgen Richter-Gebert, Aravamuthan Sarangarajan,
and G¨
unter M. Ziegler: Extremal Properties of 0/1-Polytopes
524/1996 Elias Dahlhaus, Jens Gustedt and Ross McConnell: Efficient and Practical
Modular Decomposition
523/1996 Jens Gustedt and Christophe Fiorio: Memory Management for Union-Find
Algorithms
520/1996 Rolf H. M¨
ohring, Matthias M¨
uller-Hannemann, and Karsten Weihe: Mesh
Refinement via Bidirected Flows: Modeling, Complexity, and Computational Re-
sults
519/1996 Matthias M¨
uller-Hannemannand Karsten Weihe: MinimumStrictly Convex
Quadrangulations of Convex Polygons
517/1996 Rolf H. M¨
ohring, Markus W. Sch¨
affter, and Andreas S. Schulz: Scheduling
Jobs with Communication Delays: Using Infeasible Solutions for Approximation
516/1996 Leslie A. Hall, Andreas S. Schulz, David B. Shmoys, and Joel Wein: Schedul-
ing to Minimize Average Completion Time: Off-line and On-line Approximation
Algorithms
515/1996 Christophe Fiorio and Jens Gustedt: VolumeSegmentationof 3-dimensional
Images
514/1996 Martin Skutella: Approximation Algorithms for the Discrete Time-Cost
Tradeoff Problem
509/1996 Soumen Chakrabarti, Cynthia A. Phillips, Andreas S. Schulz, David B.
Shmoys, Cliff Stein, and Joel Wein: Improved Scheduling Algorithms for Minsum
Criteria
508/1996 Rudolf M¨
uller and Andreas S. Schulz: Transitive Packing
506/1996 Rolf H. M¨
ohring and Markus W. Sch¨
affter: A Simple Approximation Algo-
rithm for SchedulingForests with Unit Processing Times and Zero-OneCommuni-
cation Delays
505/1996 Rolf H. M¨
ohring and Dorothea Wagner: Combinatorial Topics in VLSI De-
sign: An Annotated Bibliography
504/1996 Uta Wille: The Role of Synthetic Geometry in Representational Measure-
ment Theory
502/1996 Nina Amenta andG¨
unter M.Ziegler: DeformedProductsandMaximalShad-
ows of Polytopes
500/1996 Stephan Hartmann and Markus W. Sch¨
affter and Andreas S. Schulz: Switch-
box Routing in VLSI Design: Closing the Complexity Gap
498/1996 Ewa Malesinska, Alessandro Panconesi: On the Hardness of Allocating Fre-
quencies for Hybrid Networks
496/1996 J¨
org Rambau: Triangulations of Cyclic Polytopes and higher Bruhat Orders
Reports may be requested from: S. Marcus
Fachbereich Mathematik, MA 6–1
TU Berlin
Straße des 17. Juni 136
D-10623 Berlin – Germany
e-mail: [email protected]
Reports are available via anonymous ftp from: ftp.math.tu-berlin.de
cd pub/Preprints/combi
file Report–
number
–
year
.ps.Z
