Task Scheduling in Networks.
Scheduling a set of tasks on a set of machines so as to yield an efficient schedule is a basic problem in computer science and operations research.  Most of the research on this problem incorporates the potentially unrealistic assumption that communication between the different machines is instantaneous.  In this paper we remove this assumption and study the problem of network scheduling, where each job originates at some node of a network, and in order to be processed at another node must take the time to travel through the network to that node.Our main contribution is to give approximation algorithms and hardness proofs for fully general forms of the fundamental problems in network scheduling.  We consider two basic scheduling objectives: minimizing the makespan and minimizing the average completion time.  For the makespan, we prove small constant factor hardness-to-approximate and approximation results.  For the average completion time, we give a log-squared approximation algorithm for the most general form of the problem.  The techniques used in this approximation are fairly general and have several other applications.  For example, we give the first nontrivial approximation algorithm to minimize the average weighted completion time of a set of jobs on related or  unrelated machines, with or without a network.
Introduction
Scheduling a set of tasks on a set of machines so as to yield an efficient schedule is a basic problem
in computer science and operations research. It is also a difficult problem and hence, much of the
research in this area has incorporated a number of potentially unrealistic assumptions. One such
assumption is that communication between the different machines is instantaneous. In many application
domains, however, such as a network of computers or a set of geographically-scattered repair
shops, decisions about when and where to move the tasks are a critical part of achieving efficient
resource allocation. In this paper we remove the assumption of instantaneous communication from
the traditional parallel machine models and study the problem of network scheduling, in which each
job originates at some node of a network, and in order to be processed at another node must take
the time to travel through the network to that node.
Until this work, network scheduling problems had either loose [2, 4] or no approximation algo-
rithms. Our main contribution is to give approximation algorithms and hardness proofs for fully
general forms of the fundamental problems in network scheduling. Our upper bounds are robust,
as they depend on general characteristics of the jobs and the underlying network. In particular,
our algorithmic techniques to optimize average completion time yield other results, such as the
first nontrivial approximation algorithms for a combinatorial scheduling question: minimization of
average weighted completion time on unrelated machines, and the first approximation algorithm for
a problem motivated by satellite communication systems. (To differentiate our network scheduling
models from the traditional parallel machine models, we will refer to the latter as combinatorial
scheduling models.)
Our results not only yield insight into the network scheduling problem, but also demonstrate
contrasts between the complexity of certain combinatorial scheduling problems and their network
variants, shedding light on their relative difficulty.
An instance of the network scheduling problem consists of a network
non-negative edge lengths '; we define ' max to be the maximum edge length. At each
vertex v i in the network is a machine M i . We are also given a set of n jobs, J Each job J j
originates, at time 0, on a particular origin machine M
and has a processing requirement
define p max to be max 1-j-n p j . Each job must be processed on one machine without interruption.
Job J j is not available to be processed on a machine M 0 until time d(M
the length of the shortest path in G between M i and M k . We assume that the M i are either identical
on every machine) or that they are unrelated (J j takes time p ij on M i , and the
may all be different). In the unrelated machines setting we define p . The
identical and unrelated machine models are fundamental in traditional parallel machine scheduling
and are relatively well understood [3, 10, 11, 12, 15, 17, 25]. Unless otherwise specified, in this
paper the machines in the network are assumed to be identical.
An alternative view of the network scheduling model is that each job J j has a release date,
a time before which it is unavailable for processing. In previous work on traditional scheduling
models a job's release date was defined to be the same on all machines. The network model can
be characterized by allowing a job J j 's release date to be different on different machines; J j 's
release date on M k is d(M
One can generalize further and consider problems in which a
job's release date can be chosen arbitrarily for all m machines, and need not reflect any network
structure. Almost all of our upper bounds apply in this more general setting, whereas our lower
bounds all apply when the release dates have network structure.
We study algorithms to minimize the two most basic objective functions. One is the makespan
or maximum completion time of the schedule; that is, we would like all jobs to finish by the earliest
time possible. The second is the average completion time. We define an ff-approximation algorithm
to be a polynomial-time algorithm that gives a solution of cost no more than ff times optimal.
1.1 Previous Work
The problem of network scheduling has received some attention, mostly in the distributed setting.
Deng et. al. [4] considered a number of variants of the problem. In the special case in which each
edge in the network is of unit length, all job processing times are the same, and the machines are
identical, they showed that the off-line problem is in P . It is not hard to see that the problem is
NP-Complete when jobs are allowed to be of different sizes; they give an off-line O(log(m' max ))-
approximation algorithm for this. They also give a number of results for the distributed version of
the problem when the network topology is completely connected, a ring or a tree.
Awerbuch, Kutten and Peleg [2] considered the distributed version of the problem under a novel
notion of on-line performance, which subsumes the minimization of both average and maximum
completion time. They give distributed algorithms with polylogarithmic performance guarantees
in general networks. They also characterize the performance of feedback-based approaches. In
addition they derived off-line approximation results similar to those of Deng et. al [2, 20]. Alon
et. al. [1] proved an
m) lower bound on the performance of any distributed scheduler that
is trying to minimize schedule length. Fizzano et. al. [5] give a distributed 4:3-approximation
algorithm for schedule length in the special case in which the network is a ring.
Our work differs from these papers by focusing on the centralized off-line problem and by giving
approximations of higher quality. In addition, our approximation algorithms work in a more general
setting, that of unrelated machines.
1.2 Summary of Results
We first focus on the objective of minimizing the makespan, and give a 2-approximation algorithm
for scheduling jobs on networks of unrelated machines; the algorithm gives the same performance
guarantee for identical machines as a special case. The 2-approximation algorithm matches the best
known approximation algorithm for scheduling unrelated machines with no underlying network [17].
Thus it is natural to ask whether the addition of a network to a combinatorial scheduling problem
actually makes the problem any harder. We resolve this question by proving that the introduction of
the network to the problem of scheduling identical machines yields a qualitatively harder problem.
We show that for the network scheduling problem, no polynomial-time algorithm can do better
than a factor of 4
3 times optimal unless even in a network in which all edges have length
one. Comparing this with the polynomial approximation scheme of Hochbaum and Shmoys [10] for
parallel machine scheduling, we see that the addition of a network does indeed make the problem
harder.
Although the 2-approximation algorithm runs in polynomial time, it may be rather slow [21]. We
thus explore whether a simpler strategy might also yield good approximations. A natural approach
to minimizing the makespan is to construct schedules with no unforced idle time. Such strategies
provide schedules of length a small constant factor times optimal, at minimal computational cost,
for a variety of scheduling problems [6, 7, 15, 24]. We call such schedules busy schedules, and show
that for the network scheduling problem their quality degrades significantly; they can be as much
as
an\Omega
log log m
factor longer than the optimal schedule.
This is in striking contrast to the combinatorial model (for which Graham showed that a busy
strategy yields a 2-approximation algorithm [6]). In fact, even when release dates are introduced
into the identical machine scheduling problem, if each job's release date is the same on all machines,
busy strategies still give a
)-approximation guarantee [8, 9]. Our result shows that when the
Combinatorial Network
min. makespan, identical machines ff
min. makespan, identical machines,
log log m
log log m
Busy schedules
min. makespan, unrelated machines 3=2
min. avg. completion time
unrelated machines
n)
min. avg. wtd. completion time
unrelated machines, release dates ff - O(log 2
n)

Figure

1: Summary of main algorithms and hardness results. The notation x ! ff - y means that
we can approximate the problem within a factor of y, but unless
the problem within a factor of x. Unreferenced results are new results found in this paper.
release dates of the jobs are allowed to be different on different machines busy scheduling degrades
significantly as a scheduling strategy. This provides further evidence that the introduction of a
network makes scheduling problems qualitatively harder. However, busy schedules are of some
quality; we show that they are of length a factor of O
log log m
longer than optimal. This analysis
gives a better bound than the (O(log m' max )) bound of previously known approximation algorithms
for identical machines in a network [2, 4, 20].
We then turn to the NP-hard problem of the minimization of average completion time. Our
major result for this optimality criterion is a O(log 2 n)-approximation algorithm in the general
setting of unrelated machines. It formulates the problem as a hypergraph matching integer program
and then approximately solves a relaxed version of the integer program. We can then find an integral
solution to this relaxation, employing as a subroutine the techniques of Plotkin, Shmoys and Tardos
[21]. In combinatorial scheduling, a schedule with minimum average completion time can be found
in polynomial time, even if the machines are unrelated.
The techniques for the average completion time algorithm are fairly general, and yield an
O(log 2 n)-approximation for minimizing the average weighted completion time. A special case of
this result is an O(log 2 n)-approximation algorithm for the NP-hard problem of minimizing average
weighted completion time for unrelated machines with no network; no previous approximation
algorithms were known, even in the special case for which the machines are just of different speeds [3,
15]. Another special case is the first O(log 2 n)-approximation algorithm for minimizing the average
completion time of jobs with release dates on unrelated machines. No previous approximation
algorithms were known, even for the special case of just one machine [15]. The technique can also
be used to give an approximation algorithm for a problem motivated by satellite communication
systems [18, 26].
We also give a number of other results, including polynomial-time algorithms for several special
cases of the above-mentioned problems and a 5
-approximation for a variant of network scheduling
in which each job has not only an origin, but also a destination.
A summary of some of these upper bounds and hardness results appears in Figure 1.
A line of research which is quite different from ours, yet still has some similarity in spirit, was
started by Papadimitriou and Yannakakis [19]. They modeled communication issues in parallel
machine scheduling by abstracting away from particular networks and rather describing the communication
time between any two processors by one network-dependent constant. They considered
the scheduling of precedence-constrained jobs on an infinite number of identical machines in this
model; the issues involved and the sorts of theorems proved are quite different from our results.
Although all of our algorithms are polynomial-time algorithms, they tend to be rather inefficient.
Most rely on the work of [21] as a subroutine. As a result we will not discuss running times explicitly
for the rest of the paper.
Makespan
In this section we study the problem of minimizing the makespan for the network scheduling
problem. We first give an algorithm that comes within a factor of 2 of optimal. We then show that
this is nearly the best we can hope for, as it is NP-hard to approximate the minimum makespan
within a factor of better than 4
3 for identical machines in a network. This hardness result contrasts
sharply with the combinatorial scenario, in which there is a polynomial approximation scheme [10].
The 2-approximation algorithm is computationally intensive, so we consider simple strategies that
typically work well in parallel machine scheduling. In another sharp contrast to parallel machine
scheduling, we show that the performance of such strategies degrades significantly in the network
setting; we prove
an\Omega
log log m
lower bound on the performance of any such algorithm. We also
show that greedy algorithms do have some performance guarantee, namely O( log m
log log m ). Finally we
consider a variant of the problem in which each job has not only an origin, but also a destination,
and give a 5
-approximation algorithm.
2.1 A 2-Approximation Algorithm For Makespan
In this section we describe a 2-approximation algorithm to minimize the makespan of a set of jobs
scheduled on a network of unrelated machines; the same bound for identical machines follows as a
special case. Let U be an instance of the unrelated network scheduling problem with
optimal schedule length D. Assuming that we know D, we will show how to construct a schedule
of length at most 2D. This can be converted, via binary search, into a 2-approximation algorithm
for the problem in which we are not given D [10].
In the optimal schedule of length D, we know that the sum of the time each job spends travelling
and being processed is bounded above by D. Thus, job J j may run on machine M i in the optimal
schedule only if:
In other words, the length of an optimal schedule is not altered if we allow job J j to run only on
the machines for which (1) is satisfied. Formally, for a given job J j , we will denote by Q(J j ) the
set of machines that satisfy (1). If we restrict each J j to only run on the machines in Q(J j ), the
length of the optimal schedule remains unchanged.
combinatorial unrelated machines scheduling problem (Z) as follows:
If the optimal schedule for the unrelated network scheduling problem has length D, then the
optimal solution to the unrelated parallel machine scheduling problem (2) is at most D. We will
use the 2-approximation algorithm of Lenstra, Shmoys and Tardos [17] to assign jobs to machines.
The following theorem is easily inferred from [17].
Theorem 2.1 (Lenstra, Shmoys, Tardos [17]) Let Z be an unrelated parallel machine scheduling
problem with optimal schedule of length D. Then there exists a polynomial-time algorithm that
finds a schedule S of length 2D. Further, S has the property that no job starts after time D.
Theorem 2.2 There exists a polynomial-time 2-approximation algorithm to minimize makespan
in the unrelated network scheduling problem.
Proof: Given an instance of the unrelated network scheduling problem, with shortest schedule
of length D, form the unrelated parallel machine scheduling problem Z defined by (2) and use
the algorithm of [17] to produce a schedule S of length 2D. This schedule does not immediately
correspond to a network schedule because some jobs may have been scheduled to run before their
release dates. However, if we allocate D units of time for sending all jobs to the machines on which
they run, and then allocate 2D units of time to run schedule S, we immediately get a schedule of
length 3D for the network problem.
By being more careful, we can create a schedule of length 2D for the network problem. In
schedule S, each machine M i is assigned a set of jobs S i . Let jS i j be the sum of the processing
times of the jobs in S i and let S max
i be the job in S i with largest processing time on machine
call its processing time p max
. By Theorem 2.1 and the fact that the last job run on machine i is
no longer than the longest job run, we know that jS
i denote the set of jobs
i . We form the schedule for each machine i by running job S max
i at time
by the jobs in S 0
In this schedule the jobs assigned to any machine clearly finish by time 2D; it remains to be
shown that all jobs can be routed to the proper machines by the time they need to run there. Job
must start at time
conditions (1) and (2) guarantee that it arrives in time. The
remaining jobs need only arrive by time D; conditions (1) and (2) guarantee this as well. Thus we
have produced a valid schedule of length 2D.
Observe that this approach is fairly general and can be applied to any problem that can be
characterized by a condition such as (2). Consider, for example the following very general problem,
which we call generalized network scheduling with costs. In addition to the usual unrelated network
scheduling problem, the time that it takes for job J j to travel over an edge is dependent not only
on the endpoints of the edge, but also on the job. Further, there is a cost c ij associated with
processing job J j on machine M i . Given a schedule in which job J j runs on machine M -(j) , the
cost of a schedule is
Given any target cost C, we define s(C) to be the minimum length
schedule of cost at most C.
Theorem 2.3 Given a target cost C, we can, in polynomial time, find a schedule for the generalized
network scheduling problem with makespan at most 2s(C) and of cost C if a schedule of cost C exists.
Proof: We use similar techniques to those used for Theorem 2.2. We first modify Condition (1)
so that d(\Delta; \Delta) depends on the job as well. We then use a generalization of the algorithm of Lenstra,
Shmoys and Tardos for unrelated machine scheduling, due to Shmoys and Tardos [25] which, given
a target cost C finds a schedule of cost C and length at most twice that of the shortest schedule of
cost C. The schedule returned also has the property that no job starts after time D, so the proof
of Theorem 2.2 goes through if we use this algorithm in place of the algorithm of [17].
2.2 Nonapproximability
Theorem 2.4 It is NP-complete to determine if an instance of the identical network scheduling
problem has a schedule of length 3, even in a network with '
Proof: See Appendix.
Corollary 2.5 There does not exist an ff-approximation algorithm for the network scheduling problem
with even in a network with '
Proof: Any algorithm with ff ! 4=3 would have to give an exact answer for a problem with a
schedule of length 3 since an approximation of 4 would have too high a relative error.
It is not hard to see, via matching techniques, that it is polynomial-time decidable whether there
is a schedule of length 2. We can show that this is not the case when the machines in the network
can be unrelated. Lenstra, Shmoys and Tardos proved that it is NP-Complete to determine if
there is a schedule of length 2 in the traditional combinatorial unrelated machine model [17]. If we
allow multiple machines at one node, their proof proves Theorem 2.6. If no zero length edges are
allowed, i.e. each machine is forced to be at a different network node, this proof does not work,
but we can give a different proof of hardness, which we do not include in this paper.
Theorem 2.6 There does not exist an ff-approximation algorithm for the unrelated network scheduling
problem with ff ! 3=2 unless even in a network with '
2.3 Naive Strategies
The algorithms in Section 2.1 give reasonably tight bounds on the approximation of the schedule
length. Although these algorithms run in polynomial time, they may be rather slow [21]. We thus
explore whether a simpler strategy might also yield good approximations.
A natural candidate is a busy strategy: construct a busy schedule, in which, at any time t there
is no idle machine M i and idle job J j so that job J j can be started on M i at time t. Busy strategies
and their variants have been analyzed in a large number of scheduling problems (see [15]) and have
been quite effective in many of them. For combinatorial identical machine scheduling, Graham
showed that such strategies yield a
In this section we analyze
the effectiveness of busy schedules for identical machine network scheduling. Part of the interest of
this analysis lies in what it reveals about the relative hardness of scheduling with and without an
underlying network; namely, the introduction of an underlying network can make simple strategies
much less effective for the problem.
2.3.1 A Lower Bound
We construct a family of instances of the network scheduling problem, and demonstrate, for each
instance, a busy schedule which is \Omega\Gamma
log log m ) longer than the shortest schedule for that instance.
The network E) consists of ' levels of nodes, with level nodes.
Each node in level is connected to every node in level by an edge of length
1. Each machine in levels ae jobs of size 1 at time 0. The machines in level '
initially receive no jobs. The optimal schedule length for this instance is 2 and is achieved by each
machine in level taking exactly one job from level i \Gamma 1. We call this instance I. See

Figure

2.
The main idea of the lower bound is to construct a busy schedule in which machine M always
processes a job which originated on M , if such a job is available. This greediness "prevents" the
scheduler from making the much larger assignment of jobs to machines at time 2 in which each job
is assigned to a machine one level away.
To construct a busy schedule S, we use algorithm B, which in Step t constructs the subschedule
of S at time t.
Step t:
Phase 1: Each machine M processes one job that originated at M , if any such jobs remain. We
call such jobs local to machine M .
r
r
r
r
r
Level 1 Level 2 . Level L

Figure

2: Lower Bound Instance for Theorem 2.8. Circles represent processors, and the numbers
inside the circles are the number of jobs which originate at that processor at time 0. Levels i and
are completely connected to each other. The optimal schedule is of length 2 and is achieved
by shifting each job to a unique processor one level to its right.
Phase 2: Consider the bipartite graph G  has one vertex representing each
job that is unprocessed after Phase 1 of time t, Y contains one vertex representing each machine
which has not had a job assigned to it in Phase 1 of Step t, and (x; y) 2 A if and only if job x
originated a distance no more than t \Gamma 1 from machine y. Complete the construction of S at time t
by processing jobs on machines based on any maximum matching in G   . It is clear that S is busy.
When we apply algorithm B to instance I, the behavior follows a well-defined pattern. In Phase
2 of Step 2, all unprocessed jobs that originated in level are processed by distinct processors
in level '. During Phase 2 of Step 3, all unprocessed jobs that originated in levels are
processed by machines in levels This continues, so that at Step i an additional (i \Gamma 1)
levels pass their jobs to higher levels and all these jobs are processed. This continues until either
level 1 passes its jobs, or processes its own jobs. We characterize the behavior of the algorithm
more formally in the following lemma.
Lemma 2.7 Let j(i; t) be the number of local jobs of processor i still unprocessed after Phase 2 of
Step t and let lev(i) be the level number of processor i. Then for all times t - 2, if ae - t, then
Proof: We prove the lemma by induction on t. During Phase 2 of Step 2, the only edges in the
graph G   connect levels ' and ' \Gamma 1. There are ae '\Gamma1 nodes in level ' and ae '\Gamma2 (ae \Gamma 1) remaining
jobs local to machines in level ' \Gamma 1, so the matching assigns all the unprocessed jobs in level
to level '. Machines in level 1 to process local jobs during Phase 1. As a result, all the
neighbors of machines in levels 1 to are busy in Phase 1 and cannot process jobs local to these
machines during Phase 2. The number of local jobs on these machines, therefore, decreases only
by 1. Thus the base case holds.
Assume the lemma holds for all
greater than b as well. We now show that j(i; t 0
level b+x has ae b+x\Gamma1 processors. Level
has at most ae \Delta ae b+x\Gamma(t 0 local jobs remaining. If t 0 - 2 then there are enough
machines on level b + x to process all the remaining jobs local to level b
another of the highest-numbered levels have their local jobs completed during time t 0 . Thus
at time t 0 we have
Since we assumed sufficiently large initial workloads on all processors on levels
by the induction hypothesis, for all machines in levels less than
distance them have local jobs remaining after time will be assigned a local job
during Phase 1 of Step t 0 . Therefore all machines i such that lev(i)
any jobs to higher levels and j(i; t 0
Depending on the relative values of ae and ', either the machine in level 1 processes all of the
jobs which originated on it, or some of those jobs are processed by machines in higher-numbered
levels. Balancing these two cases we get the following theorem:
Theorem 2.8 For the family of instances of the identical machine network scheduling problem
defined above, there exist busy schedules of length a
log log m ) longer than optimal.
Proof: The first case in (3) will apply to level 1 when 1 This inequality does
not hold when
2', but it does hold when
2' then the schedule
length is
2', while if ae !
2' then the jobs in level 1 will be totally processed in their level,
which takes ae time. Therefore the makespan of S is at most min(
ae). Given that the total
number of machines is calculation reveals that min(c
'; ae) is maximized at
log log m ). Thus S is a busy schedule of length '(
log log m ) longer than optimal.
Note that this example shows that several natural variants of busy strategies, such as scheduling
a job on the machine on which it will finish first, or scheduling a job on the closest available
processor, also perform poorly.
2.3.2 An Upper Bound
In contrast to the lower bound of the previous subsection, we can prove that busy schedules are
of some quality. Given an instance I of the network scheduling problem, we define C
(I) to be
the length of a shortest schedule for I and C A
(I) to be the length of the schedule produced by
algorithm A; when it causes no confusion we will drop the I and use the notation C
Definition 2.9 Consider a busy schedule S for an instance I of the identical machines network
scheduling problem. Let p j (t) be the number of units of job J j remaining to be processed in schedule
S at time t, and W
be the total work remaining to be processed in schedule S at time
t.
Lemma 2.10 W iC
Proof: We partition schedule S into consecutive blocks
what happens in each block of schedule S to an optimal schedule S   of length C
for instance I.
Consider a job J j that was not started by time C
in schedule S, and let M j be the machine
on which job J j is processed in schedule S   . This means that in block B 1 machine M j is busy
for units of time during job J j 's slot in schedule S   - the period of time during which job J j
was processed on machine M j in schedule S   . Hence for every job J j that is not started in block
there is an equal amount of unique work which we can identify that is processed in block B 1 ,
implying that WC   max
Successive applications of this argument yields W iC
which proves the lemma for 2.
To obtain the stronger bound W iC
we increase the amount of processed work
which we identify with each unstarted job. Choose i - 3 and consider a job J j which is unstarted
in schedule S at the start of block B i+1 , namely at time iC
. Assume for the sake of simplicity
that in every block B k of schedule S, only one job is processed in job J j 's slot (the time during
which job J j would be processed if block B k was schedule S   ). Assume also that this job is exactly
of the same size as job J multiple jobs are processed the argument is essentially the same. Let
J r be the job that took job J j 's slot in block B r , for r - 2. We will show that J j could have
been processed in J r 's slot in block B i for all 2. Figure 2.3.2 illustrates the network
structure used in this argument.
Assume that job J j originated on machine M
, and that job J r originated on machine M or , and
that job J j was processed on machine M j in schedule S   . Then d(M
since job J j
was processed on machine M j in schedule S   , and d(M or ; M j ) - rC
since job J r was processed
in job J j 's slot in block B r . Thus d(M
consequently J j could have run
in job J r 's slot in any of blocks B We focus on block B i . Since J j was not processed in
and schedule S is busy, some job must have been processed during job J r 's slot in block
We identify this work with job J note that no work is ever identified with
more than one job.
When we consider the (i\Gamma2) different jobs which were processed in J j 's slot in blocks
and consider the jobs that were processed in their slots in B i , we see that with each job J j unstarted
at time iC
, we can uniquely identify units of work that was processed in block
O
<_
<_
O r
r
<_

Figure

3: If J r takes J j 's slot in B r , then the machine on which J j originates, M
, is at most a
distance of (r
r , the machine on which J r runs in S   . Thus J j could have been
run in J r 's slot in block i,
. If all these slots were not full in block B i , then job J j would have been started in one of them.
Including the work processed during job J j 's slot in block B i , we obtain
Corollary 2.11 During time iC
max at most m=(2i!) machines are completely busy.
Proof: We have W 0 - mC
. Therefore, by Lemma 2.10, we have W iC
machine that is completely busy from time iC
does C
work during that
time and therefore at most m=(2i!) machines can be completely busy.
To get a stopping point for the recurrence, we require the following lemma:
Lemma 2.12 In any busy schedule, if at time t all remaining unprocessed jobs originated on the
same machine, the schedule is no longer than t
Let M be the one machine with remaining local jobs. Let W
be the amount of work
from machine M that is done by machine M i in the optimal schedule. Clearly
equals the
amount of work that originated on machine M . Because there is no work left that originated on
machines other than M , each machine M i can process at least W
work from machine M in the
next C
steps. If after C
steps, all the work originating on machine M is done, then
we have finished. Otherwise, some machine M i processed less than W
work during this time,
which means there was no more work for it to take. Therefore after C
steps all the jobs that
originated on machine M have started. Because no job is longer than C
suffices to finish all the jobs that have started.
We are now ready to prove the upper bound:
Theorem 2.13 Let A be any busy scheduling algorithm and I an instance of the identical machine
network scheduling problem. Then C A
log log m C
Proof: If a machine ever falls idle, all of its local work must be started. Otherwise it would process
remaining local work. Thus by Corollary 2.11, in O( lg m
time, the number of processors
with local work remaining is reduced to 1. By Lemma 2.12, when the number of processors with
remaining local work is down to one, a constant number of extra blocks suffice to finish.
2.4 Scheduling with Origins and Destinations
In this subsection we consider a variant of the (unrelated machine) network scheduling problem in
which each job, after being processed, has a destination machine to which it must travel. Specif-
ically, in addition to having an origin machine M
, job J j also has a terminating machine M t j
begins at machine M
, travels distance d(M
) to machine M d j
, the machine it gets
processed on, and then proceeds to travel for d(M d j
units of time to machine M t j
. We call
this problem the point-to-point scheduling problem.
Theorem 2.14 There exists a polynomial-time 5
-approximation algorithm to minimize makespan
in the point-to-point scheduling problem.
Proof: We construct an unrelated machines scheduling problem as in the proof of Theorem 2.2.
In this setting the condition on when a job J j can run on machine M i depends on the time for J j
to get to M i , the time to be processed there, and the time to proceed to the destination machine.
Thus a characterization of when job J j is able to run on machine M i in the optimal schedule is
Now, for a given job J j , we define Q(J j ) to be the set of machines that satisfy (4). We can then
form a combinatorial unrelated machines scheduling problem as follows:
We then approximately solve this problem using [17] to obtain an assignment of jobs to machines.
Pick any machine M i and let J i be the set of jobs assigned to machine M i . By Theorem 2.1 we
know that the sum of the processing times of all of the jobs in J i except the longest is at most
D. We partition the set of jobs J i into three groups, and place each job into the lowest numbered
group which is appropriate:
1. J 0
i contains the job in J i with the longest processing time,
2. J 1
contains jobs for which d(M
3. J 2
contains jobs for which d(M
i ) be the sum of the processing times of the jobs in group J k
2. As noted above,
We will always schedule J 1
i in a block of D consecutive time steps, which
we call B. The first p(J 1
steps will be taken up by jobs in J 1
i while the last p(J 2
steps will be taken up by jobs in J 2
. Note that there may be idle time in the interior of the block.
We consider two possible scheduling strategies based on the relative sizes of p(J 1
Case 1:(p(J 1
In this case we first run the long job in J 0
by condition (4) it finishes by
time D. We then run block B from time D to 2D. Since p(J 1
the jobs in J 1
all finish by
time 3D=2 and by condition (4) reach their destinations by time 5D=2. By the definition of J 2
for any job J
i is scheduled to complete processing
by time 2D, it will arrive at its destination by time 5D=2.
Case 2: (p(J 1
first run block B from time D=2 to 3D=2. We then start the long job
in J 0
i at time 3D=2; by condition (4) it arrives at its destination by time 5D=2. Since p(J 2
machine M i need not start processing any job in J 2
hence we are guaranteed
that they have arrived at machine M i by that time. By definition of J 1
i all of its jobs are available
by time D=2; it is straightforward from condition (4) that all jobs arrive at their destinations by
time 5D=2.
We can also show that the analysis of this algorithm is tight, for algorithms in which we assign
jobs to processors using the linear program defined in [17] using the processing times specified by
Equation 5. Let D be the length of the optimal schedule. Then we can construct instances for
which any such schedule S has length at least 5=2D \Gamma 1. Consider a set of k+1 jobs and a particular
machine M i . We specify the largest of these jobs to have size D and to have M i as both its origin
and destination machine. We specify that each of the other k jobs are of size D=k and have distance
to both their origin and destination machines. The combinatorial unrelated
machines algorithm may certainly assign all of these jobs to M i , but it is clear that any schedule
adopted for this machine will have competion time at least ( 5
2k )D.
3 Average Completion Time
3.1 Background
We turn now to the network scheduling problem in which the objective is to minimize the average
completion time. Given a schedule S, let C S
j be the time that job J j finishes running in S. The
average completion time of S is 1
whose minimization is equivalent to the minimization of
. Throughout this section we assume without loss of generality that n - m.
We have noted in Section 1 that our network scheduling model can be characterized by a set of
and a set of release dates r ij , where J j is not available on m i until time r ij . We noted
that this is a generalization of the traditional notion of release dates, in which r
will refer to the latter as traditional release dates; the unmodified phrase release date will refer to
the general r ij .
The minimization of average completion time when the jobs have no release dates is polynomial-time
solvable [3, 12], even on unrelated machines. The solution is based on a bipartite matching
formulation, in which one side of the bipartition has jobs and the other side (machine, position)
pairs. Matching J j to (m corresponds to scheduling J j in the kth-from-last position on m i ; this
edge is weighted by kp ij , which is J j 's contribution to the average completion time if J j is kth from
last.
When release dates are incorporated into the scheduling model, it seems difficult to generalize
this formulation. Clearly it can not be generalized precisely for arbitrary release dates, since even
the one machine version of the problem of minimizing average completion time of jobs with release
dates is strongly NP-hard [3]. Intuitively, even the approximate generalization of the formulation
seems difficult, since if all jobs are not available at time 0, the ability of J j to occupy position
on m i is dependent on which jobs precede it on m i and when. Release dates associated with
a network structure do not contain traditional release dates as a subclass even for one machine,
so the NP-completeness of the network scheduling problem does not follow immediately from the
combinatorial hardness results; however, not surprisingly, minimizing average completion time for
a network scheduling problem is NP-complete.
Theorem 3.1 The network scheduling problem with the objective of minimum average completion
time is NP-complete even if all the machines are identical and all edge lengths are 1.
Proof: See Appendix.
In what follows we will develop an approximation algorithm for the most general form of this
problem. We will follow the basic idea of utilizing a bipartite matching formulation; however we
will need to explicitly incorporate time into the formulation. In addition, for the rest of the section
we will consider a more general optimality criterion: average weighted completion time. With each
J j we associate a weight w j , and the goal is to minimize
. All of our algorithms handle
this more general case; in addition they allow the nm release dates r ij to be arbitrary and not
necessarily derived from the network structure.
3.2 Unit-Size Jobs
We consider first the special case of unit-size jobs.
Theorem 3.2 There exists a polynomial-time algorithm to schedule unit-size jobs on a network of
identical machines with the objective of minimizing the average weighted completion time.
Proof: We reduce the problem to minimum-weight bipartite matching. One side of the bipartition
will have a node for each job J j , 1 - j - n, and the other side will have a node [m
to be described below. An edge included if J j
is available on m i at time t, and the inclusion of that edge in the matching will represent the
scheduling of J j on m i from time t to t + 1. Release dates are included in the model by excluding
an edge will not be available on m i by time t.
To determine the necessary sets T i , we observe that there is no advantage in unforced idle time.
Since each job is only one unit long, there is no reason to make it wait for a job of higher weight
that is about to be released. It is clear, therefore, that setting T would
suffice, since no job would need to be scheduled more than n time later than its release date. This
this can be reduced to O(n), but we omit the details for the sake of brevity.
By excluding edges which do not give job J j enough time to travel between the machine on which
runs and the destination machine M d j
, we can prove a similar theorem for the point-to-point
scheduling problem, defined in Section 2.4.
Theorem 3.3 There exists a polynomial-time algorithm to solve the point-to-point scheduling problem
with the objective of minimizing the average weighted completion time of unit-size jobs.
3.3 Polynomial-Size Jobs
We now turn to the more difficult setting of jobs of different sizes and unrelated machines. The
minimization of average weighted completion time in this setting is strongly NP-hard, as are
many special cases. For example, the minimization of average completion time of jobs with release
dates on one machine is strongly NP-hard [16]; no approximation algorithms were known for this
special case, to say nothing of parallel identical or unrelated machines, or weighted completion
times. If there are no release dates, namely all jobs are available at time 0, then minimization of
average weighted completion time is NP-hard for parallel identical machines. A small constant
factor approximation algorithm was known for this problem [14], but no approximation algorithms
were known for the more general cases of machines of different speeds or unrelated machines. We
introduce techniques which yield the first approximation algorithms for several other problems as
well, which we discuss in Section 3.5.
Our approximation algorithm for minimum average completion time begins by formulating the
scheduling problem as a hypergraph matching problem. The set of vertices will be the union of two
sets, J and M , and the set of hyperedges will be denoted by F . J will contain n vertices J j , one for
each job, and M will contain mT vertices, where T is an upper bound on the number of time units
that will be needed to schedule this instance. The time units will range over
g. M will have a node for each (machine, time) pair; we will denote the node that
corresponds to machine M i at time t as [m i ; t]. A hyperedge e 2 F represents scheduling a job J j
on machine M i from time t 1 to t 2 by including nodes J The cost
of an edge e, denoted by c e , will be the weighted completion time of job J j if it is scheduled in the
manner represented by e. There will be one edge in the hypergraph for each feasible scheduling of
a job on a machine; we exclude edges that would violate the release date constraints.
The problem of finding the minimum cost matching in the hypergraph can be phrased as the
following integer program I. We use decision variable x e 2 f0; 1g to denote whether hyperedge e
is in the matching.
minimize
e
subject to X
(i;t)2e
Two considerations suggest that this formulation might not be useful. The formulation is not
of polynomial size in the input size, and in addition the following theorem suggests that calculating
approximate solutions for this integer program may be difficult.
Theorem 3.4 Consider an integer program in the form I which is derived from an instance of the
network scheduling problem with identical machines, with the c e allowed to be arbitrary. Then there
exists no polynomial-time algorithm A to approximate I within any factor unless
Proof: For an arbitrary instance of the network scheduling problem construct the hypergraph
matching problem in which an edge has weight W ?? n if it corresponds to a job being completed
later than time 3 and give all other edges weight 1. If there is a schedule of length 3 then the
minimum weight hypergraph matching is of weight n; otherwise the weight is at least W ; therefore
an ff-approximation algorithm with ff ! W
would give a polynomial-time algorithm to decide if
there was a schedule of length 3 for the network scheduling problem, which by Theorem 2.4 would
imply
In order to overcome this obstacle, we need to seek a different kind of approximation to the
hypergraph matching problem. Typically, an approximate solution is a feasible solution, i.e. one
that satisfies all the constraints, but whose objective value is not the best possible. We will look for
a different type of solution, one that satisfies a relaxed set of constraints. We will then show how to
turn a solution that satisfies the relaxed set of constraints into a schedule for the network scheduling
problem, while only introducing a bounded amount of error into the quality of the approximation.
We will assume for now that p max - n 3 . This implies that the size of program I is polynomial
in the input size. We will later show how to dispense with the assumption on the size of p max via
a number of rounding and scaling techniques.
We begin by turning the objective function of I into a constraint. We will then use the standard
technique of applying bisection search to the value of the objective function. Hence for the
remainder of this section we will assume that C, the optimal value to integer program I, is given.
We can now construct approximate solutions to the following integer linear program (J
(i;t)2e
e
This integer program is a packing integer program, and as has been shown by Raghavan [22],
Raghavan and Thompson [23] and Plotkin, Shmoys and Tardos [21], it is possible to find provably
good approximate solutions in polynomial time. We briefly review the approach of [21], which
yields the best running times.
Plotkin, Shmoys and Tardos [21] consider the following general problem.
The Packing Problem: 9?x 2 P such that Ax - b, where A is an m \Theta n nonnegative matrix,
b ? 0, and P is a convex set in the positive orthant of R n .
They demonstrate fast algorithms that yield approximately optimal integral solutions to this
linear program. All of their algorithms require a fast subroutine to solve the following problem.
The Separation Problem: Given an m-dimensional vector y - 0, find ~ x 2 P such that
A.
The subroutine to solve this problem will be called the separating subroutine.
An approximate solution to the packing problem is found by considering the relaxed problem
and approximating the minimum - such that this is true. Here the value - characterizes the "slack"
in the inequality constraints, and the goal is to minimize this slack.
Our integer program can be easily put in the form of a packing problem; the equality constraints
(7) define the polytope P and the inequality constraints (8,9) make up Ax - b. The quality of the
integral solutions obtained depends on the width of P relative to Ax - b, which is defined by
a
It also depends on d, where d is the smallest integer such that any solution returned by the
separating routine is guaranteed to be an integral multiple of 1
d .
Applying equation (10) to compute ae for polytope P (defined by (7)) yields a value that is at
least n, as we can create matchings (feasible schedules) whose cost (average completion time) is
much greater than C, the optimal average completion time.
In fact, many other packing integer programs considered in [21] also, when first formulated,
have large width. In order to overcome this obstacle, [21] gave several techniques to reduce the
width of integer linear programs. We discuss and then use one such technique here, namely that of
decomposing a polytope into n lower-dimensional polytopes, each of which has smaller width. The
intuition is that all the non-zero variables in each equation of the form (7) are associated with only
one particular job. Thus we will be able to decompose the polytope into n polytopes, one for each
job. We will then be able to optimize individually over each polytope and use only the inequality
constraints (8) and (9) to describe the relationships between different jobs.
We now procede in more detail. We say that a polytope P can be decomposed into a product
of n polytopes the coordinates of each vector x can be partitioned into
our polytope can be decomposed
in this way, and we can solve the separation problem for each polytope P l , then we can apply a
theorem of [21] to give an approximately optimal solution in polynomial time. In particular, let -
be the optimum value of J . The following theorem is a specialization of Theorem 2.11 in [21] to
our problem, and describes the quality of integral solutions that can be obtained for such integer
programs.
Theorem 3.5 [21] Let ae l be the width of P l and -
. Let fl be the number of constraints
in Ax - b, and let - log fl). Given a polynomial-time separating subroutine for
each of the P l , there exists a polynomial-time algorithm for J which gives an integral solution with
We will now show how to reformulate J so that we will be able to apply this theorem. Polytope
(from can indeed be decomposed into n different polytopes:
to those equality constraints which include only J j . In order to keep the width of the P j
small, we also include into the definition of P j the constraint x for each edge e which includes
J j and has c e ? C; this does not increase the optimal value of the integer program. We integrate
each of these new constraints into the appropriate polytope P j , and decompose
consists of those components of x which represent edges that include J j . In other words,
P l is defined by
J l 2e
e:
This yields the following relaxation L:
subject to
(i;t)2e
e
To apply Theorem 3.5 we must (1) demonstrate a polynomial-time separating subroutine and
ae, d and fl. The decomposition of P into n separate polytopes makes this task much
easier. The separating subroutine must find x l 2 P l that minimizes cx l ; however, since the vector
that is 1 in the eth component and 0 in all other components is in P l for all e such that J l 2 e
and c e - C, the separating routine reduces merely to finding the minimum component c e 0 of c and
returning the vector with a 1 in position e 0 and 0 everywhere else. An immediate consequence of
this is that d = 1. Recall as well that the assumption that p max - n 3 implies that fl is upper
bounded by a polynomial in n.
It is not hard to see that -
ae is 1; HERE IT IS. therefore
(-ae=d) log fl(-ae=d) log(flnd))
By employing binary search over C and the knowledge that the optimal solution has
can obtain an invalid "schedule" in which as many as O(-) jobs are scheduled at one time. If p max
is polynomial in n and m then we have a polynomial-time algorithm; therefore we have proven the
following lemma.
Lemma 3.6 Let C   be the solution to the integer program I and assume that jM j is bounded by
mn 4 . There exists a polynomial-time algorithm that produces a solution x   such that
j2e
x
(i;t)2e
x
e
x
x
This relaxed solution is not a valid schedule, since O(log n) jobs are scheduled at one time;
however, it can be converted to a valid schedule by use of the following lemma.
Lemma 3.7 Consider an invalid schedule S for a set of jobs with release dates on m unrelated
parallel machines, in which at most - jobs are assigned to each machine at any time. If W is the
average weighted completion time of S, then there exists a schedule of average weighted completion
time at most -W , in which at most one job is assigned to each machine at any time,
Proof: Consider a job J j scheduled in S; let its completion time be C S
. If we schedule the jobs
on each machine in the order of their completion times in S, never starting one before it's release
date, then in the resulting schedule
1. J j is started no earlier than its release date,
2. J j finishes by time at most -C S
.
Statement 1 is true by design of the algorithm. Statement 2 is true since at most -C S
work from other jobs can complete no later than C S
in schedule S, and jobs run simultaneously
in schedule S can run back-to-back with no intermediate idle time in our expanded schedule.
Therefore, job J j is started by time -C S
completed by time -C S
.
Combining the last two lemmas with the observation that p max - n 3 implies jM j - mn 4 yields
the following theorem.
Theorem 3.8 There is a polynomial-time O(log 2 n)-approximation algorithm for the minimization
of average weighted completion time of a set of jobs with machine-varying release dates on unrelated
machines, under the assumption that the maximum job sizes are bounded by p
3.4 Large Jobs
Since the p ij are input in binary and in general need not be polynomial in n and m, the technique
of the last section can not be applied directly to all instances, since it would yield superpolynomial-
size formulations. Therefore we must find a way to handle very large jobs without impacting
significantly on the quality of solution.
It is a standard technique in combinatorial scheduling to partition the jobs into a set of large
jobs and a set of small jobs, schedule the large jobs, which are scaled to be in a polynomially-
bounded range, and then schedule the small jobs arbitrarily and show that their net contribution is
not significant, (see e.g. [24]). In the minimization of average weighted completion time, however,
we must be more careful, since the small jobs may have large weights and can not be scheduled
arbitrarily.
We employ several steps, each of which increases the average weighted completion time by a
small constant factor. With more care we could reduce the constants introduced by each step;
however since our overall bound is O(log 2 n) we dispense with this precision for the sake of clarity
of exposition.
The basic idea is to characterize each job by the minimum value, taken over all machines, of its
(release date processing time) on that machine. We then group the jobs together based on the
size of their minimum . The jobs in each group can be scaled down to be of polynomial
size and thus we can construct a schedule for the scaled down versions of each group. We then
scale the schedules back up, correct for the rounding error, and show that this does not affect the
quality of approximation by more than a constant factor. We then apply Lemma 3.9 (see below)
to show that the makespan can be kept short simultaneously.
The resulting schedules will be scheduled consecutively. However, since we have kept the
makespan from growing too much, we have an upper bound on the start time of each subsequent
schedule and thus we can show that the the net disturbance of the initial schedules to the latter
schedules will be minimal.
We now proceed in greater detail. Let m(J
g. Note that there are at most n nonempty J i , one for each of the n jobs. We will employ the
following lemma in order to keep the makespan from growing too large.
Lemma 3.9 A schedule S for J k can be converted, in polynomial time, to a schedule T of makespan
at most 2n k+1 such that C T
Proof: Remove all jobs from S that complete later than time n k+1 , and, starting at time n k+1 ,
schedule them arbitrarily on the machine on which they run most quickly. This will take at most
n k+1 time, so therefore any rescheduled job J j satisfies C T
.
We now turn to the problem of scheduling each J l with a bounded guarantee on the average
completion time.
Lemma 3.10 There exists an O(log 2 n)-approximation algorithm to schedule each J l . In addition
the schedule for J l has makespan at most 2n l+1 .
Proof: Let A be the algorithm referred to in Theorem 3.8. We will use A to find an approximately
optimal solution S l for each J l . A can not be applied directly to J l since the sizes of the jobs
involved may exceed n 3 , so we apply A to a scaled version of J l .
For all j such that J j 2 J l and for all i, set p 0
c and r 0
c. Note that on at least
one machine i , for each job J j , p 0
We use A to obtain an approximate solution to the scaled version of J l of average weighted
completion time W . Although some of the p 0
may still be large, Lemma 3.9 indicates that restricting
the hypergraph formulation constructed by A to allow completion times no later than time
only affect the quality of approximation by at most a factor of 2. Therefore jM j,
the number of (machine, time) pairs, is O(mn 3 ). Note that some of the p 0
ij may be 0, but it is still
important to include an edge in the hypergraph formulation for each job of size 0.
Now we argue that interpreting the solution of the scaled instance as a solution to the original
instance J l does not degrade the quality of approximation by more than a constant factor. The
conversion from the scaled instance to the original instance is carried out by multiplying p
ij (which has no impact on quality of approximation) and then adding to each
r
ij and p
ij the residual amount that was lost due to the floor operation.
The additional residual amounts of the release dates contribute at most a total of n l\Gamma1 time to
the makespan of the schedule, since jr
therefore the entire contribution to the
makespan is bounded above by n \Theta n . By a similar argument, the entire contribution of
the residual amounts of the processing times to the makespan is bounded above by n l\Gamma1 .
So in the conversion from p
ij to we add at most 2n l\Gamma1 to the makespan of the schedule
for J l . However, n l\Gamma1 is a lower bound on the completion time of any job in J l . Therefore, even if
this additional time were added to the completion time of every job, the restoration of the residual
amounts of the r ij and p ij degrades the quality of the approximation to average completion time
by at most a constant factor. Finally, to satisfy the makespan constraint, we apply Lemma 3.9.
We now construct two schedules S o and S e . In S o we consecutively schedule
in S e we consecutively schedule :. For the sake of clarity our schedule will have time
of length 2n i+1 dedicated to each S i even if S i has no jobs.
Lemma 3.11 Let J o be the set of jobs scheduled in S o and J e the set of jobs scheduled in S e .
The average weighted completion time of S o is within a factor of O(log 2 n) of the best possible for
similarly for S e and J e .
Proof: The subschedule for any set J i scheduled in S o or S e begins by time
since J i is scheduled after J i\Gamma2 ; J and the makespan of J l is at most 2n l+1 . Since n i\Gamma1 is
a lower bound on the completion time of any job in J i , in the combined schedule S o or S e , each
job completes within a small constant factor of its completion time in S i .
We now combine S o and S e by superimposing them over the same time slots. This creates an
infeasible schedule in which the sum of completion times is just the sum of the completions times in
but in which there may be two jobs scheduled simultaneously. We then use Lemma 3.7
to combine S o and S e to obtain a schedule S ff for all the jobs, whose average weighted completion
time is within a factor of O(log 2 n) of optimal.
Theorem 3.12 There is a polynomial-time O(log 2 n)-approximation algorithm for the minimization
of average weighted completion time of a set of jobs with machine-varying release dates on
unrelated machines.
3.5 Scheduling with Periodic Connectivity
The hypergraph formulation of the scheduling problem can model time-varying connectivity between
jobs and machines; e.g. a job can only be processed during certain times on each machine.
In this section we show how to apply our techniques to scheduling problems of periodic connectivity
under some modest assumptions on the length of the period and job sizes.
Definition 3.13 The periodic scheduling problem is defined by n jobs, m unrelated machines, a
period P , and for each time unit of P a specification of which jobs are allowed to run on which
machines at that time.
Theorem 3.14 Let I be an instance of the periodic scheduling problem in which p max is polynomial
in n and m, and let the optimum makespan of I be L. There exists a polynomial-time algorithm
which delivers a schedule of makespan O(log n)(L
Proof:
As above, we assume that L is known in advance, and then use binary search to complete the
algorithm.
We construct the integer program
(i;t)2e
Lg. We include an edge in the formulation if and only
if it is valid with respect to the connectivity conditions. We then use Theorem 3.8 to produce a
relaxed solution that satisfies
j2e
x
(i;t)2e
x
x
Let the length of this relaxed schedule be L; L - L. We construct a valid schedule of length
concatenating O(log n) blocks of length L. At the end of each block we will
have to wait until the start of the next period to begin the next block; hence we obtain an overall
bound of O(log n)(L
Note that we are assuming that the entire connectivity pattern of P is input explicitly; if it is
input in some compressed form then we must assume that P is polynomial in n and m.
One motivation for such problems is the domain of satellite communication systems [18, 26].
One is given a set of sites on Earth and a set of satellites(in Earth orbit). Each site generates a
sequence of communication requests; each request is potentially of a different duration and may
require communication with any one of the satellites. A site can only transmit to certain satellites at
certain times, based on where the satellite is in its orbit. The connectivity pattern of communication
opportunities is periodic, due to the orbiting nature of the satellites.
The goal is to satisfy all communication requests as quickly as possible. We can use our
hypergraph formulation technique to give an O(log n)-approximation algorithm for the problem
under the assumption that the p j are bounded by a polynomial, since the rounding techniques do
not generalize to this setting.

Acknowledgments

We are grateful to Phil Klein for several helpful discussions early in this
research, to David Shmoys for several helpful discussions, especially about the upper bound for
average completion time, to David Peleg and Baruch Awerbuch for explaining their off-line approximation
algorithm to us, and to Perry Fizzano for reading an earlier draft of this paper.



--R

Lower bounds on the competitive ratio for mobile user tracking and distributed job scheduling.
Competitive distributed job scheduling.

Deterministic load balancing in computer networks.
Job scheduling in rings.
Bounds for certain multiprocessor anomalies.
Bounds on multiprocessing anomalies.
Bounds for naive multiple machine scheduling with release times and deadlines.
Approximation schemes for constrained scheduling problems.
Using dual approximation algorithms for scheduling problems: theoretical and practical results.
A polynomial approximation scheme for machine scheduling on uniform processors: using the dual approximation approach.
Minimizing average flow time with parallel machines.
Reducibility among combinatorial problems.
Worst case bound of an lrf schedule for the mean weighted flow-time problem
Rinnooy Kan
Rinnooy Kan

Mobile satellite communication systems: Toward global personal communications.
Towards an architecture-independent analysis of parallel algo- rithms
Private communication
Fast approximation algorithms for fractional packing and covering problems.
Probabilistic construction of deterministic algorithms: approximating packing integer programs.
Randomized rounding: a technique for provably good algorithms and algorithmic proofs.
Improved approximation algorithms for shop scheduling problems.
Scheduling parallel machines with costs.
Mobile satellite services for travelers.
--TR

--CTR
Dekel Tsur, Improved scheduling in rings, Journal of Parallel and Distributed Computing, v.67 n.5, p.531-535, May, 2007
Cynthia A. Phillips , R. N. Uma , Joel Wein, Off-line admission control for general scheduling problems, Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms, p.879-888, January 09-11, 2000, San Francisco, California, United States
S. Muthukrishnan , Rajmohan Rajaraman, An adversarial model for distributed dynamic load balancing, Proceedings of the tenth annual ACM symposium on Parallel algorithms and architectures, p.47-54, June 28-July 02, 1998, Puerto Vallarta, Mexico
Martin Skutella, Convex quadratic and semidefinite programming relaxations in scheduling, Journal of the ACM (JACM), v.48 n.2, p.206-242, March 2001
approximation algorithm;networks;NP-completeness;scheduling