Single Machine Scheduling with Release Dates.
We consider the scheduling problem of minimizing the average weighted completion time of n jobs with release dates on a single machine. We first study two linear programming relaxations of the problem, one based on a time-indexed formulation, the other on a completion-time formulation.  We show their equivalence by proving that a O(n log n) greedy algorithm leads to optimal solutions to both relaxations. The proof relies on the notion of mean busy times of jobs, a concept which enhances our understanding of these LP relaxations. Based on the greedy solution, we describe two simple randomized approximation algorithms, which are guaranteed to deliver feasible schedules with expected objective function value within factors of 1.7451 and 1.6853, respectively, of the optimum.  They are based on the concept of common and independent $\alpha$-points, respectively.  The analysis implies in particular that the worst-case relative error of the LP relaxations is at most 1.6853, and we provide instances showing that it is at least $e/(e-1) \approx 1.5819$.  Both algorithms may be derandomized; their deterministic versions run in O(n2) time.  The randomized algorithms also apply to the on-line setting, in which jobs arrive dynamically over time and one must decide which job to process without knowledge of jobs that will be released afterwards.
Introduction
We study the single-machine scheduling problem with release dates in which the objective is to
minimize a weighted sum of completion times. It is dened as follows. A set ng
of n jobs has to be scheduled on a single disjunctive machine. Job j has a processing time
and is released at time r j  0. We assume that release dates and processing times are
integral. The completion time of job j in a schedule is denoted by C j . The goal is to nd a
non-preemptive schedule that minimizes
where the w j 's are given positive weights.
M.I.T., Department of Mathematics, Room 2-351, 77 Massachusetts Avenue, Cambridge, MA 02139, USA.
y University of British Columbia, Faculty of Commerce and Business Administration, Vancouver, B.C., Canada
V6T 1Z2. Email: maurice.queyranne@commerce.ubc.ca
z M.I.T., Sloan School of Management, Room E53-361, 77 Massachusetts Avenue, Cambridge, MA 02139, USA.
x Technische Universitat Berlin, Fakultat II { Mathematik und Naturwissenschaften, Institut fur Mathematik,
MA 6-1, Strae des 17. Juni 136, 10623 Berlin, Germany. Email: skutella@math.tu-berlin.de
{ PeopleSoft Inc., San Mateo, CA, USA 94404. Email: Yaoguang Wang@peoplesoft.com
In the classical scheduling notation [12], this problem is denoted by 1j r . It is strongly
NP-hard, even if w
One of the key ingredients in the design and analysis of approximation algorithms as well
as in the design of implicit enumeration methods is the choice of a bound on the optimal value.
Several linear programming based as well as combinatorial lower bounds have been proposed
for this well studied scheduling problem, see for example, Dyer and Wolsey [9], Queyranne [22],
and Queyranne and Schulz [23], as well as Belouadah, Posner and Potts [4]. The LP relaxations
involve a variety of dierent types of variables which, e. g., either express whether job j is completed
at time t (non-preemptive time-indexed relaxation), or whether it is being processed at
time t (preemptive time-indexed relaxation), or when job j is completed (completion time relax-
ation). Dyer and Wolsey show that the non-preemptive time-indexed relaxation is stronger than
the preemptive time-indexed relaxation. We will show that the latter relaxation is equivalent to
the completion time relaxation that makes use of the so-called shifted parallel inequalities. In
fact, it turns out that the polyhedron dened by these inequalities is supermodular and hence
one can optimize over it by using the greedy algorithm. A very similar situation arises in [24].
The greedy solution may actually be interpreted in terms of the following preemptive schedule,
which we call the LP schedule: at any point in time it schedules among the available jobs one
with the largest ratio of weight to processing time. Uma and Wein [38] point out that the value
of this LP solution coincides with one of the combinatorial bounds of Belouadah, Posner and
Potts based on the idea of allowing jobs to be split into smaller pieces that can be scheduled
individually.
We show that the optimal value of 1j r j j
is at most 1:6853 times the lower bound
given by any of these three equivalent relaxations | the preemptive time-indexed relaxation,
the completion time relaxation or the combinatorial relaxation in [4]. We prove this result on the
quality of these relaxations by converting the (preemptive) LP schedule into a non-preemptive
schedule. This technique leads to approximation algorithms for 1j r j j
Recall that a {
approximation algorithm is a polynomial-time algorithm guaranteed to deliver a solution of cost
at most  times the optimal value. A randomized {approximation algorithm is a polynomial-time
algorithm that produces a feasible solution whose expected objective function value is within
a factor of  of the optimal value.
The technique of converting preemptive schedules to non-preemptive schedules in the design
of approximation algorithms was introduced by Phillips, Stein and Wein [21]. More specically,
showed that list scheduling in order of the completion times of a given
preemptive schedule produces a non-preemptive schedule while increasing the total weighted
completion time by at most a factor of 2. In the same paper they also introduced a concept of
-points. This notion was also used by Hall, Shmoys and Wein [13], in connection with the non-preemptive
time-indexed relaxation of Dyer and Wolsey to design approximation algorithms in
various scheduling environments. For our purposes, the -point of job j in a given preemptive
schedule is the rst point in time at which an -fraction of j has been completed. When
one chooses dierent values of , sequencing in order of non-decreasing -points in the same
preemptive schedule may lead to dierent non-preemptive schedules. This increased
exibility
led to improved approximation algorithms: Chekuri, Motwani, Natarajan and Stein [6] for
Goemans [11] for 1j r chose  at random and analyzed the expected
performance of the resulting randomized algorithms. We will show that, using a common value
of  for all jobs and an appropriate probability distribution, sequencing in order of -points of
the LP schedule has expected performance no worse than 1:7451 times the optimal preemptive
time-indexed LP value. We also prove that by selecting a separate value  j for each job j,
one can improve this bound to a factor of 1:6853. Our algorithms are inspired by and partly
resemble the algorithms of Hall et al. [13] and Chekuri et al. [6]. In contrast to Hall et al.
Reference and/or O-line On-line
type of schedule deterministic randomized deterministic
Phillips et al. [21]
Hall et al. [13] 4 4
Schulz [26] 3
Hall et al. [14] 3 3
Chakrabarti et al. [5] 2:8854
Combining [5] and [14] 2:4427
-schedule
for

Table

1: Summary of approximation bounds for 1j r j
. An -schedule is obtained by sequencing
the jobs in order of non-decreasing -points of the LP schedule. The use of job-dependent  j
's yields an
)-schedule. The results discussed in this paper are below the second double line. Subsequently, Anderson
and Potts [2] gave a deterministic 2{competitive algorithm. For the unit-weight problem 1j r j
the rst constant-factor approximation algorithm is due to Phillips, Stein and Wein [21]. It has performance
ratio 2, and it also works on-line. Further deterministic 2{competitive algorithms were given by
Stougie [36] and Hoogeveen and Vestjens [15]. All these algorithms are optimal for deterministic on-line
algorithms [15]. Chekuri, Motwani, Natarajan and Stein [6] gave a randomized e=(e 1){approximation
algorithm, which is optimal for randomized on-line algorithms [37, 39].
we exploit the preemptive time-indexed LP relaxation, which, on the one hand, provides us
with highly structured optimal solutions and, on the other hand, enables us to work with mean
busy times. We also use random -points. The algorithm of Chekuri et al. starts from an
arbitrary preemptive schedule and makes use of random -points. They relate the value of the
resulting -schedule to that of the given preemptive schedule, and not to that of an underlying
LP relaxation. While their approach gives better approximations for 1j r
insights on limits of the power of preemption, the link of the LP schedule to the preemptive time-indexed
LP relaxation helps us to obtain good approximations for the total weighted completion
time.
Variants of our algorithms also work on-line when jobs arrive dynamically over time and, at
each point in time, one has to decide which job to process without knowledge of jobs that will be
released afterwards. Even in this on-line setting, we compare the value of the computed schedule
to the optimal (o-line) schedule and derive the same bounds (competitive ratios) as in the o-
line setting. See Table 1 for an account of the evolution of o-line and on-line approximation
results for the single machine problem under consideration.
The main ingredient to obtain the results presented in this paper is the exploitation of the
structure of the LP schedule. Not surprisingly, the LP schedule does not solve the strongly NP-hard
[16] preemptive version of the problem, 1j r
However, we show that the LP
schedule solves optimally the preemptive problem with the related objective function
where M j is the mean busy time of job j, i. e., the average point in time at which the machine
is busy processing j. Observe that, although 1j r are
equivalent optimization problems in the non-preemptive case (since C
are not
when considering preemptive schedules.
The approximation techniques presented in this paper have also proved useful for more
general scheduling problems. For the problem with precedence constraints 1j r
sequencing jobs in order of random -points based on an optimal solution to a time-indexed
relaxation leads to a 2:7183{approximation algorithm [27]. A 2{approximation algorithm
for identical parallel machine scheduling is given in [28]; the result is based on
a time-indexed LP relaxation an optimal solution of which can be interpreted as a preemptive
schedule on a fast single machine; jobs are then assigned randomly to the machines and sequenced
in order of random  j -points of this preemptive schedule. For the corresponding scheduling
problem on unrelated parallel machines R j r j j
performance guarantee of 2 can be
obtained by randomized rounding based on a convex quadratic programming relaxation [33],
which is inspired by time-indexed LP relaxations like the one discussed herein [28]. We refer to
[32] for a detailed discussion of the use of -points for machine scheduling problems.
Signicant progress has recently been made in understanding the approximability of scheduling
problems with the average weighted completion time objective. Skutella and Woeginger [34]
developed a polynomial-time approximation scheme for scheduling identical parallel machines
in the absence of release dates,
Subsequently, several research groups have found
polynomial-time approximation schemes for problems with release dates such as
and
see the resulting joint conference proceedings publication [1] for details.
We now brie
y discuss some practical consequences of our work. Savelsbergh, Uma and
Wein [25] and Uma and Wein [38] performed experimental studies to evaluate, in part, the
quality of the LP relaxation and approximation algorithms studied herein, for 1j r
and related scheduling problems. The rst authors report that, except for instances that were
deliberately constructed to be hard for this approach, the present formulation and algorithms
\deliver surprisingly strong experimental performance." They also note that \the ideas that led
to improved approximation algorithms also lead to heuristics that are quite eective in empirical
experiments; furthermore they can be extended to give improved heuristics for more
complex problems that arise in practice." While the authors of the follow-up study [38] report
that when coupled with local improvement the LP-based heuristics generally produce the
best solutions, they also nd that a simple heuristic often outperforms the LP-based heuristics.
Whenever the machine becomes idle, this heuristic starts non-preemptively processing an available
job of largest w j =p j ratio. By analyzing the dierences between the LP schedule and this
heuristic schedule, Chou, Queyranne and Simchi-Levi [7] have subsequently shown the asymptotic
optimality of this on-line heuristic for classes of instances with bounded job weights and
bounded processing times.
The contents of this paper are as follows. Section 2 is concerned with the LP relaxations and
their relationship. We begin with a presentation and discussion of the LP schedule. In Section 2.1
we then review a time-indexed formulation introduced by Dyer and Wolsey [9] and show that it is
solved to optimality by the LP schedule. In Section 2.2 we present the mean busy time relaxation
(or completion time relaxation) and prove, among other properties, its equivalence to the time-indexed
formulation. Section 2.3 explores some polyhedral consequences, in particular the fact
that the mean busy time relaxation is (up to scaling by the job processing times) a supermodular
linear program and that the \job-based" method for constructing the LP schedule is equivalent to
the corresponding greedy algorithm. Section 3 then deals with approximation algorithms derived
from these LP relaxations. In Section 3.1 we present a method for constructing ( j )-schedules,
which allows us to analyze and bound the job completion times in the resulting schedules. In
Section 3.2 we derive simple bounds for -schedules and ( j )-schedules, using a deterministic
common  or uniformly distributed random  j 's. Using appropriate probability distributions,
we improve the approximation bound to the value of 1.7451 for -schedules in Section 3.3 and to
the value of 1.6853 for ( j )-schedules in Section 3.4. We also indicate how these algorithms can
be derandomized in O(n 2 ) time for constructing deterministic schedules with these performance
guarantees. In Section 3.5 we show that our randomized approximations also apply in an on-line
setting and, in Section 3.6 we present a class of \bad" instances for which the ratio of the
optimal objective function value and our LP bound is arbitrarily close to e
1:5819. This
constant denes a lower bound on the approximation results that can be obtained by the present
approach. We conclude in Section 4 by discussing some related problems and open questions.
Relaxations
In this section, we present two linear programming relaxations for 1j r j j
We show their
equivalence and discuss some polyhedral consequences.
For both relaxations, the following preemptive schedule plays a crucial role: at any point in
time, schedule (preemptively) the available job with highest w j =p j ratio. We assume (throughout
the paper) that the jobs are indexed in order of non-increasing ratios w 1
wn
pn
and ties are broken according to this order. Therefore, whenever a job is released, the job
being processed (if any) is preempted if the released job has a smaller index. We refer to this
preemptive schedule as the LP schedule. See Figure 1 for an example of an LP schedule.011011011

Figure

1: An LP schedule for a 4-job instance given by r 1
r 4
5. Higher rectangles represent jobs with larger weight to processing time ratio. Time is
shown on the horizontal axis.
Notice that this LP schedule does not in general minimize
preemptive
schedules. This should not be surprising since the preemptive problem 1j r
(strongly) NP-hard [16]. It can be shown, however, that the total weighted completion time of
the LP schedule is always within a factor of 2 of the optimal value for 1j r
this bound is tight; see [29].
The LP schedule can be constructed in O(n log n) time. To see this, we now describe an
implementation, which may be seen as \dynamic" (event-oriented) or, using the terminology
of [19], \machine-based" and can even be executed on-line while the jobs dynamically arrive
over time. The algorithm keeps a priority queue [8] of the currently available jobs that have not
yet been completely processed, with the ratio w j =p j as the key and with another eld indicating
the remaining processing time. A scheduling decision is made at only two types of events: when
a job is released, and when a job completes its processing. In the former case, the released job is
added to the priority queue. In the latter case, the completed job is removed from the priority
queue. Then, in either case, the top element of the priority queue (the one with highest w
ratio) is processed; if the queue is empty, then move on to the next job release; if there is none,
then all jobs have been processed and the LP schedule is complete. This implementation results
in a total of O(n) priority queue operations. Since each such operation can be implemented in
O(log n) time [8], the algorithm runs in O(n log n) time.
The LP schedule can also be dened in a somewhat dierent manner, which may be seen as
\static" or \job-based" [19]. Consider the jobs one at a time in order of non-increasing w j =p j .
Schedule each job j as early as possible starting at r j and preempting it whenever the machine
is busy processing another job (that thus came earlier in the w j =p j ordering). This point-of-view
leads to an alternate O(n log n) construction of the LP schedule, see [10].
2.1 Time-Indexed Relaxation
Dyer and Wolsey [9] investigate several types of relaxations of 1j r j j
the strongest ones
being time-indexed. We consider the weaker of their two time-indexed formulations, which
they call formulation (D). It uses two types of variables: y being processed
during time interval [;  + 1), and zero otherwise; and t j represents the start time of job j. For
simplicity, we add p j to t j and replace the resulting expression by C j ; this gives an equivalent
relaxation.
subject to
(D)
where T is an upper bound on the makespan of an optimal schedule (for example,
We refer to this relaxation as the preemptive time-indexed relaxation.
The expression for C j given in (1) corresponds to the correct value of the completion time if
job j is not preempted; an interpretation in terms of mean busy times is given in the next section
for the case of preemptions. Observe that the number of variables of this formulation is pseudo-
polynomial. If we eliminate C j from the relaxation by using (1), we obtain a transportation
problem [9] and, as a result, y j can be assumed to be integral:
Lemma 2.1. There exists an optimal solution to (D) for which y j 2 f0; 1g for all j and  .
As indicated in [9], (D) can be solved in O(n log n) time. Actually, one can derive a feasible
solution to (D) from the LP schedule by letting y LP
j be equal to 1 if job j is being processed in
Theorem 2.2. The solution y LP derived from the LP schedule is an optimal solution to (D).
Proof. The proof is based on an interchange argument. Consider any optimal 0=1-solution y  to
(D). If there exist j < k and  >   r j such that y
replacing y
j and y
by 0, and y
j and y
k by 1, we obtain another feasible solution with an increase in the objective
function value of ( )
0. The resulting solution must therefore also be optimal.
By repeating this interchange argument, we derive that there exists an optimal solution y  such
that there do not exist j < k and  >   r j such that y
This implies that the
solution y  must correspond to the LP schedule.
In particular, despite the pseudo-polynomial number of variables in the LP relaxation (D)
an optimal solution can be obtained e-ciently. We will make use of this fact as well as of the
special structure of the LP schedule in the design and analysis of the approximation algorithms,
see Section 3. We note again that in spite of its nice properties the preemptive time-indexed
LP relaxation (D) solves neither 1j r . In the former case, the
processing of a job in the LP solution may fail to be consecutive; in the latter case equation (1)
does not necessarily dene the completion time of a job in the preemptive LP schedule, as will
be shown in the next lemma.
2.2 Mean Busy Time Relaxation
Given any preemptive schedule, let I j be the indicator function of the processing of job j at time t,
i. e., I j (t) is 1 if the machine is processing j at time t and 0 otherwise. To avoid pathological
situations, we require that, in any preemptive schedule, when the machine starts processing a
job, it does so for a positive amount of time. Given any preemptive schedule, we dene the
mean busy time M j of job j to be the average time at which the machine is processing j, i. e.,
I
For instance, in the example given in Figure 1, which will be used throughout this paper, the
mean busy time of job 4 is 5:5.
We rst establish some important properties of M j in the next two lemmas.
Lemma 2.3. For any preemptive schedule, let C j and M j denote the completion and mean busy
time, respectively, of job j. Then for any job j, we have
only if job j is not preempted.
Proof. If job j is processed without preemption, then I j
is not processed during some interval(s) of
total length L > 0 between times C
R T
I j (t) must be processed
during some time interval(s) of the same total length L before C j p j . Therefore,
I
and the proof is complete.
Let S  N denote a set of jobs and dene
Let I S (t) :=
j2S I j (t). Since, by the machine capacity constraint, I S (t) 2 f0; 1g for all t, we
may view I S as the indicator function for job set S. We can thus dene the mean busy time of
set S as M S := 1
R T
dt. Note that we have
I j (t)
So, unlike its start and completion time, the mean busy time of a job set is a simple weighted
average of the mean busy times of its elements. One consequence of this observation is the
validity of the shifted parallel inequalities (3) (see, e.g., [10, 23, 24]) below.
Lemma 2.4. For any set S of jobs and any preemptive schedule with mean busy time vector M ,
we have
and equality holds if and only if all the jobs in S are scheduled without interruption from r min (S)
to r min (S)
Proof. Note that
R T
r min (S) I S (t) t dt ; that I S
and I S (t)  1 for t  r min (S) ; and that
R T
r min (S) I S (t)
is minimized when I S
M S is uniquely minimized among all feasible preemptive schedules when all the jobs in S are
continuously processed from r min (S) to r min (S) + p(S). This minimum value is p(S)(r min (S) +2
p(S)) and is a lower bound for
in any feasible preemptive schedule.
As a result of Lemma 2.4, the following linear program provides a lower bound on the optimal
value of 1j r
and hence on that of 1j r j j
subject to
(R)
The proof of the following theorem and later developments use the notion of canonical
decompositions [10]. For a set S of jobs, consider the schedule which processes jobs in S as
early as possible, say, in order of their release dates. This schedule induces a partition of S
into such that the machine is busy processing jobs in S exactly in the disjoint
We refer to this partition as the canonical
decomposition of S. A set is canonical if it is identical to its canonical decomposition, i. e., if its
canonical decomposition is fSg. Thus a set S is canonical if and only if it is feasible to schedule
all its jobs in the time interval [r min (S); r min (S)+p(S)). Note that the set our
example is canonical whereas the subset f1; 2; 3g is not; it has the decomposition ff3g; f1; 2gg.
Let
is the canonical decomposition of S  N . Then Lemma 2.4 implies that
is a valid inequality for the mean busy time vector of
any preemptive schedule. In other words, relaxation (R) may be written as:
min
Theorem 2.5. Let M LP
j be the mean busy time of job j in the LP schedule. Then M LP is an
optimal solution to (R).
Proof. By Lemma 2.4, M LP is a feasible solution for (R).
To prove optimality of M LP , we construct a lower bound on the optimal value of (R) and
show that it is equal to the objective function value of M LP . Recall that the jobs are indexed
in non-increasing order of the w
k(i) denote
the canonical decomposition of [i]. Observe that for any vector
where we let w n+1 =p n+1 := 0. We have therefore expressed
as a nonnegative
combination of expressions
sets. By construction of the LP schedule,
the jobs in any of these canonical sets S i
are continuously processed from r min (S i
' ) to r min (S i
) in the LP schedule. Thus, for any feasible solution M to (R) and any such canonical set
' we have
r min (S i
where the last equation follows from Lemma 2.4. Combining this with (5), we derive a lower
bound on
feasible solution M to (R), and this lower bound is attained by the
LP schedule.
>From Theorems 2.2 and 2.5, we derive that the values of the two relaxations (D) and (R)
are equal.
Corollary 2.6. The LP relaxations (D) and (R) of
yield the same optimal objective
function value, i. e., weights w  0. This value can be computed in
O(n log n) time.
Proof. For the equivalence of the lower bounds, note that the mean busy time M LP
j of any job j
in the LP schedule can be expressed as
y LP
where y LP is the solution to (D) derived from the LP schedule. The result then follows directly
from Theorems 2.2 and 2.5. We have shown earlier that the LP schedule can be constructed in
O(n log n) time.
Although the LP schedule does not necessarily minimize
over the preemptive sched-
ules, Theorem 2.5 implies that it minimizes
over the preemptive schedules. In addition,
by Lemma 2.3, the LP schedule is also optimal for both preemptive and non-preemptive problems
it does not preempt any job. For example,
this is the case if all processing times are equal to 1 or if all jobs are released at the same date.
Thus, the LP schedule provides an optimal solution to problems 1j r
and to
This was already known. In the latter case it coincides with Smith's ratio rule [35];
see Queyranne and Schulz [24] for the former case.
2.3 Polyhedral Consequences
We now consider some polyhedral consequences of the preceding results. Let P 1
D be the feasible
region dened by the constraints of relaxation (D) when

In addition, we denote by PR := fM 2 R
the polyhedron
dened by the constraints of relaxation (R).
Theorem 2.7.
(i) Polyhedron PR is the convex hull of the mean busy time vectors M of all preemptive sched-
ules. Moreover, every vertex of PR is the mean busy time vector of an LP schedule.
(ii) Polyhedron PR is also the image of P 1
D in the space of the M-variables under the linear
mapping dened by
for all j 2 N:
Proof. (i) Lemma 2.4 implies that the convex hull of the mean busy time vectors M of all feasible
preemptive schedules is contained in PR . To show the reverse inclusion, it su-ces to show that
(a) every extreme point of PR corresponds to a preemptive schedule; and (b) every extreme ray
of PR is a direction of recession for the convex hull of mean busy time vectors. Property (a) and
the second part of statement (i) follow from Theorem 2.5 and the fact that every extreme point
of PR is the unique minimizer of
note that the extreme
rays of PR are the n unit vectors of R N . An immediate extension to preemptive schedules and
mean busy times of results in Balas [3] implies that these unit vectors of R N are directions of
recession for the convex hull of mean busy time vectors. This completes the proof of (i).
(ii) We rst show that the image M(P 1
D is contained in PR . For this, let y be a
vector in P 1
D and S  N with canonical decomposition g. By denition of M(y) j ,
we have
r min (S '
The inequality follows from the constraints dening P 1
and the interchange argument which
we already used in the proof of Theorem 2.2. This shows M(y) 2 PR and thus M(P 1
To show the reverse inclusion, we use the observation from the proof of part (i) that PR can
be represented as the sum of the convex hull of the mean busy time vectors of all LP schedules
and the nonnegative orthant. Since, by equation (6), the mean busy time vector M LP of any LP
schedule is the projection of the corresponding 0=1-vector y LP , it remains to show that every
unit vector e j is a direction of recession for M(P 1
D ). For this, x an LP schedule and let y LP and
denote the associated 0=1 y-vector and mean busy time vector, respectively.
For any job j 2 N and any real  > 0, we need to show that M LP
Let  max := argmaxfy LP
Ng. Choose  such that y LP
choose an integer
k otherwise. In the
associated preemptive schedule, the processing of job j that was done in interval [;  +1) is now
postponed, by  time units, until interval [ +;  ++1). Therefore, its mean busy time vector
k for all k 6= j. Let  0 := =p j  , so
. Then the vector M LP +  e j is a convex combination of M
and y be the corresponding convex combination of y LP and y 0 . Since P 1
D is
convex then y
D and, since the mapping M is linear, M LP
In view of earlier results for single machine scheduling with identical release dates [22], as
well as for parallel machine scheduling with unit processing times and integer release dates [24],
it is interesting to note that the feasible set PR of the mean busy time relaxation is, up to scaling
by the job processing times, a supermodular polyhedron:
Proposition 2.8. The set function h dened in (4) is supermodular.
Proof. Consider any two elements any subset S  N n fj; kg. We may construct
an LP schedule minimizing
using the job-based method by considering rst the
jobs in S and then job k. (Note that considering the jobs in any sequence leads to a schedule
minimizing
because jobs are weighted by their processing times in this objective
function). By denition (4) the resulting mean busy times M LP satisfy
and
Note that job k is scheduled, no earlier than its release
date, in the rst p k units of idle time left after the insertion of all jobs in S. Thus M LP
k is the
mean of all these p k time units. Similarly, we may construct an LP schedule, whose mean busy
time vector will be denoted by f
considering rst the jobs
in S, so f
f
job k, so
f
has been inserted after subset S was
scheduled, job k cannot use any idle time interval that is earlier than those it used in the former
schedule M LP |and some of the previously available idle time may now be occupied by job
j, causing a delay in the mean busy time of job k; thus we have f
k and therefore
f
This su-ces to establish that h is supermodular.
An alternate proof of the supermodularity of h can be derived, as in [10], from the fact, observed
by Dyer and Wolsey and already mentioned above, that relaxation (D) becomes a transportation
problem after elimination of the C j 's. Indeed, from an interpretation of Nemhauser,
Wolsey and Fisher [20] of a result of Shapley [31], it then follows that the value of this transportation
problem as a function of S is supermodular. One of the consequences of Proposition 2.8
is that the job-based method to construct an LP schedule is just a manifestation of the greedy
algorithm for minimizing
over the supermodular polyhedron PR .
We nally note that the separation problem for the polyhedron PR can be solved combina-
torially. One can separate over the family of inequalities
by trying all possible values for r min (S) (of which there are at most n) and then applying a
O(n log n) separation routine of Queyranne [22] for the problem without release dates. The
overall separation routine can be implemented in O(n 2 ) time by observing that the bottleneck
step in Queyranne's algorithm | sorting the mean busy times of the jobs | needs to be done
only once for the whole job set.
Provably Good Schedules and LP Relaxations
In this section, we derive approximation algorithms for 1j r j j
that are based on converting
the preemptive LP schedule into a feasible non-preemptive schedule whose value can
be bounded in terms of the optimal LP value This yields results on the quality of
both the computed schedule and the LP relaxations under consideration since the value of the
computed schedule is an upper bound and the optimal LP value is a lower bound on the value
of an optimal schedule.
In Section 3.6 below, we describe a family of instances for which the ratio between the
optimal value of the 1j r problem and the lower bounds ZR and ZD is arbitrarily
close to e
1:5819. This lower bound of e
e 1 sets a target for the design of approximation
algorithms based on these LP relaxations.
In order to convert the preemptive LP schedule into a non-preemptive schedule we make
use of so-called -points of jobs. For 0 <   1 the -point t j () of job j is the rst point in
time when an -fraction of job j has been completed in the LP schedule, i. e., when j has been
processed for  p j time units. In particular, t j (1) is equal to the completion time and we dene
to be the start time of job j. Notice that, by denition, the mean busy time M LP
j of
job j in the LP schedule is the average over all its -points
We will also use the following notation: For a xed job j and 0 <   1 we denote the fraction
of job k that is completed in the LP schedule by time t j () by  k (); in particular,  j
The amount of idle time that occurs between time 0 and the start of job j in the LP schedule is
denoted by  idle . Note that  k and  idle implicitly depend on the xed job j. By construction,
there is no idle time between the start and completion of job j in the LP schedule; therefore we
can express j's -point as
For a given 0 <   1, we dene the -schedule as the schedule in which jobs are processed
non-preemptively as early as possible and in the order of non-decreasing -points. We denote
the completion time of job j in this schedule by C
. The idea of scheduling non-preemptively
in the order of -points in a preemptive schedule was introduced by Phillips, Stein and Wein
[21], and used in many of the subsequent results in the area.
This idea can be further extended to individual, i. e., job-dependent  j -points t
1. We denote the vector consisting of all  j 's by    :=
Then, the ( j )-schedule is constructed by processing the jobs as early as possible and in non-decreasing
order of their  j -points; the completion time of job j in the ( j )-schedule is denoted
by C
.

Figure

compares an -schedule to an ( j )-schedule both derived from the LP schedule
in

Figure

1.
In the sequel we present several results on the quality of -schedules and ( j )-schedules.
These results also imply bounds on the quality of the LP relaxations of the previous section.
The main result is the construction of a random ( j )-schedule whose expected value is at most
a factor 1:6853 of the optimal LP value Therefore the LP relaxations (D) and
(R) deliver a lower bound which is at least 0:5933 ( 1:6853 1 ) times the optimal value. The
corresponding randomized algorithm can be implemented on-line; it has competitive ratio 1:6853
and running time O(n log n); it can also be derandomized to run o-line in O(n 2 ) time. We also
investigate the case of a single common  and show that the best -schedule is always within a
factor of 1:7451 of the optimum.

Figure

2: A non-preemptive -schedule (for and an ( j
)-schedule shown above and below the
LP schedule, respectively. Notice that there is no common  value that would lead to the latter schedule.
3.1 Bounding the completion times in ( j )-schedules
To analyze the completion times of jobs in ( j )-schedules, we consider non-preemptive schedules
of similar structure that are, however, constructed by a slightly dierent conversion routine which
we call ( j )-Conversion:
Consider the jobs j 2 N in order of non-increasing  j -points t iteratively
change the preemptive LP schedule to a non-preemptive schedule by applying the
following steps:
i) remove the  j p j units of job j that are processed before t j leave the
machine idle during the corresponding time intervals; we say that this idle time
is caused by job j;
ii) delay the whole processing that is done later than t
iii) remove the remaining (1  j )-fraction of job j from the machine and shrink
the corresponding time intervals; shrinking a time interval means to discard the
interval and move earlier, by the corresponding amount, any processing that
occurs later;
iv) process job j in the released time interval

Figure

3 contains an example illustrating the action of ( j )-Conversion starting from the LP
schedule of Figure 1. Observe that in the resulting schedule jobs are processed in non-decreasing
order of  j -points and no job j is started before time t . The latter property will be
useful in the analysis of on-line ( j )-schedules.
Figure

3: Illustration of the individual iterations of ( j
)-Conversion.
Lemma 3.1. The completion time of job j in the schedule constructed by
equal to
Proof. Consider the schedule constructed by )-Conversion. The completion time of job j
is equal to the idle time before its start plus the sum of processing times of jobs that start no
later than j. Since the jobs are processed in non-decreasing order of their  j -points, the amount
of processing before the completion of job j is
The idle time before the start of job j can be written as the sum of the idle time  idle that
already existed in the LP schedule before j's start plus the idle time before the start of job j
that is caused in steps i) of ( j )-Conversion; notice that steps iii) do not create any additional
idle time since we shrink the aected time intervals. Each job k that is started no later than j,
i. e., such that  k units of idle time, all other jobs k only contribute
units of idle time. As a result, the total idle time before the start of job j can be
written as
The completion time of job j in the schedule constructed by is equal to the
sum of the expressions in (9) and (10); the result then follows from equation (8).
It follows from Lemma 3.1 that the completion time C j of each job j in the non-preemptive
schedule constructed by hence is a feasible
schedule. Since the ( j )-schedule processes the jobs as early as possible and in the same order
as the ( j )-Conversion schedule, we obtain the following corollary.
Corollary 3.2. The completion time of job j in an ( j )-schedule can be bounded by
3.2 Bounds for -schedules and ( j )-schedules
We start with a result on the quality of the -schedule for a xed common value of .
Theorem 3.3. For xed , (i) the value of the -schedule is within a factor max

of the optimal LP value; in particular, for
2 the bound is 1
2. Simultaneously, (ii)
the length of the -schedule is within a factor of 1 +  of the optimal makespan.
Proof. While the proof of (ii) is an immediate consequence of (8) and Corollary 3.2, it follows
from the proof of Theorem 2.5 that for (i) it is su-cient to prove that, for any canonical set S,
we have
Indeed, using (5) and Lemma 2.4 it would then follow that
proving the result.
Consider now any canonical set S and let us assume that, after renumbering the jobs,
the ordering is not necessarily anymore in
non-increasing order of w j =p j ). Fix now any job j 2 S. From Corollary 3.2, we derive that
where  k :=  k () represents the fraction of job k processed in the LP schedule before t j ().
Let R denote the set of jobs k such that t k () < r min (S) (and thus    k ). Since S is a
canonical set, the jobs in S are processed continuously in the LP schedule between r min (S) and
therefore every job k with    k is either in S or in R. Observe that
implies that p(R)  1
r min (S). We can thus simplify (12)
Since the jobs in S are scheduled with no gaps in [r min (S); r min (S) + p(S)], we have that
Combining (13) and (14), we derive that
Multiplying by p j and summing over S, we get:
which implies (11).
In the sequel we will compare the completion time C
j of every job j with its \completion time"
in the LP schedule. However, for any xed common value of , there exist instances
which show that this type of job-by-job analysis can give a bound no better than 1+
One can also show that, for any given value of , there exist instances for which the objective
function value of the -schedule can be as bad as twice the LP lower bound.
In view of these results, it is advantageous to use several values of  as it appears that no
instance can be simultaneously bad for all choices of . In fact, the -points develop their full
power in combination with randomization, i. e., when a common  or even job-dependent  j 's are
chosen randomly from (0; 1] according to an appropriate density function. This is also motivated
by equation (7) which relates the expected -point of a job under a uniform distribution of
to the LP variable M LP
. For random values  j , we analyze the expected value of the resulting
)-schedule and compare it to the optimal LP value. Notice that a bound on the expected
value proves the existence of a vector ( j ) such that the corresponding ( j )-schedule meets this
bound. Moreover, for our results we can always compute such an ( j ) in polynomial time by
derandomizing our algorithms with standard methods; see Propositions 3.8 and 3.13.
Although the currently best known bounds can only be achieved for ( j )-schedules with
job-dependent  j 's, we investigate -schedules with a single common  as well. On the one
hand, this helps to better understand the potential advantages of ( j )-schedules; on the other
hand, the randomized algorithm that relies on a single  admits a natural derandomization. In
fact, we can easily compute an -schedule of least objective function value over all  between
0 and 1; we refer to this schedule as the best-schedule. In Proposition 3.8 below, we will
show that there are at most n dierent -schedules. The best-schedule can be constructed
in O(n 2 ) time by evaluating all these dierent schedules.
As a warm-up exercise for the kind of analysis we use, we start by proving a bound of 2 on
the expected worst-case performance ratio of uniformly generated ( j )-schedules in the following
theorem. This result will then be improved by using more intricate probability distributions and
by taking advantage of additional insights into the structure of the LP schedule.
Theorem 3.4. Let the random variables  j be pairwise independently and uniformly drawn
from (0; 1]. Then, the expected value of the resulting ( j )-schedule is within a factor 2 of the
optimal LP value
Proof. Remember that the optimal LP value is given by
To get the claimed
result, we prove that EU [C
denotes the
expectation of a function F of the random variable    when the latter is uniformly distributed.
The overall performance follows from this job-by-job bound by linearity of expectations.
Consider an arbitrary, but xed job j 2 N . To analyze the expected completion time of j,
we rst keep  j xed, and consider the conditional expectation EU [C
the random
variables  j and  k are independent for each k 6= j, Corollary 3.2 and equation (8) yield
EU [C
To obtain the unconditional expectation EU [C
we integrate over all possible choices of
EU [C
Z 1EU [C
the last equation follows from (7).
We turn now to deriving improved results. We start with an analysis of the structure of
the LP schedule. Consider any job j, and assume that, in the LP schedule, j is preempted at
time s and its processing resumes at time t > s. Then all the jobs which are processed between
s and t have a smaller index; as a result, these jobs will be completely processed between times
s and t. Thus, in the LP schedule, between the start time and the completion time of any job j,
the machine is constantly busy, alternating between the processing of portions of j and the
complete processing of groups of jobs with smaller index. Conversely, any job preempted at the
will have to wait at least until job j is complete before its processing
can be resumed.
We capture this structure by partitioning, for a xed job j, the set of jobs N n fjg into two
subsets N 1 and denote the set of all jobs that are processed between the start and
completion of job j. All remaining jobs are put into subset N 1 . Notice that the function  k is
constant for jobs k 2 N 1 ; to simplify notation we write  k :=  k ( j ) for those jobs. For k 2 N 2 ,
the fraction of job j that is processed before the start of job k; the
function  k is then given by
We can now rewrite equation (8) as
Plugging (15) into equation (7) yields
and Corollary 3.2 can be rewritten as
where, for k 2 N 2 , we have used the fact that  k   k ( j ) is equivalent to  j >  k . The
expressions (15), (16), and (17) re
ect the structural insights that we need for proving stronger
bounds for ( j )-schedules and -schedules in the sequel.
As mentioned above, the second ingredient for an improvement on the bound of 2 is a more
sophisticated probability distribution of the random variables  j . In view of the bound on C
given in (17), we have to cope with two contrary phenomena: On the one hand, small values of
k keep the terms of the form (1 on the right-hand side of (17) small;
on the other hand, choosing larger values decreases the number of terms in the rst sum on the
right-hand side of (17). The balancing of these two eects contributes to reducing the bound
on the expected value of C
.
3.3 Improved bounds for -schedules
In this subsection we prove the following theorem.
Theorem 3.5. Let
0:4675 be the unique solution to the equation
satisfying 0 <
< 1. Dene c := 1+
e
< 1:7451 and - := 1 1+
0:8511. If  is chosen
according to the density function
then the expected value of the resulting random -schedule is bounded by c times the optimal LP
value
Before we prove Theorem 3.5 we state two properties of the density function f that are
crucial for the analysis of the corresponding random -schedule.
Lemma 3.6. The function f given in Theorem 3.5 is a density function with the following
properties:
Property (i) is used to bound the delay to job j caused by jobs in N 1 which corresponds to
the rst summation on the right-hand side of (17). The second summation re
ects the delay to
caused by jobs in N 2 and will be bounded by property (ii).
Proof of Lemma 3.6. A short computation shows that
. The function f is a density
function since
Z -e
In order to prove property (i), observe that for  2 [0; -]
For  2 (-; 1] we therefore get
Property (ii) holds for  2 (-; 1] since the left-hand side is 0 in this case. For  2 [0; -] we have
e
This completes the proof of the lemma.
Proof of Theorem 3.5. In Lemma 3.6, both (i) for
denotes the expected value of a random variable  that is distributed according to
the density f given in Theorem 3.5. Thus, using inequality (17) and Lemma 3.6 we derive that
C
the last inequality follows from the denition of N 1 and  k and the last equality follows from (16).
Notice that any density function satisfying properties (i) and (ii) of Lemma 3.6 for some
value c 0 directly leads to the job-by-job bound E f [C
for the corresponding
random -schedule. It is easy to see that the unit function satises Lemma 3.6 with c
which establishes the following variant of Theorem 3.4.
Corollary 3.7. Let the random variable  be uniformly drawn from (0; 1]. Then, the expected
value of the resulting -schedule is within a factor 2 of the optimal LP value
The use of an exponential density function is motivated by the rst property in Lemma 3.6;
notice that the function  7! (c 1)e  satises it with equality. On the other hand, the exponential
function is truncated in order to reduce the term
in the second property.
In fact, the truncated exponential function f in Theorem 3.5 can be shown to minimize c 0 ; it
is therefore optimal for our analysis. In addition, there exists a class of instances for which the
ratio of the expected cost of an -schedule, determined using this density function, to the cost
of the optimal LP value is arbitrarily close to 1:745; this shows that the preceding analysis is
essentially tight in conjunction with truncated exponential functions.
Theorem 3.5 implies that the best-schedule has a value of at most 1:7451 ZR . The following
proposition shows that the randomized algorithm that yields the -schedule can be easily
derandomized because the sample space is small.
Proposition 3.8. There are at most n dierent -schedules; they can be computed in O(n 2 )
time.
Proof. As  goes from 0 + to 1, the -schedule changes only whenever an -point, say for
reaches a time at which job j is preempted. Thus, the total number of changes in the -schedule
is bounded from above by the total number of preemptions. Since a preemption can occur in the
LP schedule only whenever a job is released, the total number of preemptions is at most n 1,
and the number of -schedules is at most n. Since each of these -schedules can be computed
in O(n) time, the result on the running time follows.
3.4 Improved bounds for ( j )-schedules
In this subsection, we prove the following theorem.
Theorem 3.9. Let
0:4835 be the unique solution to the equation
)e
satisfying 0 <
< 1. Dene - :=
=- < 1:6853. Let the
's be chosen pairwise independently from a probability distribution over (0; 1] with the density
function
Then, the expected value of the resulting random ( j )-schedule is bounded by c times the optimal
LP value
The bound in Theorem 3.9 yields also a bound on the quality of the LP relaxations:
Corollary 3.10. The LP relaxations (D) and (R) deliver in O(n log n) time a lower bound
which is at least 0:5933 ( 1:6853 1 ) times the objective function value of an optimal schedule.
Following the lines of the last subsection, we state two properties of the density function g
that are crucial for the analysis of the corresponding random ( j )-schedule.
Lemma 3.11. The function g given in Theorem 3.9 is a density function with the following
properties:
denotes the expected value of a random variable  that is distributed according to g.
Notice the similarity of Lemma 3.11 and Lemma 3.6 of the last subsection. Again, properties
(i) and (ii) are used to bound the delay to job j caused by jobs in N 1 and N 2 , respectively,
in the right-hand side of inequality (17). Property (i) for
yield E g []  c 1.
Proof of Lemma 3.11. A short computation shows that
. It thus follows from the
same arguments as in the proof of Lemma 3.6 that g is a density function and that property (i)
holds. In order to prove property (ii), we rst compute
Z -e
Property (ii) certainly holds for  2 (-; 1]. For  2 [0; -] we get
e
)e
e
e
This completes the proof of the lemma.
Proof of Theorem 3.9. Our analysis of the expected completion time of job j in the random
)-schedule follows the line of argument developed in the proof of Theorem 3.4. First we
consider a xed choice of  j and bound the corresponding conditional expectation E g [C
In a second step we bound the unconditional expectation E g [C
by integrating the product
over the interval (0; 1].
For a xed job j and a xed value  j , the bound in (17) and Lemma 3.11 (i) yield
The last inequality follows from (15) and . Using property (ii) and
equation (16) yields
The result follows from linearity of expectations.
While the total number of possible orderings of jobs is log n) , we show in the
following lemma that the maximum number of ( j )-schedules is at most 2 n 1 . We will use the
following observation. Let q j denote the number of dierent pieces of job j in the LP schedule;
thus q j represents the number of times job j is preempted plus 1. Since there are at most n 1
preemptions, we have that
Lemma 3.12. The maximum number of ( j )-schedules is at most 2 n 1 and this bound can be
attained.
Proof. The number of ( j )-schedules is given by
. Note that q
is not preempted in the LP schedule. Thus,
1). By the
mean inequality, we have that
Y
Furthermore, this bound is attained if q and this is achieved for example
for the instance with
Therefore, and in contrast to the case of random -schedules, we cannot aord to derandomize
the randomized 1:6853{approximation algorithm by enumerating all ( j )-schedules. We
instead use the method of conditional probabilities [18].
>From inequality (17) we obtain for every vector   an upper bound on the objective
function value of the corresponding ( j )-schedule,
denotes the right-hand side of inequality (17). Taking expectations
and using Theorem 3.9, we have already shown that
where c < 1:6853. For each job j 2 N let
g denote the set of the intervals
for  j corresponding to the q j pieces of job j in the LP schedule. We consider the jobs one by
one in arbitrary order, say, Assume that, at step j of the derandomized algorithm,
we have identied intervals Q d
Using conditional expectations, the left-hand side of this inequality is
Since
there exists at least one interval Q j' 2 Q j such that
Therefore, it su-ces to identify such an interval Q d
satisfying (18) and we may conclude
that
Having determined in this way an interval Q d
j for every job note that the
)-schedule is the same for all    2 Q d Q d     Q d
n . The (now deterministic) objective
function value of this ( j )-schedule is
as desired. For every checking whether an interval Q d
amounts to evaluating O(n) terms, each of which may be computed in constant time. Since, as
observed just before Lemma 3.12, we have a total of
follows that the derandomized algorithm runs in O(n 2 ) time.
Proposition 3.13. The randomized 1:6853{approximation algorithm can be derandomized; the
resulting deterministic algorithm runs in O(n 2 ) time and has performance guarantee 1:6853 as
well.
Constructing provably good schedules on-line
In this subsection we show that our randomized approximation results also apply in an on-line
setting. There are several dierent on-line paradigms that have been studied in the area
of scheduling; we refer to [30] 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.
It has already been shown in Section 2 that the LP schedule can be constructed on-line.
Unfortunately, for a given vector ( j ), the corresponding ( j )-schedule cannot be constructed
on-line. We only learn about the position of a job k in the sequence dened by non-decreasing
-points at time t k ( k ); therefore we cannot start job k at an earlier point in time in the on-line
setting. On the other hand, however, the start time of k in the ( j )-schedule can be earlier than
its  k -point t k ( k ).
Although an ( j )-schedule cannot be constructed on-line, the above discussion reveals that
the following variant, which we call on-line-( j )-schedule, can be constructed on-line: For a
given vector ( j ), process the jobs as early as possible in the order of their  j -points, with the
additional constraint that no job k may start before time t k ( k ). See Figure 4 for an example.
We note that this idea of delaying the start of jobs until su-cient information for a good decision
is available was in this setting introduced by Phillips, Stein and Wein [21].
Notice that the non-preemptive schedule constructed by
straints; its value is therefore an upper bound on the value of the on-line-( j )-schedule. Our
analysis in the last subsections relies on the bound given in Corollary 3.2 which also holds for
the schedule constructed by 3.1. This yields the following results.
Theorem 3.14. For any instance of the scheduling problem 1j r j j
a) choosing
2 and constructing the on-line-schedule yields a deterministic on-line
algorithm with competitive ratio 1
2:4143 and running time O(n log n);
b) choosing the  j 's randomly and pairwise independently from (0; 1] according to the density
function g of Theorem 3.9 and constructing the on-line-( j )-schedule yields a randomized
on-line algorithm with competitive ratio 1:6853 and running time O(n log n).
The competitive ratio 1:6853 in Theorem 3.14 beats the deterministic on-line lower bound 2
for the unit-weight problem 1j r 36]. For the same problem, Stougie and Vestjens
proved the lower bound e
randomized on-line algorithms [37, 39].
Figure

4: The on-line schedule for the previously considered instance and  j
-points. The LP schedule
is shown above for comparison.
3.6 Bad instances for the LP relaxations
In this subsection, we describe a family of instances for which the ratio between the optimal
value of the 1j r j j
problem and the lower bounds ZR and ZD is arbitrarily close to
e
These instances I n have n  2 jobs as follows: one large job, denoted job n, and
small jobs denoted 1. The large job has processing time
and release date r Each of the n 1 small jobs j has zero processing time, weight
release date r
Throughout the paper, we have assumed that processing times are non-zero. In order to
satisfy this assumption, we could impose a processing time of 1=k for all small jobs, multiply
all processing times and release dates by k to make the data integral, and then let k tend to
innity. For simplicity, however, we just let the processing time of all small jobs be 0.
The LP solution has job n start at time 0, preempted by each of the small jobs; hence its
mean busy times are: M LP
Its objective function value
is
Notice that the completion time of each job j is in fact equal
to M LP
such that the actual value of the preemptive schedule is equal to ZR .
Now consider an optimal non-preemptive schedule C  and let
c n  0, so k is the
number of small jobs that can be processed before job n. It is then optimal to process all these
small jobs at their release dates, and to start processing job n at date r just after
job k. It is also optimal to process all remaining jobs k just after
job n. Let C k denote the resulting schedule, that is, C k
otherwise. Its objective function value is
n(n 1) . Therefore the optimal
schedule is C n 1 with objective function value
. As n grows large, the LP
objective function value approaches e 1 while the optimal non-preemptive cost approaches e.
Even though polynomial-time approximation schemes have now been discovered for the problem
[1], the algorithms we have developed, or variants of them, are likely to be superior
in practice. The experimental studies of Savelsbergh et al. [25] and Uma and Wein [38] indicate
that LP-based relaxations and scheduling in order of  j -points are powerful tools for a variety
of scheduling problems.
Several intriguing questions remain open. Regarding the quality of linear programming
relaxations, it would be interesting to close the gap between the upper (1:6853) and lower
(1:5819) bound on the quality of the relaxations considered in this paper. We should point out
that the situation for the strongly NP-hard [16] problem 1j r is similar. It is
shown in [29] that the completion time relaxation is in the worst case at least a factor of 8=7 and
at most a factor of 4=3 o the optimum; the latter bound is achieved by scheduling preemptively
by LP-based random -points. Chekuri et al. [6] prove that the optimal non-preemptive value
is at most e=(e 1) times the optimal preemptive value; our example in Section 3.6 shows that
this bound is tight.
Dyer and Wolsey [9] propose also a (non-preemptive) time-indexed relaxation which is
stronger than the preemptive version studied here. This relaxation involves variables for each job
and each time representing whether this job is being completed (rather than simply processed)
at that time. This relaxation is at least as strong as the preemptive version, but its worst-case
ratio is not known to be strictly better.
For randomized on-line algorithms, there is also a gap between the known upper and lower
bound on the competitive ratios that are given at the end of Section 3.5. For deterministic
on-line algorithms, the 2{competitve algorithm of Anderson and Potts [2] is optimal.

Acknowledgements

The research of the rst author was performed partly when the author was at C.O.R.E., Louvain-
la-Neuve, Belgium and supported in part by NSF contract 9623859-CCR. The research of the
second author was supported in part by a research grant from NSERC (the Natural Sciences
and Research Council of Canada) and by the UNI.TU.RIM. S.p.a. (Societa per l'Universita
nel riminese), whose support is gratefully acknowledged. The research of the third author was
performed partly when he was with the Department of Mathematics, Technische Universitat
Berlin, Germany. The fourth author was supported in part by DONET within the frame of
the TMR Programme (contract number ERB FMRX-CT98-0202) while staying at C.O.R.E.,
Louvain-la-Neuve, Belgium, for the academic year 1998/99. The fth author was supported by
a research fellowship from Max-Planck Institute for Computer Science, Saarbrucken, Germany.
We are also grateful to an anonymous referee whose comments helped to improve the presentation
of this paper.



--R








Introduction to Algorithms



Rinnooy Kan



Rinnooy Kan
Rinnooy Kan and P.
Randomized Algorithms


", Mathematical Programming, 82, 199-223 (1998). An extended abstract appeared under the title \Scheduling jobs that arrive over time"






" in R. Burkard and







cited as personal communication in



--TR

--CTR
Jairo R. Montoya-Torres, Competitive Analysis of a Better On-line Algorithm to Minimize Total Completion Time on a Single-machine, Journal of Global Optimization, v.27 n.1, p.97-103, September
Leah Epstein , Rob van Stee, Lower bounds for on-line single-machine scheduling, Theoretical Computer Science, v.299 n.1-3, p.439-450,
R. N. Uma , Joel Wein , David P. Williamson, On the relationship between combinatorial and LP-based lower bounds for NP-hard scheduling problems, Theoretical Computer Science, v.361 n.2, p.241-256, 1 September 2006
Martin W. P. Savelsbergh , R. N. Uma , Joel Wein, An Experimental Study of LP-Based Approximation Algorithms for Scheduling Problems, INFORMS Journal on Computing, v.17 n.1, p.123-136, Winter 2005
Martin Skutella, Convex quadratic and semidefinite programming relaxations in scheduling, Journal of the ACM (JACM), v.48 n.2, p.206-242, March 2001
F. Afrati , I. Milis, Designing PTASs for MIN-SUM scheduling problems, Discrete Applied Mathematics, v.154 n.4, p.622-639, 15 March 2006
Rolf H. Mhring , Andreas S. Schulz , Frederik Stork , Marc Uetz, Solving Project Scheduling Problems by Minimum Cut Computations, Management Science, v.49 n.3, p.330-350, March
on-line algorithm;LP relaxation;approximation algorithm;scheduling