Scheduling to Minimize Total Weighted Completion Time via
Time-Indexed Linear Programming Relaxations

arXiv:1707.08039v1 [] 25 Jul 2017

Shi Li

∗

Abstract
We study approximation algorithms for scheduling problems with the objective of minimizing
total weighted completion time, under identical and related machine models with job precedence
constraints. We give algorithms that improve upon many previous 15 to 20-year-old state-ofart results. A major theme in these results is the use of time-indexed linear programming
relaxations. These are natural relaxations for their respective problems, but surprisingly are
not studied in the literature.
We also consider the scheduling problem of minimizing total weighted completion time on
unrelated machines. The recent breakthrough result of [Bansal-Srinivasan-Svensson, STOC
2016] gave a (1.5 − c)-approximation for the problem, based on some lift-and-project SDP
relaxation. Our main result is that a (1.5 − c)-approximation can also be achieved using a
natural and considerably simpler time-indexed LP relaxation for the problem. We hope this
relaxation can provide new insights into the problem.

1

Introduction

Scheduling jobs to minimize total weighted completion time is a well-studied topic in scheduling
theory, operations research and approximation algorithms. A systematic study of this objective
under many different machine models (e.g, identical, related and unrelated machine models, job
shop scheduling, precedence constraints, preemptions) was started in late 1990s and since then it
has led to great progress on many fundamental scheduling problems.
In spite of these impressive results, the approximability of many problems is still poorly understood. Many of the state-of-art results that were developed in late 1990s or early 2000s have not
been improved since then. Continuing the recent surge of interest on the total weighted completion
time objective [4, 19, 37], we give improved approximation algorithms for many scheduling problems under this objective. The machine models we study in this paper include identical machine
model with job precedence constraints, with uniform and non-uniform job sizes, related machine
model with job precedence constraints and unrelated machine model.
A major theme in our results is the use of time-indexed linear programming relaxations. Given
the time aspect of scheduling problems, they are natural relaxations for their respective problems.
However, to the best of our knowledge, many of these relaxations were not studied in the literature
and thus their power in deriving improved approximation ratios was not well-understood. Compared
to other types of relaxations, solutions to these relaxations give fractional scheduling of jobs on
machines. Many of our improved results were obtained by using the fractional scheduling to identify
the loose analysis in previous results.
∗

Department of Computer Science and Engineering, University at Buffalo, Buffalo, NY, USA

1

1.1

Definitions of Problems and Our Results

We now formally describe the problems we study in the paper and state our results. In all of
these problems, we have a set J of n jobs, P
a set M of m machines, each job j ∈ J has a weight
wj ∈ Z>0 , and the objective to minimize is j∈J wj Cj , where Cj is the completion time of the job
j. We consider non-preemptive schedules only. So, a job must be processed on a machine without
interruption. For simplicity, this global setting will not be repeated when we define problems.
Scheduling on Identical Machines with Job Precedence Constraints In this problem,
each job j ∈ J has a processing time (or size) pj ∈ Z>0 . The m machines are identical; each job j
must be scheduled on one of the m machines non-preemptively; namely, j must be processed during
a time interval of length pj on some machine. The completion time of j is then the right endpoint
of this interval. Each machine at any time can only process at most one job. Moreover, there are
precedence constraints given by a partial order “≺”, where a constraint j ≺ j ′ requires that job
j ′ can only start after job j is completed. Using the popular
three-field notation introduced by
P
Graham et al. [17], this problem is described as P prec
j wj Cj .
For the related problem P |prec|Cmax , i.e, the problem with the same setting but with the
makespan objective, the seminal work of Graham [16] gives a 2-approximation algorithm, based on
a simple machine-driven list-scheduling algorithm. In the algorithm, the schedule is constructed in
real-time. As time goes, each idle machine shall pick any available job to process (a job is available
if it is not scheduled but all its predecessors are completed.), if such a job exists; otherwise, it
remains idle until some job becomes available. On the negative side, Lenstra and Rinnooy Kan
[23] proved a (4/3 − ǫ)-hardness of approximation for P |prec|Cmax . Under some stronger version
of the Unique Game Conjecture (UGC) introduced by Bansal and Khot [1], Svensson [39] showed
that P |prec|Cmax is hard to approximate within a factor of 2 − ǫ for any ǫ > 0.
With precedence constraints, the weighted completion time objective is more general than
makespan: one can create a dummy job of size 0 and weight 1 that must be processedPafter all
jobs in J, which have weight 0. Thus, the above negative results carry over to P prec
j wj Cj .
Indeed, Bansal and Khot [1] showed that the problem with even one machine is already hard to
approximate within a factor of 2 − ǫ, P
under their stronger version of UGC. However, no better
hardness results are known for P prec
j wj Cj , compared to those for P |prec|Cmax .
On the positive side, by combining the
Plist-scheduling algorithm of Graham [16] with a convex programming relaxation for P prec
j Cj , Hall et al. [18] gave a 7-approximation for
jw
P
P
P prec
j wj Cj . For the special case 1|prec|
j wj Cj of the problem where there is only 1 machine, Hall et al. [18] gave a 2-approximation, which matches the (2 − ǫ)-hardness assuming the
stronger version of UGC due to [1]. Later, Munier,PQueyranne and Schulz ([27], [29]) gave the
current best 4-approximation algorithm for P prec
j wj Cj , using a convex programming relaxation similar to that in Hall et al. [18] and in Charkrabarti et al. [6]. The convex programming
gives a completion time vector (Cj )j∈J , and the algorithm of [27] runs a job-driven list-scheduling
algorithm using the order of jobs determined by the values Cj − pj /2. In the algorithm, we schedule
jobs j one by one, according to the non-increasing order of Cj − pj /2; at any iteration, we schedule
ej − pj , C
ej ] with the minimum C
ej , subject to the precedence constraints and the
j at an interval (C
m-machine constraint. It has been a long-standing open problem to improve this factor of 4 (see
the discussion after Open Problem 9 in [33]).
Munier, Queyranne and P
Schulz [27] also considered an important special case of the problem,
denoted as P prec, pj = 1
j wj Cj , in which all jobs have size pj = 1. They showed that the
2

approximation ratio of their algorithm becomes 3 for the special case, which has not been improved
since then. On the negative side, the 2 − ǫ strong UGC-hardness result of Bansal and Khot also
applies to this special case.
P
In this paper, we improve the long-standing approximation ratios of 4 and 3 for P prec
j wj Cj
P
and P prec, pj = 1
j wj Cj due to Munier, Queyranne and Schulz [27, 29]:
P
Theorem 1.1. There is a 2+ 2 ln 2+ ǫ < (3.387+ ǫ)-approximation algorithm for P prec
j wj Cj ,
for every ǫ > 0.
√
P
Theorem 1.2. There is a 1 + 2 < 2.415-approximation algorithm for P prec, pj = 1
j wj Cj .

Scheduling on Related Machines with Job Precedence Constraints Then we consider
the scheduling
problem on related machines. We have all the input parameters in the problem
P
P |prec| j wj Cj . Additionally, each machine i ∈ M is given a speed si > 0 and the time of
processing job j on machine i is pj /si (so the m machines are not identical any more). A job
j must be scheduled on some machine i during
P an interval of length pj /si . Using the three-field
notation, the problem is described as Q|prec| j wj Cj .
Chudak and Shmoys [12] gave the current best O(log m) approximation algorithm for the prob√
lem, improving upon the previous O( m)-approximation due to Jaffe [20]. Using a general framework of Hall et al. [18] and Queyranne and Sviridenko [30], that converts an algorithm for a
scheduling problem with makespan objective to an algorithm for the correspondent problem
P with
weighted completion time objective, Chudak and Shmoys reduced the problem Q|prec| j wj Cj
to Q|prec|Cmax . In their algorithm for Q|prec|Cmax , we partition the machines into groups, each
containing machines of similar speeds. By solving an LP relaxation, we assign each job to a group
of machines. Then we can run a generalization of the Graham’s machine-driven list scheduling
problem, that respect the job-to-group assignment. The O(log m)-factor comes from the number
O(log m) of machine groups.
On the negative
side, all the hardness results for P |prec|Cmax carry over to both Q|prec|Cmax
P
and Q|prec| j wj Cj . Recently Bazzi and Norouzi-Fard [5] showed that assuming the hardness of
some optimization problem on k-partite graphs, both problems are hard to be approximated within
any constant.
In this paper, we give a slightly better approximation
ratio than O(log m) due to Chudak and
P
Shmoys [12], for both Q|prec|Cmax and Q|prec| j wj Cj :
Theorem
P 1.3. There are O(log m/ log log m)-approximation algorithms for both Q|prec|Cmax and
Q|prec| j wj Cj .

Scheduling on Unrelated Machines Finally, we consider the classic scheduling problem to
minimize total weighted completion time on unrelated machines (without precedence constraints).
In this problem we are given a number pi,j ∈ Z>0 for every i ∈ M,
P j ∈ J, indicating the time needed
to process job j on machine i. This problem is denoted as R|| j wj Cj .
For this problem, there are many classic 3/2-approximation algorithms, based on a weak timeindexed LP relaxation [32] and a convex-programming relaxation ([36], [34]). These algorithms are
all based on independent rounding. Solving some LP (or convex programming) relaxation gives
yi,j values, where each yi,j indicates the fraction of job j that is assigned to machine i. Then
the algorithms randomly and independently assign each job j to a machine i, according to the
3

distribution {yi,j }i . Under this job-to-machine assignment, the optimum scheduling can be found
by applying the Smith rule on individual machines.
Improving the 3/2-approximation ratio had been a long-standing open problem (see Open Problem 8 in [33]). The difficulty of improving the ratio comes from the fact P
that any independent
rounding algorithm can not give a better than a 3/2-approximation for R|| j wj Cj , as shown by
Bansal, Srinivasan and Svensson [4]. This lower bound is irrespective of the relaxation used: even
if the fractional solution is already a convex combination of optimum integral schedules, independent rounding can only give a 3/2-guarantee. To overcome this barrier, [4] introduced a novel
dependence rounding scheme, which guarantees some strong negative correlation between events
that jobs are assigned to the same machine i. Combining this with their lifted SDP relaxation for
the problem,PBansal, Srinivasan and Svensson gave a (3/2 − c)-approximation algorithm for the
problem R|| j wj Cj , where c = 1/(108 × 20000). This solves the long-standing open problem in
the affirmative.
Besides the slightly improved approximation ratio, our main contribution for this problem is
that the (1.5− c)-approximation ratio can also be achieved using the following natural time-indexed
LP relaxation:
X X
xi,j,s(s + pi,j )
s.t.
(LPR||wC )
min
wj
i,s

j

X

X

xi,j,s = 1

∀j

(1)

xi,j,s = 0

∀i, j, s > T − pi,j

(3)

xi,j,s ≤ 1

∀i, t

(2)

xi,j,s ≥ 0

∀i, j, s

(4)

i,s

j,s∈(t−pi,j ,t]

InP
the above LP, T is a trivial upper bound on the makespan of any reasonable schedule
(T = j maxi:pi,j 6=∞ pi,j suffices). i, j, s and t are restricted to elements in M, J, {0, 1, 2, · · · , T − 1}
and [T ] respectively. xi,j,s indicates whether job j is processed
P onPmachine i with starting time s.
The objective to minimize is the weighted completion time j wj i,s xi,j,s (s+pi,j ). Constraint (1)
requires every job j to be scheduled. Constraint (2) says that on every machine i at any time point
t, only one job is being processed. Constraint (3) says that if job j is scheduled on i, then it can
not be started after T − pi,j . Constraint (4) requires all variables to be nonnegative.
P
Theorem 1.4. The LP relaxation (LPR||wC ) for R|| j wj Cj has an integrality gap of at most
1
. Moreover, there is an algorithm that, given a valid fractional
solution x to
1.5 − c, where c = 6000
P
P
(LPR||wC ), outputs a random valid schedule with expected cost at most (1.5 − c) j wj i,s xi,j,s (s +
pi,j ), in time polynomial in the number of non-zero variables of x.1
P
The above algorithm leads to a (1.5 − c)-approximation for R|| j wj Cj immediately if T is
polynomially bounded. In Section 6, we shall show how to handle the case when T is superpolynomial.

1.2

Our Techniques

A key technique in many of our results is the use of time-indexed LP relaxations. For the identical
machine setting, we have variables xj,t indicating whether job j is scheduled in the time-interval
(t − pj , t]; we can visualize xj,t as a rectangle of height xj,t with horizontal span (t − pj , t]. With this
1

We assume x is given as a sequence of (i, j, s, xi,j,s )-tuples with non-zero xi,j,s .

4

visualization, it is straightforward to express the objective function, and formulate the machinecapacity constraints and the precedence constraints. For the unrelated machine model, the LP we
use is (LPR||wC ). (We used starting points to index intervals, as opposed to ending points; this is
only for the simplicity of describing the algorithm.) Each xi,j,s can be viewed as a rectangle of
height xi,j,s on machine i with horizontal span (s, s + pi,j ]. The rectangle structures allow us to
recover the previous state-of-art results, and furthermore to derive the improved approximation
results by identifying the loose parts in these algorithms and analysis.
P
P |prec| j wj Cj Let us first consider the scheduling problem on identical machines with job
precedence constraints. The 4-approximation algorithm of Munier, Queyranne, and Schulz [27, 29]
used a convex programming that only contains the completion time variables {Cj }j∈J . After
obtaining the vector C, we run the job-driven list scheduling algorithm, by considering jobs j
in increasing order of Cj − pj /2. To analyze the expected completion time of j ∗ in the output
schedule, focus on the schedule S constructed by the algorithm at the time j ∗ was inserted. Then,
we consider the total length of busy and idle slots in S before the completion of j ∗ separately. The
length of busy slots can be bounded by 2Cj ∗ , using the m-machine constraint. The length of idle
slots can also be bounded by 2Cj ∗ , by identifying a chain of jobs that resulted in the idle slots.
More generally, they showed that if jobs are considered in increasing order of Cj − (1 − θ)pj for
θ ∈ [0, 1/2] in the list scheduling algorithm, the factor for idle slots can be improved to 1/(1 − θ)
but the factor for busy slots will be increased to 1/θ. Thus, θ = 1/2 gives the best trade-off.
The rectangle structure allows us to exam the tightness of the above factors more closely: though
the 1/θ factor for busy slots is tight for every individual θ ∈ [0, 1/2], it can not be tight for every
such θ. Roughly speaking, the 1/θ factor is tight for a job j ∗ only when j ∗ has small pj ∗ , and all
the other jobs j considered before j ∗ in the list scheduling algorithm has large pj and Cj − θpj is
just smaller than Cj ∗ − θpj ∗ . However in this case, if we decrease θ slightly, these jobs j will be
considered after j ∗ and thus the bound can not be tight for all θ ∈ [0, 1/2]. We show that even if
we choose θ uniformly at random from [0, 1/2], the factor for busy time slots remains 2, as opposed
R 1/2 2
R 1/2
dθ = 2 ln 2,
to θ=0 2θ dθ = ∞. On the other hand, this decreases the factor for idle slots to θ=0 1−θ
thus improving the approximation factor to 2 + 2 ln 2. The idea of choosing a random point for each
job j and using them to decide the order in the list-scheduling algorithm has been studied before
under the name “α-points” [15, 18, 28, 9]. The novelty of our result is the use of the rectangle
structure to relate different θ values. In contrast, solutions to the convex programming of [27] and
the weak time-indexed LP relaxation of [32] lack such a structure.
P
P |prec, pj = 1| j wj Cj When jobs have uniform length, the approximation ratio of the algorithm
of [27] improves to 3. In this case, the θ parameter in the above algorithm becomes useless since
all jobs have the same length. Taking the advantage of the uniform job length, the factor for idle
time slots improves 1, while the factor for busy slots remains 2. This gives an approximation factor
of 3 for the special case.
To improve the factor of 3, we use another randomized procedure to decide the order of jobs
in the list scheduling algorithm. For every θ ∈ [0, 1], let Mjθ be the first time when we scheduled θ
fraction of job j in the fractional solution. Then we randomly choose θ ∈ [0, 1] and consider jobs
the increasing order of Mjθ in the list-scheduling algorithm. This algorithm can recover the factor
of 1 for total length of idle slots and 2 for total length of busy slots.
We again use the rectangle structure to discover the loose part in the analysis. With uniform
5

job size, the idle slots before a job j are caused only by the precedence constraints: if the total
length of idle slots before the completion time of j is a, then there is a precedence-chain of a jobs
ending at j; in other words, j is at depth at least a in the precedence graph. In order for the factor
1 for idle slots to be tight, we need to have a ≈ Cj . We show that if this happens, the factor for
busy time slots shall be much better than 2. Roughly speaking, the factor of 2 for busy time slots
is tight only if j is scheduled evenly among [0, 2Cj ]. However, if j is at depth-a in the dependence
graph, it can not be scheduled before time a ≈ Cj with any positive fraction.
A quantification of
√
this argument allows us to derive the improved approximation ratio 1 + 2 for this special case.
P
Q|prec| j wj Cj Our O(log m/ log log m)-approximation for related machine scheduling is a simple one. As mentioned earlier, by losing a constant factor in the approximation ratio, we can convert
the problem of minimizing the weighted completion time to that of minimizing the makespan, i.e,
the problem Q|prec|Cmax . To minimize the makespan, the algorithm of Chudak and Shmoys [12]
partitions machines into O(log m) groups according to their speeds. Based on their LP solution, we
assign each job j to a group of machines. Then we run the machine-driven list-scheduling algorithm,
subject to the precedence constraint, and the constraint that each job can only be scheduled to a
machine in its assigned group. The final approximation ratio is the sum of two factors: one from
grouping machines with different speeds into the same group, which is O(1) in [12], and the other
from the number of different groups, which is O(log m) in [12]. To improve the ratio, we make the
speed difference between machines in the same group as large as Θ(log m/ log log m), so that we
only have O(log m/ log log m) groups. Then, both factors become O(log m/ log log m), leading to
an O(log m/ log log m)-approximation for the problem. One remark is that in the algorithm of [12],
the machines in the same group can be assumed to have the same speed, since their original speeds
only differ by a factor of 2. In our algorithm, we have to keep the original speeds of machines, to
avoid a multiplication of the two factors in the approximation ratio.
P
R|| j wj Cj Then we sketch how we use our time-indexed LP to recover the (1.5−c)-approximation
of [4] (with much better constant c), for the scheduling
problem on unrelated machines to minimize
P
total weighted completion time, namely R|| j wj Cj .
The dependence rounding
procedure of [4] is the key component leading to a better than 1.5
P
approximation for R|| j wj Cj . It takes as input a grouping scheme: for each machine i, the jobs
are partitioned into groups with total fractional assignment on i being at most 1. The jobs in
the same group for i will have strong negative correlation towards being assigned to i. To apply
the theorem, they first solve the lift-and-project SDP relaxation for the problem, and construct
a grouping scheme based on the optimum solution to the SDP relaxation. For each machine
i, the grouping algorithm will put jobs with similar Smith-ratios in the same group, as the 1.5approximation ratio is caused by conflicts between these jobs. With the strong negative correlation,
the approximation ratio can be improved to (1.5 − c) for a tiny constant c = 1/(108 × 20000).
We show that the natural time-indexed relaxation (LPR||wC ) for the problem suffices to give
a (1.5 − c)-approximation. To apply the dependence rounding procedure, we need to construct a
grouping for every machine i. In our recovered 1.5-approximation
algorithm for the problem using
P
(LPR||wC ), the expected completion time of j is at most
x
(s + 1.5pi,j ), i.e, the average
i,j,s
i,s
starting time of j plus 1.5 times the average length of j in the LP solution. This suggests that a
job j is bad only when its average starting time is very small compared to its average length in the
LP solution. Thus, for each machine i, the bad jobs are those with a large weight of scheduling
6

intervals near the beginning of the time horizon. If these bad intervals for two bad jobs j and j ′
have large overlap, then they are likely to be put into the same group for i. To achieve this, we
construct a set of disjoint basic blocks {(2a , 2a+1 ] : a ≥ −2} in the time horizon. A bad job will be
assigned to a random basic block contained in its scheduling interval and two bad jobs assigned to
the same basic block will likely to be grouped together. Besides the improved approximation ratio,
we believe the use of (LPR||wC ) will shed light on getting an approximation ratio for the problem
that is considerably better than 1.5, as it is simpler than the lift-and-project SDP of [4]. Another
useful property of our algorithm is that the rounding procedure is oblivious to the weights of the
jobs; this may be useful when we consider some variants of the problem.
Finally, we remark that Theorems 1.1, 1.2 and 1.3 can be easily extended to handle job arrival
times. However, to deliver the key ideas more efficiently, we chose not to consider arrival times.

1.3

Other Related Work

There is a vast literature on approximating algorithms for scheduling problems to minimize the total
weighted completion time. Here we only discuss the ones that are most relevant to our results; we
refer readers to [8] for a more comprehensive overview. When there are no precedence constraints,
the P
problems of minimizing
total weighted completion time on identical and related machines
P
(P || j wj Cj and Q|| j wj Cj ) admit PTASes ([38, 10]). For the problem of scheduling
P jobs on
unrelated machines with job arrival times to minimize weighted completion time (R|rj | j wj Cj ),
many classic results give 2-approximation algorithms ([36, 32, 22]); recently Im and Li [19] gave
a 1.8687-approximation for the problem, solving a long-standing open problem. Skutella [37] gave
√ √
a e/( e − 1) ≈ 2.542-approximation algorithm for the single-machine scheduling problem with
precedence constraints and job release times, improving upon the previous e ≈ 2.718-approximation
[31].
Makespan is an objective closely related to weighted completion time. As we mentioned,
for P |prec|Cmax , the Graham’s list scheduling algorithm gives a 2-approximation, which is the
best possible under a stronger version of UGC [1, 39]. For the special case of the problem
P m|prec, pj = 1|Cmax where there are constant number of machines and all jobs have unit size,
the recent breakthrough result of Levey
 and Rothvoss [26] gave a (1 + ǫ)-approximation with running time exp exp Om,ǫ (log2 log n) , via the LP hierarchy of the natural LP relaxation for the
problem. On the negative side, it is not even known whether P m|prec, pj = 1|Cmax is NP-hard or
not. For the problem R||Cmax , i.e, the scheduling of jobs on unrelated machines to minimize the
makespan, the classic result of Lenstra, Shmoys and Tardos [24] gives a 2-approximation, which
remains the best algorithm for the problem. Some efforts have been put on a special case of the
problem, where each job j has a size pj and pi,j ∈ {pj , ∞} for every i ∈ M (the model is called
restricted assignment model.) [13, 40, 7, 21].
When jobs have arrival times, the flow time of a job, which is its completion time minus its
arrival time, is a more suitable measurement of quality of service. There is a vast literature on
scheduling algorithms with flow time related objectives [25, 11, 14, 35, 3, 2]; since they are much
harder to approximate than completion time related objectives, most of these works can not handle
precedence constraints and need to allow preemptions of jobs.
Organization The proofs of Theorems 1.1 to 1.4 are given in Sections 2 to 5 respectively.
Throughout this paper, we assume the weights, lengths of jobs are integers. Let T be the maximum
7

P
P
makespan of any “reasonable” schedule. For problems P prec
j wj Cj and R||
j wj Cj , we first
assume T is polynomial in n. By losing a 1 + ǫ factor in the approximation ratio, we can handle
the case where T is super-polynomial. This is shown in Section 6.

2

Scheduling on Identical Machines with Job Precedence Constraints

In this section we give our (2 + 2 ln 2 + ǫ)-approximationP
for the problem of scheduling precedenceconstrained jobs on identical machines, namely P |prec| j wj Cj . We solve (LPP|prec|wC ) and run
the job-driven list-scheduling algorithm of [27] with a random order of jobs.

2.1

Time-Indexed LP Relaxation for P |prec|

P

j

w j Cj

In the identical machine setting, we do not need to specify which machine each job is assigned
to; it suffices to specify a scheduling interval (t − pj , t] for every job j. A folklore result says that
a set of intervals can be scheduled on m machines if and only if their congestion is at most m:
i.e, the number of intervals covering any time point is at most m. Given such a set of intervals,
there is a simple greedy algorithm to produce the assignment of intervals to machines. Thus, in
our LP relaxation and in the list-scheduling algorithm, we focus on finding a set of intervals with
congestion at most m.
P
P
P
We use (LPP|prec|wC ) for both P prec
j wj Cj and P prec, pj = 1
j wj Cj . Let T =
j pj
be a trivial upper bound on the makespan of any reasonable schedule. In the LP relaxation, we
have a variable xj,t indicating whether job j is scheduled in (t − pj , t], for every j ∈ J and t ∈ [T ].
Throughout this and the next section, t and t′ are restricted to be integers in [T ], and j, j ′ and j ∗
are restricted to be jobs in J.
min

X

X

j

xj,t = 1

t

j,t∈[t′ ,t′ +p

j)

X

xj,t ≤ m

∀j

(5)

∀t′

(6)

wj

X
t

xj,tt

X

t<t′ +pj ′

s.t.
xj ′ ,t ≤

X
t<t′

xj,t = 0
xj,t ≥ 0

xj,t

(LPP|prec|wC )
∀j, j ′ , t′ : j ≺ j ′

(7)

∀j, t < pj

(8)

∀j, t

(9)

P
P
The objective function is j wj t xj,t t, i.e, the total weighted completion time over all jobs.
Constraint (5) requires every job j to be scheduled. Constraint (6) requires that at every time
point t′ , at most m jobs are being processed. Constraint (7) requires that for every j ≺ j ′ and t′ ,
j ′ completes before t′ + pj ′ only if j completes before time t′ . A job j can not complete before pj
(Constraint (8)) and all variables are non-negative (Constraint P
(9)).
We solve (LPP|prec|wC ) to obtain x ∈ [0, 1]J×[T ] . Let
C
=
t xj,t t be the completion time of
P j
j in the LP solution. Thus, the value of the LP is j wj Cj . For every θ ∈ [0, 1/2], we define
Mjθ = Cj − (1 − θ)pj . Our algorithm is simply the following: choose θ uniformly at random
from (0, 1/2], and output the schedule returned by job-driven-list-scheduling(M θ ) (described in
Algorithm 1).

8

Algorithm 1 job-driven-list-scheduling(M )
Input: a vector M ∈ RJ≥0 used to decide the order of scheduling, s.t. if j ≺ j ′ , then Mj < Mj ′
e C
e ∈ RJ
Output: starting and completion time vectors S,
≥0
1: for every j ∈ J in non-decreasing order of Mj , breaking ties arbitrarily
ej ′ , or t ← 0 if {j ′ ≺ j} = ∅
2:
let t ← maxj ′ ≺j C
3:
find the minimum s ≥ t such that we can schedule j in interval (s, s + pj ], without increasing
the congestion of the schedule to m + 1
ej ← s + pj , and schedule j in (Sej , C
ej ]
4:
Sej ← s, C
e C)
e
5: return (S,
We first make a simple observation regarding the C vector, which follows from the constraints
in the LP.
′
Claim 2.1. For every pair of jobs j, j ′ such that j ≺ j ′ , we have Cj + pj ′ ≤
! Cj .
X
X
X
X
P roof.
Cj + p j ′ =
xj,t′ t′ + pj ′ =
1−
xj,t′ + pj ′ =
xj,t′ + pj ′

≤
=

X
t



1 −

X

t′ ≥pj ′

t′

X

t′ <t+pj ′



xj ′ ,t′  + pj ′ =

(t′ − pj ′ )xj ′ ,t′ + pj ′ =

t

t′ ,t≤t′

X
t′

X

t,t′ ≥t+pj ′

xj ′ ,t′ + pj ′ =

t′ <t

X

t′ xj ′ ,t′ − pj ′ + pj ′ = Cj ′ .

t′

xj ′ ,t′



t : t ≤ t′ − p j ′

+ pj ′

The inequality used Constraint (7); some of the equalities used Constraint (5) and (8) and the
definitions of Cj and Cj ′ .
Indeed, our analysis does not use the full power of Constraint (7), except for the above claim
which is implied by the constraint. Thus, we could simply use Cj + pj ′ ≤ Cj ′ (along with the
definitions of Cj ’s) to replace Constraint (7) in the LP. However, in the algorithm for the problem
with unit job lengths (described in Section 3), we do need Constraint (7). To have a unified LP
for both problems, we chose to use Constraint (7). Our algorithm does not use x-variables, but we
need them in the analysis.

2.2

Analysis

Our analysis is very similar to that in [27]. We fix a job j ∗ from now on and we shall upper bound
ej ∗ ]
E[C
ej ∗ is determined and will not be changed
. Notice that once j ∗ is scheduled by the algorithm, C
Cj ∗

later. Thus, we call the schedule at the moment the algorithm just scheduled j ∗ the final schedule.
We can then define idle and busy points and slots w.r.t this final schedule. We say a time
point τ ∈ (0, T ] is busy if the congestion of the intervals at τ is m in the schedule (in other words,
all the m machines are being used at τ in the schedule); we say τ is idle otherwise. We say a
left-open-right-closed interval (or slot) (τ, τ ′ ] (it is possible that τ = τ ′ , in which case the interval
is empty) is idle (busy, resp.) if all time points in (τ, τ ′ ] are idle (busy, resp.).
ej ∗ respectively, w.r.t the
Then we analyze the total length of busy and idle time slots before C
final schedule. For a specific θ ∈ (0, 1/2], the techniques in [27] can bound the total length of
9

C

C

∗

∗

j
idle slots by 1−θ
and the total length of busy slots by θj . Thus choosing θ = 1/2 gives the best
4-approximation, which is the best using this analysis. Our improvement comes from the bound on
ej ∗ is
the total length of busy time slots. We show that the expected length of busy slots before C
Cj ∗
at most 2Cj ∗ , which is much better than the bound Eθ∼R (0,1/2] θ = ∞ given by directly applying

C

∗

the bound for every θ. We remark that the θj bound for each individual θ is tight and thus can
not be improved; our improvement comes from considering all possible θ’s together.
Bounding the Expected Length of Idle Slots We first bound the total length of idle slots
ej ∗ , the completion time of job j ∗ in the schedule produced by the algorithm. Lemma 2.2
before C
and 2.3 are established in [27] and we include their proofs for completeness.

Lemma 2.2. Let j ∈ J be a job in the final schedule with Sej > 0. Then we can find a job j ′ such
that
ej ′ , Sej ] is busy,
• either j ′ ≺ j and (C
• or Mj ′ ≤ Mj , Sj ′ < Sj and (Sj ′ , Sej ] is busy.

Proof. Recall that busy and idle slots are defined w.r.t the final schedule, i.e, the schedule at the
moment we just scheduled j ∗ . We first assume (Sej − 1, Sej ] is idle. Then before the iteration for j,
the interval (Sej − 1, Sej + pj ] is available for scheduling and thus scheduling j at (Sej − 1, Sej − 1 + pj ]
ej ′ .
will not violate the congestion constraint. Therefore, it must be the case that Sej = maxj ′ ≺j C
′
e
e
e
e
So, there is a job j ≺ j such that Cj ′ = Sj . Since (Cj ′ , Sj ] = ∅, the first property holds.
So we can assume (Sej − 1, Sej ] is busy. Let (τ, τ ′ ] be the maximal busy slot that contains
ej ′ , Sej ]
ej ′ ≥ τ , then the first property holds since (C
(Sej − 1, Sej ]. If there is a job j ′ ≺ j such that C
′
is busy. So, we can assume that no such job j exists.
ej < Sej ,
As τ is the starting point of a maximal busy slot, there is a job j1 with Sj1 = τ < Sej . If C
1
e
e
e
e
then there is a job j2 with Cj1 = Sj2 < Sj , as (Cj1 , Cj1 + 1] is busy. If Cj2 < Sj then there is job
ej = Sej < Sej . We can repeat this process to find a job jk such that τ ≤ Sj < Sej ≤ C
ej .
j3 with C
2
3
k
k
′
′
Let j = jk ; we claim that Mj ′ ≤ Mj . Otherwise, j is considered before j in the list scheduling
ej ] is available. Since we assumed that there
algorithm. At the iteration for j, the interval (Sej ′ , C
ej ′′ ≥ τ , j should be started at Sj ′ , a contradiction. Thus, Mj ′ ≤ Mj
are no jobs j ′′ ≺ j such that C
′
and j satisfies the second property of the lemma.
Applying Lemma 2.2 repeatedly, we can identify a chain of jobs whose scheduling intervals cover
ej ∗ , which can be used to bound the total length of these slots. This leads
all the idle slots before C
to the following lemma from [27]:
ej ∗ is at most
Lemma 2.3. The total length of idle time slots before C

Cj ∗
1−θ .

Proof. Let j0 = j ∗ ; if Sj0 > 0, we apply Lemma 2.2 for j = j0 to find a job j ′ and let j1 = j ′ . If
Sj1 > 0, then we apply the lemma again for j = j1 to find a job j ′ and let j2 = j ′ . We can repeat
the process until we reach a job jk with Sjk = 0. For convenience, we shall revert the sequence so
that j ∗ = jk and Sj0 = 0. Thus, we have found a sequence j0 , j1 , · · · , jk = j ∗ of
i jobs such that
ej , Sj
Sj = 0, and for each ℓ = 0, 1, 2, · · · , k − 1, either (i) jℓ ≺ jℓ+1 and C
is busy, or (ii)
0

ℓ

Mjℓ ≤ Mjℓ+1 , Sjℓ < Sjℓ+1 and (Sjℓ , Sjℓ+1 ] is busy.

10

ℓ+1

We say ℓ is of type-1 if ℓ satisfies (i); otherwise, we say ℓ is of type-2 (ℓ must satisfy (ii)). The
interval (0, Sj ∗ ] can be broken into k intervals: (Sj0 , Sj1 ], (Sj1 , Sj2 ], · · · , (Sjk−1 , Sjk ]. If some ℓ is of
ej , Sj ] is busy. Let L be the set of type-1
type-2, then (Sjℓ , Sjℓ+1 ] is busy; if ℓ is of type-1, then (C
ℓ
ℓ+1
[
ej ]. With this
∗
indices ℓ ∈ [0, k − 1]. Then, all the idle slots in (0, Sj ] are contained in
(Sjℓ , C
ℓ
ℓ∈L
∗
observation, we can bound the total length of idle slots in (0, Sj ] by
X
ℓ∈L

pj ℓ ≤

X
ℓ∈L

k−1
Mjθ∗
1 X θ
Cj ∗
1
(Mjθℓ+1 − Mjθℓ ) ≤
=
− pj ∗ .
(Mjℓ+1 − Mjθℓ ) ≤
1−θ
1−θ
1−θ
1−θ
ℓ=0





1
1
1
The first inequality holds since pjℓ = 1−θ
Mjθℓ+1 −
Cjℓ − Mjθℓ ≤ 1−θ
Cjℓ+1 − pjℓ+1 − Mjθℓ ≤ 1−θ

Mjθℓ , due to Claim 2.1. The second inequality is by the fact that Mjℓ ≤ Mjℓ+1 for every ℓ ∈ [0, k−1]
and the third inequality is by jk = j ∗ and Mjθ0 ≥ 0. The equality is by the definition of Mjθ∗ . Thus,
ej ∗ ] is at most Cj∗ .
the total length of idle slots in (0, C
1−θ

ej ∗ , over all choices of θ, is at most
Thus, the expected length of idle slots before C
Z

1/2

θ=0

Cj ∗
2dθ =
1−θ



1
2 ln
1−θ

1/2

θ=0



Cj ∗ = (2 ln 2)Cj ∗ .

(10)

Bounding the Expected Length of Busy Slots We now proceed to bound the total length of
ej ∗ . This is the key to our improved approximation ratio. For every θ ∈ [0, 1/2],
busy slots before C
θ
ej ∗ }. Thus, if θ < θ ′ , we have Jθ ⊇ Jθ′ . For every θ ∈ [0, 1/2] and j ∈ J0 , define
let Jθ = {j : Mj ≤ C
′
θj = sup {θ ∈ [0,
P1/2] : j ∈ Jθ }; this is well-defined since j ∈ J′ 0 . For any subset J ⊆ J of jobs, we
′
define p(J ) = j∈J ′ pj to be the total length of all jobs in J .
ej ∗ is at most
Lemma 2.4. For a fixed θ ∈ (0, 1/2], the total length of busy slots before C

ej ∗ ] is at most
Proof. The total length of busy time slots in (0, C
scheduled so far, which is at most
1
m

X

j∈J:Mjθ ≤Mjθ∗

pj ≤

1
m

X

pj =

j∈J:Mjθ ≤Cj ∗

1
m

1
m p(Jθ ).

times the total length of jobs

1
p(Jθ ).
m

The key lemma for our improved approximation ratio is an upper bound on the above quantity
when θ is uniformly selected from (0, 1/2]:
Z 1/2
p(Jθ )dθ ≤ mCj ∗ .
Lemma 2.5.
θ=0

Proof. Notice that we have
Z
Z 1/2
p(Jθ )dθ =
θ=0

1/2

X

θ=0 j∈J
0

pj 1j∈Jθ dθ =

X

j∈J0

pj

Z

1/2
θ=0

1j∈Jθ dθ =

X

θ j pj .

j∈J0

P
Thus, it suffices to prove that j∈J0 θj pj ≤ mCj ∗ . To achieve this, we construct a set of axisparallel rectangles. For each j ∈ J0 and t such that xj,t > 0, we place a rectangle with height xj,t
11

and horizontal span (t − pj , t − pj + 2θj pj ]. The total area of all the rectangles for j is exactly 2θj pj .
Notice that θj ≤ 1/2 and thus (t − pj , t − pj + 2θj pj ] ⊆ (t − pj , t].
P
P
θ
Notice that t xj,t (t − pj + θj pj ) = Cj − (1 − θj )pj = Mj j ≤ Cj ∗ , t xj,t = 1, and t − pj + θj pj
is the mass center2 of the rectangle for (j, t). Thus, the mass center of the union of all rectangles
for j is at most Cj ∗ . This in turn implies that the mass center of the union of all rectangles over
all j ∈ J0 and t, is at most Cj ∗ . Notice that for every t ∈ (0, T ], the total height of all rectangles
covering t is at most m, by Constraint (6), and the fact that (t − pj , t − pj + 2θj pj ] ⊆ (t − pj , t] for
every j ∈ J0 and t. Therefore, the total area of rectangles for all j P
∈ J0 and t is at most 2mCj ∗
(otherwise, the mass center will be larger than Cj ∗ ). So, we have j∈J0 2θj pj ≤ 2mCj ∗ , which
finishes the proof of the lemma.
ej ∗ is at
Thus, by Lemma 2.4 and Lemma 2.5, the expected length of busy time slots before C
most
Z 1/2
Z
p(Jθ )
2 1/2
2dθ =
p(Jθ )dθ ≤ 2Cj ∗ .
(11)
m
m θ=0
θ=0
Thus, by Inequalities (10) and (11), we have
h
i
ej ∗ ≤ (2 ln 2)Cj ∗ + 2Cj ∗ = (2 + 2 ln 2)Cj ∗ .
E C

Thus, we have proved the 2+2 ln 2+ǫ ≤ (3.387+ǫ)-approximation ratio for our algorithm, finishing
the proof of Theorem 1.1.
Remarks One might wonder if choosing a random θ from [0, θ ∗ ] for a different θ ∗ can improve
R θ∗ 1
the approximation ratio. For θ ∗ ≤ 1/2, the ratio we can obtain is θ1∗ + θ1∗ θ=0 1−θ
dθ = θ1∗ + θ1∗ ln θ1∗ ;
that is, the first factor (for busy time slots) will be increased to 1/θ ∗ and the second factor (for
idle time slots) will be decreased to θ1∗ ln θ1∗ . This ratio is minimized when θ ∗ = 1/2. If θ ∗ > 1/2,
however, the first factor does not improve to 1/θ ∗ , as the proof of Lemma 2.5 used the fact that
θj ≤ 1/2 for each j. Thus, using our analysis, the best ratio we can get is 2 + 2 ln 2.

3

Scheduling Unit-Length Jobs on Identical Machines with Job
Precedence Constraints

√
P
In this section, we give our (1 + 2)-approximation
j wj Cj . Again,
P algorithm for P prec, pj = 1
we solve (LPP|prec|wC ) to obtain x; define Cj = t xj,t for every j ∈ J. For this special case, we
define the random M -vector differently. In particular, it depends on the
P values of x variables. For
every j ∈ J and θ ∈ (0, 1], define Mjθ to be the minimum t such that tt′ =1 xj,t′ ≥ θ. Notice that
R1
P
Cj = θ=0 Mjθ dθ. Our algorithm for P prec, pj = 1
j wj Cj chooses θ uniformly at random from
θ
(0, 1], and then call job-driven-list-scheduling(M ) and output the returned schedule.
For every j ∈ J, we define aj to be the largest a such that there exists a sequence of a jobs
j1 ≺ j2 ≺ j3 ≺ · · · ≺ ja = j. Thus, aj is the “depth” of j in the precedence graph.
Claim 3.1. For every j ∈ J and t < aj , we have xj,t = 0.
2

Here, we use mass center for the horizontal coordinate of the mass center, since we are not concerned with the
vertical positions of rectangles.

12

Proof. By the definition of aj , there is a sequence of a := aj jobs j1 ≺ j2 ≺ · · · ≺ ja such that
ja = j. Let ta = t. If xja ,ta > 0, then by Constraint (7), there is an ta−1 ≤ ta − 1 such that
xja−1 ,ta−1 > 0. Then, there is an ta−2 ≤ ta−1 − 1 ≤ ta − 2 such that xja−2,ta−2 > 0. Repeating
this process, there will be an t1 ≤ ta − (a − 1) such that xj1 ,t1 > 0. This contradicts the fact that
ta = t ≤ a − 1.
Again, we fix a job j ∗ and focus on the schedule at the moment the algorithm just scheduled
ej ∗ ]/Cj ∗ (recall that C
ej ∗ is the
j ∗ ; we call this schedule the final schedule. We shall bound E[C
∗
completion time of j in the schedule we output), by bounding the total length of idle and busy
ej ∗ separately. Recall that a time point is busy if all the m
slots in the final schedule before C
machines are processing some jobs at that time, and idle otherwise. The next lemma gives this
bound for a fixed θ. The first (resp. second) term on the right side bounds the total length of busy
ej ∗ . The clean bound aj ∗ on the total length of idle slots comes from the
(resp. idle) slots before C
unit-job size property.
o
n
ej ∗ ≤ 1 j : Mjθ ≤ Mjθ∗ + aj ∗ .
Lemma 3.2. C
m
ej ∗ ] is at most 1/m times the total number of jobs
Proof. The total length of busy slotsnin (0, C
o
1
j : Mjθ ≤ Mjθ∗ .
scheduled so far, which is at most m
ej ∗ ]. We start from j1 = j ∗ . For every
We now bound the total length of idle slots in (0, C
ℓ = 1, 2, 3 · · · , let jℓ+1 ≺ jℓ be the job that is scheduled the last in the final schedule; if jℓ+1 does
not exists, then we let a = ℓ and break the loop. Thus, we constructed a chain ja ≺ ja−1 ≺ ja−2 ≺
· · · ≺ j1 = j ∗ of jobs. By the definition of aj ∗ , we have a ≤ aj ∗ .
We shall show that for every idle unit slot (t − 1, t] in (0, Cej ∗ ], some job in the chain is scheduled
ej > t (ℓ exists since
in (t − 1, t]. Assume otherwise; let ℓ ∈ [a] be the largest index such that C
ℓ
ej ∗ ). Then either jℓ+1 does not exist, or C
ej
ej ∗ − 1, C
ej ∗ ] and t < C
j1 = j ∗ is scheduled in (C
≤ t − 1.
ℓ+1
Consider the iteration when jℓ is considered in the list scheduling algorithm. Before the iteration,
(t − 1, t] is available for scheduling. Since jℓ is scheduled after t, there must be a job j ′ ≺ jℓ such
ej ′ ≥ t. Thus, we would have set jℓ+1 = j ′ , a contradiction.
that C
ej ∗ are covered by the scheduling intervals of jobs in the chain.
Thus, the idle slots before C
ej ∗ is at most a ≤ aj ∗ . Overall, we have C
ej ∗ ≤
So, nthe total number
of idle slots before C
o
1
m

j : Mjθ ≤ Mjθ∗

+ aj ∗ .

R1
We shall use g(θ) = Mjθ∗ for every θ ∈ (0, 1]. Notice that Cj ∗ = θ=0 g(θ)dθ. For simplicity,
let g(0) = limθ→0+ g(θ); so, g(0) will be the smallest t such that xj ∗ ,t > 0. By Claim 3.1, we have
g(θ)
X
xj,t . This is the total volume of job
g(0) ≥ aj ∗ . For every j ∈ J and θ ∈ [0, 1], define hj (θ) :=
t=1
P
j scheduled in (0, g(θ)]. Thus, we have j∈J hj (θ) ≤ g(θ). Noticing that Mjθ ≤ Mjθ∗ if and only if
ej ∗ ]
E[C
ej ∗ ≤ g(0) + 1 P
hj (θ) ≥ θ. So, by Lemma 3.2, we have C
j∈J 1hj (θ)≥θ . Thus, we can bound Cj ∗
m
by the superior of
R1
1 P
g(0) + m
j∈J θ=0 1hj (θ)≥θ dθ
(12)
R1
θ=0 g(θ)dθ
13

subject to
• g : [0, 1] → [1, ∞) is piecewise linear, left-continuous and non-decreasing,

(12.1)

• ∀j ∈ J, hj : [0, 1] → [0, 1] is piecewise linear, left-continuous and non-decreasing,
X
•
hj (θ) ≤ mg(θ), ∀θ ∈ [0, 1].

(12.2)
(12.3)

j∈J

.Z 1
To recover the 3-approximation ratio of [27], we know that g(0)
g(θ)dθ ≤ 1; this correθ=0

Z
. Z 1
1 X 1
e
sponds to the fact aj ∗ ≤ Cj ∗ . It is not hard to show
1hj (θ)≥θ dθ
g(θ)dθ ≤ 2.
m
θ=0
θ=0
j∈J

The tight factor 2 can be achieved when hj (θ) = θ for every j ∈ J and θ ∈ [0, 1] and g(θ) = nθ/m.
This corresponds to the following case: by the time θ-fraction of job j ∗ was completed, exactly θ
faction of every job j ∈ J was completed. However, the two bounds can not be tight simultaneously: the first bound being tight requires g to be a constant function, where the second bound
being tight requires g to be linear in θ. This is where√we obtain our improved approximation ratio.
Before formally proving that (12) is at most 1 + 2, we give the combination of g and {hj }j∈J
achieving the bound; the way we prove the upper bound is by showing that this combination√is the
worst possible.
In the worst case, we have hj (θ) = max {α, θ} for every θ ∈ [0, 1], where α = 2−1.
n
1 P
g(θ) = m
j∈J hj (θ) = m max {α, θ} for every θ ∈ [0, 1]. In this case, the numerator of (12) is
R
R1
2 )n
1
1 P
n
g(0) + m
= (α + 1) m
; the denominator is θ=0 g(θ)dθ = (1+α
j∈J θ=0 1hj (θ)≥θ dθ
2m . Thus, (12)
√
α+1
2.
in this case is (1+α
2 )/2 = 1 +
Computing the superior of (12) We now compute the superior of (12) subject to Constraints (12.1), (12.2) and (12.3). The functions g and hj ’s defined may have other stronger properties (e.g, they are piecewise constant functions); however in the process, we only focus on the
properties described above. In the following, j in a summation is over all jobs in J.
First, we can add the following constraint without changing the superior of (12).
1 X
hj (θ), ∀θ ∈ (θ ∗ , 1].
(13)
∃θ ∗ ∈ [0, 1], such that g(θ) = g(0), ∀θ ∈ [0, θ ∗ ], and g(θ) =
m
j

′
To
we take
n see this,
o any g and {hj }j satisfying Constraints (12.1) to (12.3). Let g (θ) =
P
1
max g(0), m
for every θ ∈ [0, 1]. Then g ′ : [0, 1] → [0, ∞) is piecewise-linear, leftj hj (θ)

continuous and non-decreasing because of Property (12.2); so g′ satisfies Property (12.1). Obviously
g′ satisfies Property (12.3). We define θ ∗ = sup {θ ∈ [0, 1] : g ′ (θ)P
= g ′ (0)}. Since g′ is left-continuous
1
∗
and monotone non-decreasing, we have g′ (θ) = g ′ (0) ≥ m
j hj (θ) for every θ ∈ [0, θ ] and
P
1
′
∗
′
g′ (θ) = m
j hj (θ) > g (0) for every θ ∈ (θ , 1]. Thus, g satisfies Constraint (13). Changing
′
g to g will not decrease (12):
the numerator
does not change and the denominator can only
o
n
1 P
decrease since g(θ) ≥ max g(0), m j hj θ = g′ (θ) for every θ ∈ [0, 1]. Thus, we can impose
Constraint (13), without changing the superior of (12).
Then, we can make the following constraint on {hj }j :
For every j ∈ J, hj is a constant over [0, θ ∗ ].
14

(14)

∗ , 1]. Then
For every j, we define h′j (θ) = hj (θ ∗ ) if θ ∈ [0, θ ∗ ] and h′j (θ) = hj (θ) if θ ∈ (θP
each h′j satisfies Constraint (12.2). Moreover, {h′j }j satisfies Constraint (12.3) since j h′j (θ) =
P
∗
∗
∗
′
j hj (θ ) ≤ mg(θ ) = mg(θ) for every θ ∈ [0, θ ]. Moreover, if we change hj to hj for every j ∈ J,
the denominator of (12) does not change and the numerator can only increase.
Finally, we can assume
X
hj (θ) = mg(θ), ∀θ ∈ [0, θ ∗ ].
(15)
j

P
Notice that the functions {hj }j and g are constant functions over [0, θ ∗ ] and j hj (θ) = mg(θ) for
θ ∈ (θ ∗ , 1]. If the constraint is not satisfied, we can find some j such that hj is not right-continuous
at θ ∗ . Then, we increase hj (θ) simultaneously for all θ ∈ [0, θ ∗ ] until the constraint is satisfied
or hj becomes right-continuous at θ ∗ . This process can be repeated until the constraint becomes
satisfied.
1 P
Thus, with all the constraints, we have g(θ) = m
j hj (θ) for every θ ∈ [0, 1]. So, (12) becomes

R1
P 
R1
1 P
1 P
h
(0)
+
1
dθ
j
j
θ=0 hj (θ)≥θ
j hj (0) + m
j θ=0 1hj (θ)≥θ dθ
m
=
.
R1
P R1
1 P
j θ=0 hj (θ)dθ
j θ=0 hj (θ)dθ
m
To bound the quantity, it suffices to upper bound
R1
h(0) + θ=0 1h(θ)≥θ dθ
sup
,
R1
h
h(θ)dθ
θ=0

(16)

where the superior is over all piecewise-linear, left-continuous and monotone non-decreasing functions h : [0, 1] → [0, 1].
Z 1
R1
h(θ)dθ ≥
Claim 3.3. Let α = h(0) and β = θ=0 1h(θ)≥θ dθ. Then 0 ≤ α ≤ β ≤ 1 and
θ=0

β2
α2
+β− .
2
2
Proof. β ≥ α because h(θ) ≥ θ holds for every θ ∈ [0, α]. To prove the second part, we can assume
that h(θ)
h(θ) to α for every θ ∈ (0, α]; this does not
R 1= α if θ ∈ [0, α]: otherwise, we canRchange
1
change θ=0 1h(θ)≥θ dθ and can only decrease θ=0 h(θ)dθ. Also, we can assume that h(θ) ≤ θ for
every θ R∈ [α, 1]. Otherwise, for every θ such Rthat h(θ) > θ, we decrease h(θ) to θ. This does not
1
1
change θ=0 1h(θ)≥θ dθ and can only decrease θ=0 h(θ)dθ.
Z 1
Z 1
Z 1

1 α2
(θ − h(θ))dθ.
h(θ)dθ = α2 +
θ − (θ − h(θ)) dθ = +
−
2
2
θ=α
θ=α
θ=0
Rb
2
For interval [a, b] ⊆ [θ ∗ , 1] such that h(a) = a, we have that θ=a (θ − h(θ))dθ ≤ (b−a)
2 . Since
R1
R1
(1−β)2
. Thus, the above quantity is at least
1
≤
1
−
β,
we
have
that
h(θ)<θ
2
θ=α
θ=α (θ − h(θ)) ≤
1
2

+

α2
2

−

(1−β)2
2

=

α2
2

+β−

β2
2 .

Thus, (16) is at most sup0≤α≤β≤1

α+β
2
α2
+β− β2
2

= sup0≤α≤β≤1

2(α+β)
2β−(α+β)(β−α) .

Scaling both α and β

Thus, we can assume β = 1 and (16) becomes supα∈[0,1] 2(1+α)
1+α2 .
√
√
√
2(1+
2−1)
2(1+α)
For α ∈ [0, 1], 1+α2 is maximized at α∗ = 2 − 1 and the maximum value is 1+(√2−1)2 = 2 + 1.
√
P
This finishes the proof of the ( 2 + 1)-approximation for P |prec, pj = 1| j wj Cj (Theorem 1.2).

up can only increase

2(α+β)
2β−(α+β)(β−α) .

15

4

Scheduling on Related Machines with Job Precedence Constraints

P
In this section, we give our O(log m/ log log m)-approximation for Q|prec|Cmax and Q|prec| j wj Cj ,
proving Theorem 1.3. This slightly improves the previous best O(log m)-approximation, due to Chudak and Shmoys [12]. Our improvement comes from a better tradeoff between two contributing
factors.
As in [12], we can convert the objective of minimizing total weighted completion time to minimizing makespan, losing a factor of 16. We now describe the LP used in [12] and state the theorem
for the reduction. Throughout this section, i is restricted to machines in M , and j and j ′ are
restricted to jobs in J.
min
X

xi,j = 1

i

pj

X xi,j

∀j

(17)

≤ Cj

∀j

(18)

X xi,j ′

≤ Cj ′

∀j, j ′ , j ≺ j ′

(19)

i

si

(LPQ|prec|Cmax )
1 X
pj xi,j ≤ D
si
j

si

i

Cj + p j ′

D

Cj ≤ D

xi,j , Cj ≥ 0

∀i

(20)

∀j

(21)

∀j, i

(22)

(LPQ|prec|Cmax ) is a valid LP relaxation for Q|prec|Cmax . In the LP, xi,j indicates whether job
j is scheduled on machine i. D is the makespan of the schedule, and Cj is the completion time
of j in the schedule. Constraint (17) requires every job j to be scheduled. Constraint (18) says
that the completion time of j is at least the processing time of j on the machine it is assigned to.
Constraint (19) says that if j ≺ j ′ , then Cj ′ is at least Cj plus the processing time of j ′ on the
machine it is assigned to. Constraint (20) says that the makespan D is at least the total processing
time of all jobs assigned to i, for every machine i. Constraint (21) says that the makespan D is
at least the completion time of any job j. Constraint (22) requires the x and C variables to be
non-negative.
The value of (LPQ|prec|Cmax ) provides a lower bound on the makespan of any valid schedule.
However, even if we require each xi,j ∈ {0, 1}, the optimum solution to the integer programming
is not necessarily a valid solution to the scheduling problem, since it does not give a scheduling
interval for each job j. Nevertheless, we can use the LP relaxation to obtain our O(log m/ log log m)approximation
P for Q|prec|Cmax . Using the following theorem from [12], we can extend the result
to Q|prec| j wj Cj :

Theorem 4.1 ([12]). Suppose there is an efficient algorithm A that can round a fractional solution
to (LPQ|prec|Cmax ) to a valid solution to the correspondent Q|prec|CP
max instance, losing only a factor
of α. Then there is a 16α-approximation for the problem Q|prec| j wj Cj .

Thus, from now on, we focus on the objective of minimizing the makespan; our goal is to design
an efficient rounding algorithm as stated in Theorem 4.1 with α = O(log m/ log log m). We assume
that m is big enough. For the given instance of Q|prec|Cmax , we shall first pre-processing the
instance as in [12] so that it contains only a small number of groups. In the first stage of the
16

pre-processing step, we discard all the machines whose speed is at most 1/m times the speed of the
fastest machine. Since there are m machines, the total speed for discarded machines is at most the
speed of the fastest machine. In essence, the fastest machine can do the work of all the discarded
machines; this will increase the makespan by a factor of 2. Formally, let i∗ be the machine with
the fastest speed. For every discarded machine i and any job j such that xi,j > 0, we shall increase
xi∗ ,j by xi,j and change this xi,j to 0. By scaling D by a factor of 2, the LP solution remains
feasible.
P x To see this, notice that the modification to the fractional solution can only ∗decrease
for each j. The only constraint we need to check is Constraint (20) for i = i . Since
pj i si,j
i
P
P
P
pj xi,j
pj xi,j
D
i discarded,j si∗ ≤
i discarded,j msi ≤
i discarded m ≤ D, moving the scheduling of jobs from
∗
discarded machines to i shall only increase the processing time of jobs on i∗ by D. Thus, we
assume all machines have speed larger than 1/m times the speed of the fastest machine. By scaling
speeds of machines uniformly, we assume all machines i have speed i ∈ [1, m), and |M | ≤ m.
In the second stage of the pre-processing step, we partition the machines into groups, where each
group contains machines with similar speeds. Let γ = log m/log log m.
 Then group Mk contains
machines with speed in [γ k−1 , γ k ), where k = 1, 2, · · · , K := logγ m = O(log m/ log log m). We
remark that that unlike [12], we can not round down the speed of each machine i to the nearest
power of γ. If we do so, we will lose a factor of (log m/ log log m) and finally we can only obtain an
O((log m/ log log m)2 )-approximation. Instead, we keep the speeds of machines unchanged.
M ′ ⊆ M of machines, we definePs(M ′ ) =
P We now define some useful notations. For a subset
′
′
i∈M ′ xi,j
i∈M ′ si to be the total speed of machines in M ; for M ⊆ M and j ∈ J, let xM ′ ,j =
′
be the total fraction of job j assigned to machines in M . P
For any job j, let ℓj be the largest integer ℓ such that K
k=ℓ xMk ,j ≥ 1/2. That is, the largest
ℓ such that at least 1/2 fraction of j is assigned to machines in groups ℓ to K. Then, let kj be
the index k ∈ [ℓj , K] that maximizes s(Mk ). That is, kj is the index of the group in groups ℓj
to K with the largest total speed. Later in the machine-driven list scheduling algorithm, we shall
constrain that job j can only be assigned to machines in group kj . The following claim says that
the time of processing j on any machine in Mkj is not too large, compared to processing time of j
in the LP solution.
X pj xi′ ,j
pj
.
≤ 2γ
Claim 4.2. For every j ∈ J, and any machine i ∈ Mkj , we have
si
s i′
′
i ∈M

Proof. Notice that
X xi′ ,j
≥
s i′
′

i ∈M

sum has

X

K
X

xMk ,j < 1/2 by our definition of ℓj . Thus,

k=ℓj +1

Sℓj
Mk
i′ ∈ k=1
1
−ℓ
j
.
si′ ≥ γ

xi′ ,j
1
≥ · γ −ℓj . This is true since
s i′
2

X

Sℓj
Mk
i′ ∈ k=1

ℓj
X

xMk ,j > 1/2. Then,

k=1

xi′ ,j ≥ 1/2 and every i′ in the

Since i is in group kj ≥ ℓj , i′ has speed at least γ ℓj −1 and thus
follows.
X pj
Claim 4.3.
≤ 2KD.
s(Mkj )

1
si

≤ γ 1−ℓj . Then the claim

j∈J

Proof. Focus on each job j ∈ J. Noticing that

K
X

k=ℓj

17

xMk ,j ≥ 1/2, and kj is the index of the group

with the maximum total speed, we have
K
K
X
X
xMk ,j
xMk ,j
1
≥
≥
.
s(Mk )
s(Mk )
2s(Mkj )
k=1

k=ℓj

Summing up the above inequality scaled by 2pj , over jobs j, we have
X
j∈J

K

K

k=1

k=1

K

X
X 1 X
X X xM ,j
pj
k
D = 2KD.
pj xMk ,j ≤ 2
≤2
pj
=2
s(Mkj )
s(Mk )
s(Mk )
j∈J

j∈J

k=1

P
To see the last inequality, we notice that j∈J pj xMk ,j is the total size of jobs assigned to group
k,
P s(Mk ) is the total speed of all machines in Mk and D
P is the makespan. Thus, we have
j∈J pj xMk ,j ≤ s(Mk )D. Formally, Constraint (20)
P says j∈J pj xi,j ≤ si D for every i ∈ Mk .
Summing up the inequalities over all i ∈ Mk gives j∈J pj xMk ,j ≤ s(Mk )D.

With the kj values, we can run the machine-driven list-scheduling algorithm in [12]. The
algorithm constructs the schedule in real time. Whenever a job completes (or at the beginning of
the algorithm), for each idle machine i, we attempt to schedule an unprocessed job j on i subject
to two constraints: (i) machine i can only pick a job j if i ∈ Mkj and (ii) all the predecessors of
j are completed. If no such job j exists, machine i remains idle until a new job is competed. We
use S to denote this final schedule; Let ij ∈ Mkj be the machine that process j in the schedule
constructed by our algorithm.
The following simple observation is the key to prove our O(log m/ log log m)-approximation.
Similar observations were made and used implicitly in [12], and in [16] for the problem on identical
machines. However, we think stating the observation in our way makes the analysis cleaner and
more intuitive. We say a time point t is critical, if some job starts or ends at t. To avoid ambiguity,
we exclude these critical time points from our analysis (we only have finite number of them). At
any non-critical time point t in the schedule, we say a job j is minimal if all its predecessors are
completed but j itself is not completed yet.
Observation 4.4. At any non-critical time point t in S, either all the minimal jobs j are being
processed, or there is a group k such that all machines in Mk are busy.
Proof. All the minimum jobs at t are ready for processing. If some such job j is not processed at
t, it must be the case that all machines in Mkj are busy.
As time goes in S, we maintain the precedence graph over J ′ , the set of jobs that are not
completed yet: we have an edge from j ∈ J ′ to j ′ ∈ J ′ if j ≺ j ′ . At any time point, the weight of a
job j is the time needed to complete the rest of job j on ij , i.e, the size of the unprocessed part of
job j, divided by sij . If at t, all minimum jobs are being processed, then the weights of all minimal
jobs are being decreased at a rate of 1. Thus, the length of the longest path of in the precedence
graph is being decreased at a rate of 1. The total length of the union of these time points is at
most length of the longest path in the precedence graph at time 0, which is at most
X X pj xi,j
X pj
≤ 2γD,
≤ max 2γ
max
H
H
s ij
si
j∈H

j∈H i∈M

18

where H is over all precedence chains of jobs. The first inequality is by Claim 4.2 and the second
inequality is by Constraints (19) and (21) in the LP.
If not all the minimal jobs are being processed at time t, then there must be a group k such
that all machines in group k are busy, by Observation 4.4. The total length of the union of all
these points is at most
P
X pj
X j:kj =k pj
=
≤ 2KD,
s(Mk )
s(Mkj )
k

j∈J

by Claim 4.3.
Thus, our schedule has makespan at most 2(γ + K)D = O(log m/ log log m)D, leading to an
O(log m/ log log m)-approximation for Q|prec|CmaxP
. Combining this with Theorem 4.1, we obtain
an O(log m/ log log m)-approximation for Q|prec| j wj Cj , finishing the proof of Theorem 1.3.
Indeed, as shown in [12], this factor is tight if we use (LPQ|prec|Cmax ).

5

(1.5−c)-Approximation Algorithm for Unrelated Machine Scheduling Based on Time-Indexed LP

In this section, we prove Theorem 1.4, using the dependence rounding scheme of [4] as a black-box.
We first describe the rounding algorithm and then give the analysis.

5.1

Rounding Algorithm

P
xi,j,s (s+
Let x be a feasible solution to (LPR||wC ) as stated in Theorem 1.4. Again, we use Cj = i,sP
pi,j ) to denote
the
completion
time
of
j
in
the
LP
solution;
thus
the
value
of
the
LP
is
j wj Cj .
P
LetP
yi,j = s xi,j,s for every pair i, j to denote the fraction of job j that is scheduled on machine i;
so i yi,j = 1 for every j. It is convenient to define a rectangle Ri,j,s for every xi,j,s > 0: Ri,j,s has
height xi,j,s , with horizontal span being (s, s + pi,j ]. We say Ri,j,s is the rectangle for j on machine
i at time s. We say a rectangle covers a time point (resp. a time interval), if its horizontal span
covers the time point (resp. the time interval).
P
We can recover the classic 1.5-approximation for R|| j wj Cj using (LPR||wC ). For each job
j ∈ J, randomly choose a rectangle for j: the probability of choosing Ri,j,s is xi,j,s , i.e, its height.
We shall assign job j to i and let τj be a random number in (s, s + pi,j ]. Then, all jobs j assigned to
machine i will be scheduled in increasing order of their τj values. To see this is a 1.5-approximation,
fix a job j ∗ ∈ J and condition on the event that j ∗ →i (indicating that j ∗ is assigned to machine i)
e
and
time of j ∗ inithe schedule returned by the algorithm. Notice that
h τj ∗ . Let Cj ∗ ibe thehcompletion
P
ej ∗ |j ∗ →i, τj ∗ ≤ E
E C
pi,j |τj ∗ + pi,j ∗ . If for some j 6= j ∗ , the selected rectangle
∗
j6=j :j→i,τj ≤τj ∗

for j is Ri,j,s and τj ≤ τj ∗ , then we say the pi,j term in summation inside E[·] on the right side
is contributed by the rectangle Ri,j,s. We then consider the contribution of each rectangle Ri,j,s ,
j 6= j ∗ to the expectation on the right side. The probability that we choose the rectangle Ri,j,s for j
is xi,j,s . Under this condition, the probability that τj ≤ τj ∗ is exactly fraction of the portion of Ri,j,s
that is before τj ∗ . When this happens, the contribution made by this Ri,j,s is exactly pi,j . Thus, the
contribution of Ri,j,s to the expectation is exactly the area of the portion of Ri,j,s before τj ∗ . Since
the total height of rectangles on i covering hany time pointi is at most
from
hP 1, the total contribution
i
∗
e
∗
∗
∗
∗
all rectangles on i is at most τj . Thus E Cj |j →i, τj ≤ E
+ pi,j ∗ ≤
j6=j ∗ :j→i,τj ≤τj ∗ pi,j |τj
19

τj ∗ + pi,j ∗ . Notice that conditioned
on choosing rectangle Ri,j ∗ ,s for j ∗ , the expected value of
h
i
P
P
ej ∗ ≤
τj ∗ is s + pi,j ∗ /2. Thus, E C
i,s xi,j ∗ ,s (s + pi,j ∗ /2 + pi,j ∗ ) =
i,s xi,j ∗ ,s (s + 1.5pi,j ∗ ) ≤
P
1.5 i,s xi,j ∗ ,s (s + pi,j ∗ ) = 1.5Cj ∗ . This recovers the 1.5-approximation ratio.
As [4] already showed, we can not beat 1.5 if the assignments of jobs to machines are independent. This lower bound is irrespective of the LP we use: even if the fractional solution is a convex
combination of integral solutions for the problem, independently assigning jobs to machines with
probabilities {yi,j }i,j can only lead to a 1.5-approximation. To overcome this barrier, [4] used an
elegant dependence rounding scheme, that is formally stated in the following theorem, which we
shall apply as a black-box:
Theorem 5.1 ([4]). Let ζ = 1/108. Consider a bipartite graph G = (M ∪J, E) between the set M of
machines and the set J of jobs. Let y ∈ [0, 1]E be fractional values on the edges satisfying y(δ(j)) = 1
for every job j ∈ J. For each machine i ∈ M , select any family of disjoint Ei1 , Ei2 , · · · , Eiκi ⊆ δ(i)
subsets of edges incident to i such that y(Eiℓ ) ≤ 1 for ℓ = 1, · · · , κi .
Then, there exists a randomized polynomial-time algorithm that outputs a random subset of the
edges E ∗ ⊆ E satisfying
(a) For every j ∈ J , we have |E ∗ ∩ δ(j)| = 1 with probability 1;
(b) For every e ∈ E, Pr[e ∈ E ∗ ] = ye ;
(c) For every i ∈ M and all e 6= e′ ∈ δ(i):
(


(1 − ζ) · ye ye′
Pr e ∈ E ∗ , e′ ∈ E ∗ ≤
y e y e′

if ∃ℓ ∈ [κi ], e, e′ ∈ Eiℓ ,
otherwise.

P
In the theorem, δ(u) is the set of edges incident to the vertex u in G, and y(E ′ ) = e∈E ′ ye
for every E ′ ⊆ E. We shall apply the theorem with G = (M ∪ J, E), with E = {(i, j) : yi,j > 0}
and y values being our y values. In the theorem, we can specify a grouping for edges incident to
every machine i ∈ M subject to the constraint that the total y-value of all edges in a group is at
most 1. The theorem says that we can select a subset E ∗ ⊆ E of edges respecting the marginal
probabilities {yi,j }(i,j)∈E , and satisfying the property that exactly one edge incident to any job j is
selected, and the negative correlation. The key to the improved approximation ratio in [4] is that
for two distinct edges e, e′ in the same group for i, their correlation is “sufficiently negative”.
The key to apply Theorem 5.1 is to define a grouping for each machine i. Notice that our
analysis for the
Pindependent rounding algorithm suggests that the expected completion time for
∗
j is at most i,s xi,j ∗ ,s (s + 1.5pi,j ∗ ); that is, there is no 1.5-factor before s. Thus, for the 1.5approximation ratio to be tight, for most rectangles Ri,j ∗ ,s , s should be very small compared to
pi,j ∗ . Intuitively, we define our random groupings such that, if such rectangles for j and for j ′ on
machine i overlap a lot, then j and j ′ will have a decent probability to be grouped together in the
grouping for i.
Defining the Groupings for Machines Our groupings for the machines are random. We
choose a τi,j value for every job j on every machine i such that yi,j > 0 (as opposed to choosing
only one τj value for a job j as in the recovered 1.5-approximation):
choose si,j at random such
P
that Pr[si,j = s] = xi,j,s /yi,j ; this is well-defined since s xi,j,s = yi,j . Then we let τi,j be a random
real number in (si,j , si,j + pi,j ].
20

Recall
P that the expected completion time of j in the schedule given by the independence rounding is i,s xi,j,s (s + 1.5pi,j ). As there is no 1.5-factor before s, we can afford to “shift” a rectangle
Ri,j,s to the right side by a small constant times s and use the shifted rectangles to sample {si,j }i,j
ej ] can still be bounded by
and {τi,j } values. On one hand, after the shifting of rectangles for j, E[C
1.5Cj . On the other hand, the shifting of rectangles for j will benefit the other jobs. Formally, for
every machine i and job j with yi,j > 0, we define
φi,j =

1 X
xi,j,s s
yi,j s

the average starting time of rectangles for job j on machine i, and
θi,j = 0.2(si,j + φi,j ) + 0.4yi,j pi,j .
to be the shifting parameter for job j on i. Namely, we shall use the values of {τi,j + θi,j }i,j to
decide the order of scheduling jobs.
We shall distinguish between good jobs and bad jobs. Informally, we say a job j is good on
a machine i, if using the independent rounding algorithm, we can already prove a better than
1.5-factor on the completion time of j, conditioned on that j is assigned to i. Formally,
Definition 5.2. Given a job j and machine i with yi,j > 0, we say j is good on i if
φi,j + yi,j pi,j ≥ 0.01pi,j .
Otherwise, we say job j is bad on i.
ej ∗ |j ∗ →i] ≤
Returning to the recovered 1.5-approximation algorithm, we can show that E[C
∗
(1.5 − Ω(1))(φi,j ∗ + pi,j ∗ ), if j is good on i. Either φi,j ∗ ≥ 0.005pi,j ∗ or yi,j ∗ ≥ 0.005. In the former
ej ∗ |j ∗ →i] ≤ φi,j ∗ + 1.5pi,j ∗ , which is at most (1.5 − Ω(1))(φi,j ∗ + pi,j ∗ ). In the latter
case, we have E[C
case, we total area of the portions of rectangles {Ri,j,s : j 6= j ∗ , s} before τj ∗ is smaller than τj ∗ by
yi,j ∗ pi,j ∗ /2, in expectation over all τj ∗ . This also can save a constant factor. The formal argument
will be made in the proof of Lemma 5.9, where we shall not use the strong negative correlation of
the dependence rounding scheme.

Now we are ready to define the groupings Eiℓ i∈M,j∈[κ ] in Theorem 5.1. Till this end, we fix
i
a machine i and show how to construct the grouping for i. If a job j is good on i, then (i, j) is not
in any group. It suffices to focus on bad jobs on i; keep in mind that for these jobs j, both φi,j /pi,j
and yi,j are tiny; thus si,j /pi,j and θi,j /pi,j will also be tiny with high probability.
Definition 5.3. A basic block is a time interval (2a , 2a+1 ] ⊆ (0, T ], where a ≥ −2 is an integer.
Definition 5.4. For a bad job j on machine i (thus yi,j > 0), we say the edge (i, j) is assigned to
a basic block (2a , 2a+1 ], denoted as j
(5.4a)

(2a , 2a+1 ]

i

a, if

⊆ (10φi,j , pi,j ], and

(5.4b) si,j + θi,j ≤ 2a , and

(5.4c) τi,j ∈ (2a , 2a+1 ].

21

Property (5.4a) requires the block to be inside (10φi,j , pi,j ] and Property (5.4c) requires τi,j to
be inside the block. Property (5.4b) requires that for the rectangle for j starting at si,j , after we
shift it by θi,j distance, it still contains (2a , 2a+1 ]. With Property (5.4a) and the definition of φi,j ,
we can prove the following lemma:
P
yi,j ≤ 10/9.
Lemma 5.5. For every machine i and a basic block (2a , 2a+1 ], we always have
i
j

a

P

Proof. Focus on a job j that is bad on i. We have s≤10φi,j xi,j,s ≥ 9yi,j /10, since otherwise we
P
shall have s xi,j,s s > 10φi,j · (yi,j /10) = φi,j yi,j , contradicting the definition of φi,j . Thus, yi,j ≤
P
i
(10/9) s≤10φi,j xi,j,s. If j a, then (2a , 2a+1 ] ⊆ (10φi,j , pi,j ] by Property (5.4a). Thus, (2a , 2a+1 ] is
P
P
xi,j,s ≤
yi,j ≤ (10/9)
covered by (s, s + pi,j ] for every s ≤ 10φi,j . Thus, we have
i
i
j

j

a

10/9. The second inequality used the fact that the total height of rectangles
machine i is at most 1.

a,s≤10φi,j
covering (2a , 2a+1 ]

on

For every basic block (2a , 2a+1 ], we partition the set of edges assigned to (2a , 2a+1 ] into at most
10 sets, each containing edges with total weight at most 1/8. This is possible since the total weight
of all edges assigned to (2a , 2a+1 ] is at most 10/9 by Lemma 5.5, and every bad job j on i has
yi,j < 0.01: we can keep adding edges to a set until the total weight is at least 1/9 and then we
start constructing the next set; the number of sets we constructed is at most (10/9)/(1/9) = 10
and each set has a total weight of at most 1/9 + 0.01 ≤ 1/8. Now, we can randomly drop at most
2 sets so that we have at most 8 sets remaining. Then we create a group for i containing the edges
in the remaining sets. Thus, the total y-value of the edges in this group is at most 1.
So, we have defined the grouping for i; recall that for each basic block (2a , 2a+1 ] ⊆ (10φi,j , pi,j ],
we may create a group. For a bad job j on i, (i, j) may not be assigned to any group. This may
happen if (i, j) is not assigned to any basic block, or if (i, j) is assigned to a basic block, but we
dropped the set containing (i, j) when constructing the group for the basic block.
Obtaining the Final Schedule With the groupings for the machines, we can now apply Theorem 5.1 to obtain a set E ∗ of edges that satisfies the properties of the theorem. If (i, j) ∈ E ∗ , then
we assign j to i; j is assigned to exactly one machine since E ∗ contains exactly one edge incident to
j. For all the jobs j assigned to i, we schedule them according to the increasing order of τi,j + θi,j ;
ej be the completion time of
with probability 1, no two jobs j have the same τi,j + θi,j value. Let C
j in this final schedule.

5.2

Analysis of Algorithm
i

Notations and Simple Observations From now on, we use j ∼j ′ to denote the event that (i, j)
and (i, j ′ ) are assigned to the same group for i, in the grouping scheme of Theorem 5.1. We use
i
j→i to denote the event that j is assigned to the machine i. Recall that j a indicates the event
that (i, j) is assigned to the basic block (2a , 2a+1 ]. From the way we construct the groups, the
following observation is immediate:
Observation 5.6. Let (2a , 2a+1 ] be a basic block, j 6= j ′ be bad jobs on i. We have
h
i
i
i
i
Pr j ∼j ′ j a, j ′ a ≥ 1 − 2/10 = 0.8.
22

The following observation will be used in the analysis:
Observation 5.7. Let j 6= j ′ be bad jobs on i. Then
i
h
i
Pr τi,j + θi,j < τi,j ′ + θi,j ′ j ∼j ′ = 1/2.

Proof. Fix a basic block (2a , 2a+1 ] such that (2a , 2a+1 ] ∈ (10φi,j , pi,j ] and (2a , 2a+1 ] ∈ (10φi,j ′ , pi,j ′ ]
(i.e, Property (5.4a) for both j and j ′ ).
Fix a si,j such that si,j + θi,j ≤ 2a (i.e, Property (5.4b)). Condition on this si,j , τi,j is uniformly
distributed in (si,j , si,j +pi,j ], and thus τi,j +θi,j is uniformly distributed in (si,j +θi,j , si,j +pi,j +θi,j ] ⊇
i

(2a , 2a+1 ]. Thus, conditioned on si,j and j

a, τi,j + θi,j is uniformly distributed in (2a , 2a+1 ].

i

This holds even if we only condition on j a, since the statement holds for any si,j satisfying
si,j + θi,j ≤ 2a .
′
hThe same holds
i for (i, j ). For simplicity, denote by e the event τi,j + θi,j < τi,j ′ + θi,j ′ . Thus,

Pr e j

i

a, j ′

i

i

a and j ′

i

a are independent). Conditioned on
h
i
i
i
i
j
a, the event
is independent of the event e. Thus, Pr e j ∼j ′ , j a, j ′ a = 1/2.
i
h
i
This holds for every a; thus, Pr e j ∼j ′ = 1/2.
i

i
a, j ′

a = 1/2 (notice that the events j
i
j ∼j ′

We define hi,j (τ ) =

P

s∈[τ −pi,j ,τ ) xi,j,s to be the total height of rectangles for j
h
that yi,ji,j
pi,j is the probability density function for τi,j . Let

on i that

Ai,J ′ (τ ) =
cover τ . It is easy to see
Rτ
P
′
′
j∈J ′ τ ′ =0 hi,j (τ )dτ be the total area of the parts of rectangles {Ri,j,s }j∈J ′ ,s that are before τ ;
we simply use Ai,j (τ ) for Ai,{j} (τ ). Notice that Ai,J (τ ) ≤ τ for every i and τ ∈ [0, T ].
′
It is also convenient to define a set of “shifted” rectangles. For every i, j, s, we define Ri,j,s
to be
′
the rectangle Ri,j,s shifted by 0.2(s + φi,j )+ 0.4yi,j pi,j units of time to the right. That is, Ri,j,s is the
rectangle of height xi,j,s with horizontal span (1.2s + 0.2φi,j + 0.4yi,j pi,j , 1.2s + 0.2φi,j + 0.4yi,j pi,j +
pi,j ].3 Notice that 0.2(s + φi,j ) + 0.4yi,j pi,j is the definition of θi,j if si,j = s. To distinguish these
rectangles from the original rectangles, we call the new rectangles R′ -rectangles and the original
ones R-rectangles.
Similarly, we define h′i,j (τ ) to be the total height of R′ -rectangles for j on i that covers τ . Thus,
′
Rτ
hi,j
variable τi,j + θi,j . Let A′i,j (τ ) = τ ′ =0 h′i,j (τ ′ )dτ ′ to be the total
yi,j pi,j is the PDF for the random
n
o
′
area of the parts of rectangles Ri,j,s
that are before τ . Notice that for every i ∈ M and
′
j∈J ,s

τ ∈ [0, T ], A′i,J (τ ) ≤ Ai,J (τ ) ≤ τ since we only shift rectangles to the right.
For two functions f : [0, T ] → R≥0 and F : [0, T ] → R≥0 , define
f ⊗F =

Z

T

f (τ )F (τ )dτ.
τ =0

Bounding Expected Completion Time Job by Job To analyze the approximation
ratio
h
i of
∗
∗
e
the algorithm, we fix a job j and a machine i such that yi,j ∗ > 0. We shall bound E Cj ∗ |j →i . It
 P xi,j∗ ,s

1
1
suffices to bound it by 1.5 − 6000
s yi,j ∗ (s + pi,j ∗ ) = 1.5 − 6000 (φi,j ∗ + pi,j ∗ ). The following
lemma gives a comprehensive upper bound that takes all parameters into account:
3

We slightly increase T so that even after shifting, all rectangles are inside the interval (0, T ].

23

h
i
ej ∗ j ∗ →i is at most
Lemma 5.8. Let I : [0, T ] → [0, T ] be the identity function. Then E C
1.4φi,j ∗ + (1.5 − 0.1yi,j ∗ ) pi,j ∗ −

i
h
h′i,j ∗
ζ X
i
Pr j ∼j ∗ yi,j pi,j .
⊗ (I − A′i,J ) −
yi,j ∗ pi,j ∗
2
∗

(23)

j6=j

h If we throw
i away all the negative terms, then we get an 1.4φi,j ∗ + 1.5pi,j ∗ upper bound on
∗
ej ∗ j →i , which is at most 1.5(φi,j ∗ + pi,j ∗ ). If either φi,j ∗ or yi,j ∗ is large, then we can prove
E C
a better than 1.5 factor; this coincides with our definition of good jobs. For a bad job j ∗ on i, we
shall show that the absolute value of the third and fourth term in (23) is large. The third term is
large if many rectangles are shifted by a large amount. The fourth term is where we use the strong
negative correlation of Theorem 5.1 from [4] to reduce the final approximation ratio.
Proof of Lemma 5.8. For notational convenience, let ej denote the event that τi,j +θi,j ≤ τi,j ∗ +θi,j ∗ ,
for every j ∈ J.
h
i
1 X
1
ej ∗
∗ →i × C
Pr [j ∗ →i, j→i, ej ] × pi,j
E
1
=
j
Pr[j ∗ →i]
yi,j ∗
j
i
i
h

h
X
1
i
i
Pr ej , j ∼j ∗ × Pr j ∗ →i, j→i ej , j ∼j ∗
=
yi,j ∗
j6=j ∗




i
i
∗
∗
∗
+ Pr ej , j 6∼j × Pr j →i, j→i ej , j 6∼j
× pi,j + pi,j ∗


i

i
1 X h
i ∗
∗
≤
Pr ej , j ∼j (1 − ζ)yi,j ∗ yi,j + Pr ej , j 6∼j yi,j ∗ yi,j pi,j + pi,j ∗
yi,j ∗
j6=j ∗
h
i
X
X
i
=
Pr [ej ] yi,j pi,j − ζ
Pr ej , j ∼j ∗ yi,j pi,j + pi,j ∗

h
i
ej ∗ j ∗ →i =
E C

j6=j ∗

=

X

j6=j ∗

j6=j ∗

Pr [ej ] yi,j pi,j −

i
h
ζ X
i
Pr j ∼j ∗ yi,j pi,j + pi,j ∗ .
2
∗

(24)

j6=j

ej ∗ =
The second equality is due to the fact that C

P

j→i:ej

pi,j , conditioned on j ∗ →i. The only
i

i

inequality is due to the third property of E ∗ in Theorem 5.1: conditioned on j ∼j ∗ (j 6∼j ∗ resp.),
the probability that j ∗ →i, j→i is at most (1 − ζ)yi,j ∗ yi,j (yi,j ∗ yi,j resp.), independent of the τ and
θ values (thus, independent of ej ). The last equality is due to Observation 5.7.
We focus on the first term of (24):
X

Pr[ej ]yi,j pi,j =

j6=j ∗

=

X

Pr [τi,j + θi,j ≤ τi,j ∗ + θi,j ∗ ] yi,j pi,j =

j6=j ∗
h′i,j ∗

yi,j ∗ pi,j ∗

⊗I −

h′i,j ∗
yi,j ∗ pi,j ∗

⊗ (I − A′i,J ) −
h′

∗

h′i,j ∗
⊗ A′i,J\j ∗
yi,j ∗ pi,j ∗
h′i,j ∗

yi,j ∗ pi,j ∗

⊗ A′i,j ∗ .

(25)
h′

To see the second equality, we notice that τi,j ∗ + θi,j ∗ has PDF y ∗i,jp ∗ , τi,j + θi,j has PDF y ∗i,jpi,j
i,j
i,j
i,j
and the two random quantities are independent if j 6= j ∗ . Thus, for a fixed τi,j ∗ + θi,j ∗ = τ , the
24

A′ (τ )

i,j
′
probability that τi,j + θi,j ≤ τ is exactly yi,j
pi,j ; thus contribution of j is exactly Ai,j (τ ). Summing
up over all j 6= j ∗ gives the equality. The third equality is by A′i,J\j ∗ ≡ I − (I − A′i,J ) − A′i,j ∗ .
The first term of (25) is

X xi,j ∗ ,s Z s+pi,j∗ (τ + 0.2(s + φi,j ∗ ) + 0.4yi,j ∗ pi,j ∗ )dτ
h′i,j ∗
⊗I =
yi,j ∗ pi,j ∗
yi,j ∗ τ =s
pi,j ∗
s
X xi,j ∗ ,s
=
(s + 0.5pi,j ∗ + 0.2(s + φi,j ∗ ) + 0.4yi,j ∗ pi,j ∗ ) = 1.4φi,j ∗ + 0.5pi,j ∗ + 0.4yi,j ∗ pi,j ∗ .
yi,j ∗
s
Now focus on the third term of (25) :
h′i,j ∗
⊗ A′i,j ∗ = yi,j ∗ pi,j ∗
yi,j ∗ pi,j ∗

Z

T
τ =0

h′i,j ∗ (τ )
yi,j ∗ pi,j ∗

Z

T

τ ′ =0

h′i,j ∗ (τ ′ )
yi,j ∗ pi,j ∗
1τ ′ <τ dτ dτ ′ =
.
yi,j ∗ pi,j ∗
2

(26)

The first equality holds since A′i,j ∗ is the integral of h′i,j ∗ . The second equality holds since the
probability that τ ′ < τ , where τ and τ ′ are i.i.d random variables and are not equal almost surely,
is 1/2.
Thus, by applying the above two equalities to (25), we have
X

j6=j ∗

Pr [ej ] yi,j pi,j = 1.4φi,j ∗ + 0.5pi,j ∗ −

h′i,j ∗
yi,j ∗ pi,j ∗

⊗ (I − A′i,J ) − 0.1yi,j ∗ pi,j ∗ .

h
i
ej ∗ |j ∗ →i is at most
Applying the above equality to (24), we that E C
1.4φi,j ∗ + (1.5 − 0.1yi,j ∗ ) pi,j ∗ −

h′i,j ∗

yi,j ∗ pi,j ∗

⊗ (I − A′i,J ) −

i
h
ζ X
i
Pr j ∼j ∗ yi,j pi,j .
2
∗
j6=j

This is exactly (23).
With the lemma, we shall analyze good jobs and bad jobs separately. For good jobs, the bound
follows directly from the definition:
h
i
ej ∗ j ∗ →i ≤ 1.4991(φi,j ∗ + pi,j ∗ ).
Lemma 5.9. If j ∗ is good on i, then E C

h
i
ej ∗ j ∗ →i ≤ 1.4φi,j ∗ + (1.5 − 0.1yi,j ∗ ) pi,j ∗ , by throwing the two negative terms
Proof. We have E C
in (23). Since j ∗ is good on i, we have φi,j ∗ + yi,j ∗ pi,j ∗ ≥ 0.01pi,j ∗ .
h
i
ej ∗ j ∗ →i ≤ 1.5(φi,j ∗ + pi,j ∗ ) − (0.1φi,j + 0.1yi,j ∗ pi,j ∗ )
E C
≤ 1.5(φi,j ∗ + pi,j ∗ ) − 0.01φi,j ∗ − 0.09(φi,j ∗ + yi,j ∗ pi,j ∗ )

≤ 1.5(φi,j ∗ + pi,j ∗ ) − 0.01φi,j ∗ − 0.09 × 0.01pi,j ∗ ≤ 1.4991(φi,j ∗ + pi,j ∗ ).

Thus, it remains to consider the case where j ∗ is bad on i. The rest of the section is devoted to
the proof of the following lemma:
h
i

ej ∗ j ∗ →i ≤ 1.5 − 1 (φi,j ∗ + pi,j ∗ ).
Lemma 5.10. If j ∗ is bad on i, then E C
6000
25

It suffices to give a lower bound on the sum of the absolute values of negative terms in (23):
0.1yi,j ∗ pi,j ∗ +

i
h
h′i,j ∗
pi,j ∗
ζ X
i
Pr j ∼j ∗ yi,j pi,j ≥
.
⊗ (I − A′i,J ) +
yi,j ∗ pi,j ∗
2
6000
∗

(27)

j6=j

h

i
j ∗ →i ≤ 1.4φi,j ∗ + 1.5 −



1
1
ej ∗
∗
If the above inequality holds, then we have E C
6000 pi,j ≤ 1.5 − 6000
(φi,j ∗ + pi,j ∗ ), implying Lemma 5.10.
To prove (27), we construct a set of configurations with total weight 1, and lower bound the
left-side configuration by configuration. We define a configuration U to be a set of pairs in J ×
{0, 1, 2, · · · , T − 1} such that for every two distinct pairs (j, s), (j ′ , s′ ) ∈ U , the two intervals (s, s +
pi,j ] and (s′ , s′ + pi,j ′ ] are disjoint.4 For the sake of the description, we also view (j, s) as the interval
(s, s + pi,j ] associated with the job j.
Recall that the total height of all R-rectangles on i covering any time point is at most 1. It is
a folklore
we can find a set of configurations, each configuration U with a zU > 0, such
P result that P
that U zU = 1 and U ∋(s,j) zU = xi,j,s for every j and s.
With the decomposition of the R-rectangles on i into a convex combination of configurations,
we can now analyze the contribution of each configuration to the left of (27). For any configuration
U , we define a function ℓU : [0, T ] → R≥0 as follows:
ℓeU (τ ) =

X

(j,s)∈U :1.2s+0.2φi,j +0.4yi,j pi,j ≤τ

min {τ − (1.2s + 0.2φi,j + 0.4yi,j pi,j ), pi,j } .

The definition comes from the following process. Focus on the intervals {(s, s + pi,j ) : (j, s) ∈ U }.
We then shift each interval (s, s + pi,j ] to the right by 0.2s + 0.2φi,j + 0.4yi,j pi,j ; notice that this
is exactly the definition of θi,j when si,j = s. Then ℓU (τ ) is exactly the total length of the subintervals of the shifted intervals before time point τ . Recalling that A′i,J (τ ) is the total area of the
′
parts of the R′ -rectangles on i before time point τ , and each Ri,j,s
is obtained by shifting Ri,j,s by
0.2s + 0.2φi,j + 0.4yi,j pi,j to the right, the following holds:
X
zU ℓU .
(28)
A′i,J ≡
U

Let cU (j) = {s : (j, s) ∈ U } be the number of pairs in U for the job j. Now, we can define the
contribution of U to the bound to be


′
X
 ζ
hi,j ∗
i
Pr[j ∼j ∗ ]pi,j cU (j) .
⊗ I − ℓU +
DU := zU 0.1pi,j ∗ cU (j ∗ ) +
yi,j ∗ pi,j ∗
2
∗
j6=j

Claim 5.11. The left side of (27) is exactly

P

U

DU .

Proof. Indeed, the three terms in (27) is respectively the sum over all U of each of theP
three terms
in the definition of DU . For the first and the third term, thePequality comes from yi,j = U zU cU (j)
for every j. The equality for the second term comes from U zU (I − ℓU ) = I − A′i,J .
4

Notice that this configuration does not necessarily correspond to a valid scheduling on i, since it may contain
two pairs with the same j.

26

Lower Bound the Contribution of Each U Now we fix some configuration U such that
zU > 0. Let a be the largest integer such that 2a+1 ≤ 0.9pi,j ∗ ; thus a ≥ −2. We can focus on the
basic block (2a , 2a+1 ]. Notice that the length of the basic block is 2a ≥ 0.9pi,j ∗ /4, by the definition
of a.
The following simple observations are useful in establishing our bounds.
′
a
Observation 5.12. If s ≤ 18φi,j ∗ , then Ri,j
∗ ,s will cover (2 , pi,j ∗ ].
′
a
a
Proof. The rectangle Ri,j
∗ ,s will cover (2 , pi,j ∗ ] if s + 0.2(s + φi,j ∗ ) + 0.4yi,j pi,j ∗ ≤ 2 , which is s ≤
a
∗
(2 −0.2φi,j ∗ −0.4yi,j pi,j ∗ )/1.2. Since j is bad on i, we have 0.2φi,j ∗ +0.4yi,j ∗ pi,j ∗ ≤ 0.4×0.01pi,j ∗ =
0.004pi,j ∗ . Thus, (2a − 0.2φi,j ∗ − 0.4yi,j pi,j ∗ )/1.2 ≥ (2a − 0.004pi,j ∗ )/1.2 ≥ (0.9/4 − 0.004)pi,j ∗ /1.2 ≥
0.9/4−0.004 1
a
∗
∗
∗
∗
∗
1.2
0.01 φi,j ≥ 18φi,j . Thus, if s ≤ 18φi,j , we have s + 0.2(s + φi,j ) + 0.4yi,j pi,j ≤ 2 .

Observation 5.13. For every τ ∈ (2a , pi,j ∗ ], we have h′i,j ∗ (τ ) ≥

17
∗
18 yi,j .

′
Proof. This comes from Observation 5.12. Ri,j
∗ ,s will cover τ if s ≤ 18φi,j ∗ . By the definition of
∗
φi,j and Markov inequality, the sum of xi,j ∗ ,s over all such s is at least 17
18 yi,j .

Observation 5.14. If τ ′ is not contained in the interior of any interval in U and τ ≥ τ ′ , then
τ − ℓU (τ ) ≥ min {0.2τ ′ , τ − τ ′ }.
Proof. Consider the definition of ℓU via the shifting of intervals. Since τ ′ is not contained in the
interior of any interval in U , an interval in U is either to the left of τ ′ or to the right of τ ′ . By the
way we shifting intervals, any interval to the right of τ ′ will be shifted by at least 0.2τ ′ distance to
the right. Thus, the sub-intervals of the intervals in U from max {τ ′ , τ − 0.2τ ′ } to τ will be shifted
to the right of τ . The observation follows.
Observation 5.15. If τ is covered by some interval (s, s + pi,j ] in U , then
τ − ℓU (τ ) ≥ min {0.2(s + φi,j ) + 0.4yi,j pi,j , τ − s} .
Proof. The interval (s, s + pi,j ] will be shifted by 0.2(s + φi,j ) + 0.4yi,j pi,j distance to the right.
So the sub-interval (max {τ − 0.2(s + φi,j ) − 0.4pi,j , s} , τ ] will be shifted to the right of τ . The
observation follows.
Equipped with these observations, we can analyze the contribution of U case by case:
Case 1: (2a , 0.92pi,j ∗ ] is not a sub-interval of any interval in U . In this case, there is τ ′ ∈
(2a , 0.92pi,j ∗ ) that is not in the interior of any interval in U . By Observation 5.14, any time point
in τ ∈ (0.95pi,j ∗ , pi,j ∗ ] has τ − ℓU (τ ) ≥ min {τ − τ ′ , 0.2τ ′ } ≥ min{0.95pi,j ∗ − 0.92pi,j ∗ , 0.2 × 2a } ≥
min {0.03pi,j ∗ , 0.2 × 0.9pi,j ∗ /4} = 0.03pi,j ∗ . By Observation 5.13, any such τ has h′ value at least
17
∗
18 yi,j . Thus, the contribution of U is
h′i,j ∗
17yi,j ∗
⊗ (I − ℓU ) ≥ zU ×
× (0.03pi,j ∗ ) × (0.05pi,j ∗ )
yi,j ∗ pi,j ∗
18yi,j ∗ pi,j ∗
zU pi,j ∗
.
≥ 0.0014zU pi,j ∗ ≥
6000

DU ≥ zU ×

Case 2: (2a , 0.92pi,j ∗ ] is covered by some interval (s, s + pi,j ] in U , and 0.2(φi,j + s) + 0.4yi,j pi,j ≥
0.002 × 2a . Focus on any τ ∈ (1.01 × 2a , 0.92pi,j ∗ ] ⊆ (2a , pi,j ∗ ]. By Observation 5.13, we have
27

∗
h′ (τ ) ≥ 17
18 yi,j . By Observation 5.15, we have τ − ℓU (τ ) ≥ min{0.2(φi,j + s) + 0.4yi,j pi,j , τ − s} ≥
min {0.002 × 2a , 0.01 × 2a } = 0.002 × 2a . Thus, the contribution of U is

h′i,j ∗

17yi,j ∗
⊗ (I − ℓU ) ≥ zU ×
× (0.002 × 2a ) × (0.92pi,j ∗ − 1.01 × 2a )
DU ≥ zU ×
yi,j ∗ pi,j ∗
18yi,j ∗ pi,j ∗


zU pi,j ∗
17
≥
× 0.002 × 0.9/4 × (0.92 − 1.01 × 0.9/2) zU pi,j ∗ ≥ 0.00019zU pi,j ∗ ≥
,
18
6000
where we used 0.9pi,j ∗ /4 ≤ 2a ≤ 0.9pi,j ∗ /2.

Case 3: (2a , 0.92pi,j ∗ ] is covered by some interval (s, s + pi,j ] in U , and 0.2(φi,j + s) + 0.4yi,j pi,j <
0.002 × 2a . If j = j ∗ , then DU ≥ zU × 0.1pi,j ∗ cU (j ∗ ) ≥ zU × 0.1pi,j ∗ . So, we assume j 6= j ∗ . This
is where we use the strong negative correlation between j and j ∗ . We shall lower bound Pr[j ∗

i

a]

i

and Pr[j a] separately.
1
φi,j ∗ /4 ≥ 10φi,j ∗ , by the fact that j ∗ is bad on i. Thus,
Notice that 2a ≥ 0.9pi,j ∗ /4 ≥ 0.9 × 0.01
a
a+1
′
a a+1 ],
(2 , 2 ] ⊆ (10φi,j ∗ , pi,j ∗ ], implying Property (5.4a) for j ∗ . If si,j ∗ = s and Ri,j
∗ ,s covers (2 , 2
17
then Property (5.4b) holds. By Observation 5.12, this happens with probability at least 18
. Thus,
we have
h
i 17 2a
17 0.9
i
·
≥
·
≥ 0.21.
Pr j ∗ a ≥
18 pi,j ∗
18 4
h
i
i
Now, we continue to bound Pr j a . To do this, we need to first prove that j is bad on i.
Indeed, φi,j + yi,j pi,j ≤ 5(0.2(φi,j + s) + 0.4yi,j pi,j ) < 5 × 0.002 × 2a ≤ 0.01pi,j , since (s, s + pi,j ] ⊇
(2a , 0.92pi,j ∗ ] ⊇ (2a , 2a+1 ], which is of length at least 2a . This implies that j is bad on i.
a+1 ≥ 2a+1 + 0.01 × 2a .
Then, s ≤ 0.002 × 2a /0.2 = 0.01 × 2a and s + pi,j > 0.92pi,j ∗ ≥ 0.92
0.9 × 2
a+1
a
This implies that pi,j ≥ 2 . Also, 2 ≥ 0.2φi,j /0.002 = 100φi,j ≥ 10φi,j . Thus, Property (5.4a)
holds.
For every s′ ≤ 50φi,j , we have 1.2s′ + 0.2φi,j + 0.4yi,j pi,j ≤ 60.2φi,j + 0.4yi,j pi,j ≤ 60.2
0.2 (0.2(φi,j +
a ≤ 2a . Thus, Property (5.4b) holds if s
s) + 0.4yi,j pi,j ) ≤ 60.2
×
0.002
×
2
≤
50φ
i,j
i,j . Notice that
0.2
i

a

Pr[si,j ≤ 50φi,j ] ≥ 0.98. Under this condition, the probability of j a is at least p2i,j ≥
h
i
i
pi,j ∗
pi,j ∗
Overall, Pr j a ≥ 0.98 × 0.9
4 pi,j ≥ 0.22 pi,j .
Thus, by Observation 5.6,
h
i h
i
pi,j ∗
pi,j ∗
i
i
i
Pr[j ∼j ∗ ] ≥ 0.8 Pr j ∗ a Pr j a ≥ 0.8 × 0.21 × 0.22
≥ 0.036
.
pi,j
pi,j
z p

i

0.9 pi,j ∗
4 pi,j .

i,j
Thus, the contribution of U is DU ≥ zU 2ζ Pr[j ∼j ∗ ]pi,j ≥ 0.018ζzU pi,j ∗ = U6000
.
zU pi,j ∗
.
By
Claim
5.11,
the
left side of (27)
Thus,
for
every
U
,
the
contribution
of
U
is
at
least
6000
P
P zU pi,j∗
pi,j ∗
is U DU ≥ U 6000 = h6000 . Thisifinishes the proof of Lemma 5.10.

ej ∗ |j ∗ →i ≤ 1.5 − 1 (φi,j ∗ + pi,j ∗ ). Deconditioning on j ∗ →i, we
So, we always have E C
6000
h
i


ej ∗ ≤ 1.5 − 1 P yi,j ∗ (φi,j ∗ + pi,j ∗ ) = 1.5 − 1 Cj . This finishes the proof of
have E C
i
6000
6000
Theorem 1.4.

28

∗

6

Handling Super-Polynomial T

P
In this section,
we
show
how
to
handle
the
case
when
T
is
super-polynomial
in
n
for
P
|prec|
j wj Cj
P
and R|prec| j wj Cj . The way
P we handle super-polynomial T is the same as that in [19]. [19]
considers the problem R|rj | j wj Cj , i.e, the unrelated machine job scheduling with job arrival
times. They showed how to efficiently obtain a (1 + ǫ) approximate LP solution that only contains
polynomial
number of non-zero variables. Since the problem they considered is more general than
P
R|| j wj Cj and their LP is alsoP
a generalization of our (LPR||wC ), their technique can be directly
applied to our algorithm for R||
P j wj Cj . Due to the precedence constraints, the technique does
not directly apply to P |prec| j wj Cj . However, with a trivial modification, it can handle the
precedence constraints as well. We omit the detail here since the analysis will be almost identical
to that in [19].

References
[1] Nikhil Bansal and Subhash Khot. Optimal long code test with one free bit. In Proceedings
of the 2009 50th Annual IEEE Symposium on Foundations of Computer Science, FOCS ’09,
pages 453–462. IEEE Computer Society, 2009.
[2] Nikhil Bansal and Janardhan Kulkarni. Minimizing flow-time on unrelated machines. In
Proceedings of the Forty-seventh Annual ACM Symposium on Theory of Computing, STOC
’15, pages 851–860. ACM, 2015.
[3] Nikhil Bansal and Kirk Pruhs. The geometry of scheduling. In Proceedings of the 2010 IEEE
51st Annual Symposium on Foundations of Computer Science, FOCS ’10, pages 407–414. IEEE
Computer Society, 2010.
[4] Nikhil Bansal, Aravind Srinivasan, and Ola Svensson. Lift-and-round to improve weighted
completion time on unrelated machines. In Proceedings of the Forty-eighth Annual ACM
Symposium on Theory of Computing, STOC ’16, pages 156–167. ACM, 2016.
[5] Abbas Bazzi and Ashkan Norouzi-Fard. Towards Tight Lower Bounds for Scheduling Problems,
pages 118–129. Springer Berlin Heidelberg, 2015.
[6] Soumen Chakrabarti, Cynthia A. Phillips, Andreas S. Schulz, David B. Shmoys, Cliff Stein,
and Joel Wein. Improved scheduling algorithms for minsum criteria, pages 646–657. Springer
Berlin Heidelberg, 1996.
[7] Deeparnab Chakrabarty, Sanjeev Khanna, and Shi Li. On (1, ǫ)-restricted asgsignment
makespan minimization. In Proceedings of the 26th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2015), 2015.
[8] C. Chekuri and S. Khanna. Approximation algorithms for minimizing average weighted completion time. Handbook of Scheduling: Algorithms, Models, and Performance Analysis. CRC
Press, Inc., Boca Raton, FL, USA, 2004.
[9] C. Chekuri, R. Motwani, B. Natarajan, and C. Stein. Approximation techniques for average
completion time scheduling. SIAM J. Comput., 31(1):146–166, January 2002.
29

[10] Chandra Chekuri and Sanjeev Khanna. A PTAS for Minimizing Weighted Completion Time
on Uniformly Related Machines, pages 848–861. Springer Berlin Heidelberg, 2001.
[11] Chandra Chekuri and Sanjeev Khanna. Approximation schemes for preemptive weighted flow
time. In Proceedings of the Thiry-fourth Annual ACM Symposium on Theory of Computing,
STOC ’02, pages 297–305. ACM, 2002.
[12] Fabián A. Chudak and David B. Shmoys. Approximation algorithms for precedenceconstrained scheduling problems on parallel machines that run at different speeds. In Proceedings of the Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA ’97,
pages 581–590. Society for Industrial and Applied Mathematics, 1997.
[13] Tomáš Ebenlendr, Marek Krčál, and Jiřı́ Sgall. Graph balancing: A special case of scheduling
unrelated parallel machines. In Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA ’08, pages 483–490. Society for Industrial and Applied
Mathematics, 2008.
[14] Naveen Garg and Amit Kumar. Minimizing average flow-time: Upper and lower bounds. In
Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science, FOCS
’07, pages 603–613. IEEE Computer Society, 2007.
[15] Michel X. Goemans. Improved approximation algorthims for scheduling with release dates. In
Proceedings of the Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA ’97,
pages 591–598. Society for Industrial and Applied Mathematics, 1997.
[16] R. L. Graham. Bounds on multiprocessing timing anomalies. SIAM JOURNAL ON APPLIED
MATHEMATICS, 17(2):416–429, 1969.
[17] 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. Ann. Discrete Math.,
4:287–326, 1979.
[18] Leslie A. Hall, Andreas S. Schulz, David B. Shmoys, and Joel Wein. Scheduling to minimize
average completion time: Off-line and on-line approximation algorithms. Math. Oper. Res.,
22(3):513–544, August 1997.
[19] Sungjin Im and Shi Li. Better unrelated machine scheduling for weighted completion time
via random offsets from non-uniform distributions. In IEEE 57th Annual Symposium on
Foundations of Computer Science, FOCS 2016, pages 138–147, 2016.
[20] Jeffrey M. Jaffe. Efficient scheduling of tasks without full use of processor resources. Theoretical
Computer Science, 12(1):1 – 17, 1980.
[21] Klaus Jansen and Lars Rohwedder. On the configuration-LP of the restricted assignment
problem. In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete
Algorithms, SODA ’17, pages 2670–2678. Society for Industrial and Applied Mathematics,
2017.
[22] VS Anil Kumar, Madhav V Marathe, Srinivasan Parthasarathy, and Aravind Srinivasan. Minimum weighted completion time. In Encyclopedia of Algorithms, pages 544–546. Springer,
2008.
30

[23] J. K. Lenstra and A. H. G. Rinnooy Kan. Complexity of scheduling under precedence constraints. Oper. Res., 26(1):22–35, February 1978.
[24] J. K. Lenstra, D. B. Shmoys, and É. Tardos. Approximation algorithms for scheduling unrelated parallel machines. Math. Program., 46(3):259–271, February 1990.
[25] Stefano Leonardi and Danny Raz. Approximating total flow time on parallel machines. In
Proceedings of the Twenty-ninth Annual ACM Symposium on Theory of Computing, STOC
’97, pages 110–119. ACM, 1997.
[26] Elaine Levey and Thomas Rothvoss. A (1+epsilon)-approximation for makespan scheduling
with precedence constraints using LP hierarchies. In Proceedings of the Forty-eighth Annual
ACM Symposium on Theory of Computing, STOC ’16, pages 168–177. ACM, 2016.
[27] Alix Munier, Maurice Queyranne, and Andreas S. Schulz. Approximation Bounds for a General Class of Precedence Constrained Parallel Machine Scheduling Problems, pages 367–382.
Springer Berlin Heidelberg, 1998.
[28] Cynthia Phillips, Clifford Stein, and Joel Wein. Minimizing average completion time in the
presence of release dates. Mathematical Programming, 82(1):199–223, Jun 1998.
[29] Maurice Queyranne and Andreas S. Schulz. Approximation bounds for a general class of
precedence constrained parallel machine scheduling problems. SIAM J. Comput., 35(5):1241–
1253, May 2006.
[30] Maurice Queyranne and Maxim Sviridenko. Approximation algorithms for shop scheduling
problems with minsum objective. Journal of Scheduling, 5(4):287–305, 2002.
[31] Andreas S. Schulz and Martin Skutella. Random-based scheduling: New approximations and
LP lower bounds. In Proceedings of the International Workshop on Randomization and Approximation Techniques in Computer Science, RANDOM ’97, pages 119–133. Springer-Verlag,
1997.
[32] Andreas S. Schulz and Martin Skutella. Scheduling unrelated machines by randomized rounding. SIAM J. Discret. Math., 15(4):450–469, April 2002.
[33] Petra Schuurman and Gerhard J. Woeginger. Polynomial time approximation algorithms for
machine scheduling: Ten open problems, 1999.
[34] Jay Sethuraman and Mark S. Squillante. Optimal scheduling of multiclass parallel machines.
In Proceedings of the Tenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA
’99, pages 963–964. Society for Industrial and Applied Mathematics, 1999.
[35] René A. Sitters. Approximation and online algorithms. chapter Minimizing Average Flow
Time on Unrelated Machines, pages 67–77. Springer-Verlag, 2009.
[36] Martin Skutella. Convex quadratic and semidefinite programming relaxations in scheduling.
J. ACM, 48(2):206–242, March 2001.

31

[37] Martin Skutella. A 2.542-approximation for precedence constrained single machine scheduling
with release dates and total weighted completion time objective. Operations Research Letters,
44(5):676 – 679, 2016.
[38] Martin Skutella and Gerhard J. Woeginger. A ptas for minimizing the weighted sum of job
completion times on parallel machines. In Proceedings of the Thirty-first Annual ACM Symposium on Theory of Computing, STOC ’99, pages 400–407. ACM, 1999.
[39] Ola Svensson. Conditional hardness of precedence constrained scheduling on identical machines. In Proceedings of the Forty-second ACM Symposium on Theory of Computing, STOC
’10, pages 745–754. ACM, 2010.
[40] Ola Svensson. Santa claus schedules jobs on unrelated machines. In Proceedings of the Fortythird Annual ACM Symposium on Theory of Computing, STOC ’11, pages 617–626. ACM,
2011.

32

