Approximating the Throughput of Multiple Machines in Real-Time Scheduling.
We consider the following fundamental scheduling problem. The input to the problem consists of n jobs and k machines. Each of the jobs is associated with a release time, a deadline, a weight, and a processing time on each of the machines. The goal is to find a nonpreemptive schedule that maximizes the weight of jobs that meet their respective deadlines. We give constant factor approximation algorithms for four variants of the problem, depending on the type of the machines (identical vs. unrelated) and the weight of the jobs (identical vs. arbitrary). All these variants are known to be NP-hard, and the two variants involving unrelated machines are also MAX-SNP hard. The specific results obtained are as follows:  For identical job weights and unrelated machines: a greedy $2$-approximation algorithm.  For identical job weights and k identical machines: the same greedy algorithm achieves a tight $\frac{(1+1/k)^k}{(1+1/k)^k-1}$ approximation factor. For arbitrary job weights and a single machine: an LP formulation achieves a 2-approximation for polynomially bounded integral input and a 3-approximation for arbitrary input. For unrelated machines, the factors are 3 and 4, respectively.  For arbitrary job weights and k identical machines: the LP-based algorithm applied repeatedly achieves a $\frac{(1+1/k)^k}{(1+1/k)^k-1}$ approximation factor for polynomially bounded integral input and a $\frac{(1+1/2k)^k}{(1+1/2k)^k-1}$ approximation factor for arbitrary input. For arbitrary job weights and unrelated machines: a combinatorial $(3+2\sqrt{2} \approx 5.828)$-approximation algorithm.
Introduction
We consider the following fundamental scheduling problem. The input to the problem consists of
n jobs and k machines. Each of the jobs is associated with a release time, a deadline, a weight,
and a processing time on each of the machines. The goal is to nd a schedule that maximizes the
weight of the jobs that meet their deadline. Such scheduling problems are frequently referred to
as real-time scheduling problems, and the objective of maximizing the value of completed jobs is
frequently referred to as throughput. We consider four variants of the problem depending on the
type of the machines (identical vs. unrelated) and the weight of the jobs (identical vs. arbitrary).
Garey and Johnson [13] (see also [14]) show that even the simplest decision problem corresponding
to this problem is already NP-Hard in the strong sense. In this decision problem the input
consists of a set of n jobs with release time, deadline, and processing time. The goal is to decide
whether all these jobs can be scheduled on a single machine; each within its time window. We show
that the two variants involving unrelated machines are also MAX-SNP hard.
In this paper we give constant factor approximation algorithms for all four variants of the
problem. To the best of our knowledge, this is the rst paper that gives approximation algorithms
with guaranteed performance (approximation factor) for these problems. We say that an algorithm
has an approximation factor  for a maximization problem if the weight of its solution is at least
1=OPT, where OPT is the weight of an optimal solution. (Note that we dened the approximation
factor so that it would always be at least 1.)
The specic results obtained are listed below and summarized in the table given in Figure 1.
weight function identical machines unrelated machines
identical job weights (2; 1:8;
arbitrary job weights (2; 1:8;
integral, poly-size, input
arbitrary job weights (3; 2:78;
arbitrary input

Figure

1: Each entry contains the approximation factors for
For identical job weights and unrelated machines, we give a greedy 2-approximation algorithm.
For identical job weights and k identical machines, we show that the same greedy algorithm
achieves a tight (1+1=k) k
approximation factor.
For arbitrary job weights, we round a fractional solution obtained from a linear programming
relaxation of the problem. We distinguish between the case where the release times, deadlines,
and processing times, are integral and polynomially bounded, and the case where they are
arbitrary. In the former case, we achieve a 2-approximation factor for a single machine, and a
3-approximation factor for unrelated machines. In the latter case, we get a 3-approximation
factor for a single machine, and a 4-approximation factor for unrelated machines.
For arbitrary job weights and k identical machines, we achieve a (1+1=k) k
approximation
factor for polynomially bounded integral input, and a (1+1=2k) k
approximation factor for
arbitrary input. Note that as k tends to innity these factors tend to e
1:58198, and
e
2:54149, respectively.
For arbitrary job weights and unrelated machines we also present a combinatorial (3 +2
approximation factor (3
The computational di-culty of the problems considered here is due to the \slack time" available
for scheduling the jobs. In general, the time window in which a job can be scheduled may be (much)
larger than its processing time. Interestingly, the special case where there is no slack time can be
solved optimally in polynomial time even for multiple machines [3]. Moreover, the problem can be
solved on a single machine with the execution window less than twice the length of the job.
Another special case that was considered earlier in the literature is the case in which all jobs
are released at the same time (or equivalently, the case in which all deadlines are the same). This
special case remains NP-Hard even for a single machine. However, Sahni [24] gave a fully polynomial
approximation scheme for this special case.
The problems considered here have many applications. Hall and Magazine [17] considered
the single machine version of our problem in the context of maximizing the scientic, military
or commercial value of a space mission. This means selecting and scheduling in advance a set
of projects to be undertaken during the space mission, where an individual project is typically
executable during only part of the mission. It is indicated in [17] that up to 25% of the budget of a
space mission may be spent in making these decisions. Hall and Magazine [17] present eight heuristic
procedures for nding an optimal solution together with computational experiments. However, they
do not provide any performance guarantees on the solutions produced by their heuristics. They also
mention the applicability of such problems to patient scheduling in hospitals. For more applications
and related work in the scheduling literature see [8, 11] and the survey of [22].
The preemptive version of our problem for a single machine was studied by Lawler [21]. For
identical job weights, Lawler showed how to apply dynamic programming techniques to solve the
problem in polynomial time. He extended the same techniques to obtain a pseudo-polynomial
algorithm for arbitrary weights as well ([21]). Lawler [20] also obtained polynomial time algorithms
that solve the problem in two special cases: (i) the time windows in which jobs can be scheduled are
nested; and (ii) the weights and processing times are in opposite order. Kise, Ibaraki and Mine [18]
showed how to solve the special case where the release times and deadlines are similarly ordered.
A closely related problem is considered Adler et al. [1] in the context of communication in linear
networks. In this problem, messages with release times and deadlines have to be transmitted over
a bus that has a unit bandwidth, and the goal is to maximize the number of messages delivered
within their deadline. It turns out that our approximation algorithms for the case of arbitrary
weights can be applied to the weighted version of the unbuered case considered in [1] to obtain
a constant factor approximation algorithm. No approximation algorithm is given in [1] for this
version.
In the on-line version of our problems, the jobs appear one by one, and are not known in
advance. Lipton and Tomkins [23] considered the non-preemptive version of the on-line problem,
while Koren and Shasha [19] and Baruah et al. [7] considered the preemptive version. The special
cases where the weight of a job is proportional to the processing time were considered in the on-line
setting in several papers [5, 10, 12, 15, 16, 6]. Our combinatorial algorithm for arbitrary weights
borrows some of the techniques used in the on-line case.
Some of our algorithms are based on rounding a fractional solution obtained from a linear
programming (LP) relaxation of the problem. In the LP formulation for a single machine we have
a variable for every feasible schedule of each of the jobs, a constraint for each job, and a constraint
for each time point. A naive implementation of this approach would require an unbounded number
of variables and constraints. To overcome this di-culty, we rst assume that all release times,
deadlines, and processing times are (polynomially bounded) integers. This yields a polynomial
number of variables and constraints, allowing for the LP to be solved in polynomial time. For
the case of arbitrary input, we show that we need not consider more than O(n 2 ) variables and
constraints for each of the n jobs. This yields a strongly polynomial running time at the expense
of a minor degradation in the approximation factor. The rounding of the LP is done by reducing
the problem to a graph coloring problem.
We extend our results from a single machine to multiple machines by applying the single machine
algorithm repeatedly, machine by machine. We give a general analysis for this type of algorithms
and, interestingly, prove that the approximation factor for the case of identical machines is superior
to the approximation factor of the single machine algorithm which served as our starting
point. A similar phenomenon (in a dierent context) has been observed by Cornuejols, Fisher and
Nemhauser [9]. Our analysis in the unrelated machines case is similar to the one described (in
a dierent context) by Awerbuch et al. [4]. Unlike the identical machines case, in the unrelated
machines case the extension to multiple machines degrades the performance relative to a single
machine.
Our algorithms (and specically our LP based algorithms) can be applied to achieve approximation
algorithms for other scheduling problems. For example, consider a problem where we can
compute an estimate of the completion time of the jobs in an optimal (fractional) solution. Then,
we can apply our algorithms using these estimated completion times as deadlines, and get a schedule
where a constant fraction of the jobs indeed nish by these completion times. This observation has
already been applied by Wein [25] to achieve constant factor approximation algorithms for various
problems, among them the minimum
ow-time problem.
Denitions and notations
Let the job system contain n jobs Each job
J i is characterized by the quadruple (r g. The interpretation
is that job J i is available at time r i , the release time, it must be executed by time d i , the deadline,
its processing time on machine M j is ' i;j , and w i is the weight (or prot) associated with the job.
We note that our techniques can also be extended to the more general case where the release time
and deadline of each job dier on dierent machines. However, for simplicity, we consider only the
case where the release time and deadline of each job are the same on all machines. The hardness
results are also proved under the same assumption.
We refer to the case in which all job weights are the same as the unweighted model, and the
case in which job weights are arbitrary as the weighted model. (In the unweighted case our goal
is to maximize the cardinality of the set of scheduled jobs.) We refer to the case in which the
processing times of the jobs on all the machines are the same as the identical machines model,
and the case in which processing times dier as the unrelated machines model. In the unweighted
jobs and identical machines model, job J i is characterized by a triplet (r
Without loss of generality, we assume that the earliest release time is at time
A feasible scheduling of job J i on machine M j at time t, r i  t  d i ' i;j , is referred to as a job
instance, denoted by J i;j (t). A job instance can also be represented by an interval on the time line
[0; 1). We say that the interval J i;j belongs to job J i . In general, many intervals
may belong to a job. A set of job instances J 1;j (t 1 feasible schedule on machine
if the corresponding intervals are independent, i.e., they do not overlap, and they belong to
distinct jobs. The weight of a schedule is the sum of the weights of the jobs to which the intervals
(job instances) belong. In the case of multiple machines, we need to nd a feasible schedule of
distinct jobs on each of the machines. The objective is to maximize the sum of the weights of all
schedules.
We distinguish between the case where the release times, processing times, and deadlines are
integers bounded by a polynomial in the number of jobs, and between the case of arbitrary inputs.
The former case is referred to as polynomially bounded integral input and the latter case is referred
to as arbitrary input.
3 Unweighted jobs
In this section we consider the unweighted model. We dene a greedy algorithm and analyze its
performance in both the unrelated and identical models. In the former model, we show that it
is a 2-approximation algorithm, and in the latter model, we show that it is a (k)-approximation
algorithm, where
3.1 The greedy algorithm
The greedy strategy for a single machine is as follows. At each time step t (starting at the
algorithm schedules the job instance that nishes rst among all jobs that can be scheduled at t
or later. Note that the greedy algorithm does not take into consideration the deadlines of the jobs,
except for determining whether jobs are eligible for scheduling. The greedy algorithm for multiple
machines just executes the greedy algorithm (for a single machine) machine by machine.
We now dene the procedure NEXT(t; j; J ). The procedure determines the job instance J i;j (t 0 ),
t, such that t 0 is the earliest among all instances of jobs in J that start at time t or later
on machine M j . If no such interval exists, the procedure returns null, otherwise the procedure
returns J i;j (t 0 ).
Algorithm 1-GREEDY(j; J ) nds a feasible schedule on machine M j among the jobs in J . by
calling Procedure NEXT repeatedly.
1. The rst call is for J
2. Assume the algorithm has already computed Let the current time be
let the current set of jobs be J := J n fJ g.
3. The algorithm calls NEXT(t; j; J ) that returns either J i h+1 ;j (t h+1 ) or null.
4. The algorithm terminates in round r returns null. It returns the
set )g.
Algorithm k-GREEDY(J ) nds k schedules such that a job appears at most once in the schedules.
It calls Algorithm 1-GREEDY machine by machine, each time updating the set J of jobs to be
scheduled. Assume that the output of 1-GREEDY(j; J ) in the rst
where G j is a feasible schedule on machine M j , for 1  j  i 1. Then, the algorithm calls
The following property of Algorithm 1-GREEDY is used in the analysis of the approximation
factors of our algorithms.
Proposition 3.1 Let the set of jobs found by 1-GREEDY(j; J ) for a job system J be G. Let H be
any feasible schedule on machine M j among the jobs in J n G. Then, jHj  jGj.
Proof: For each interval (job instance) in H there exists an interval in G that overlaps with it and
terminates earlier. Otherwise, 1-GREEDY would have chosen this interval. The proposition follows
from the feasibility of H, since at most one interval in H can overlap with the end point of any
interval in G. 2
3.2 Unrelated machines
Based on Proposition 3.1, the following theorem states the performance of the k-GREEDY algorithm
in the unweighted jobs and unrelated machines model.
Theorem 3.2 Algorithm k-GREEDY achieves a 2 approximation factor in the unweighted jobs and
unrelated machines model.
Proof: Let be the output of k-GREEDY and let OPT
the sets of intervals scheduled on the k machines by an optimal solution OPT. (We note that these
sets will be considered as jobs and job instances interchangeably.) Let H be the set
of all the jobs scheduled by OPT on machine M j that k-GREEDY did not schedule on any machine
and let be the set of jobs taken by both k-GREEDY
and OPT. It follows that OPT
Proposition 3.1 implies that jH j j  jG j j. This is true since H j is a feasible schedule on machine
among the jobs that were not picked by k-GREEDY while constructing the schedule for machine
. Since the sets H j are mutually disjoint and the same holds for the sets G j , jHj  jG(k)j. Since
jOGj  jG(k)j, we get that jOPT (k)j  2jG(k)j and the theorem follows. 2
3.3
In this section we analyze the k-GREEDY algorithm for the unweighted jobs and identical machines
model. We show that the approximation factor in this case is
For 9=5, and for k !1 we have
The analysis below is quite general and just uses the facts that the algorithm is applied sequentially
machine by machine, and that the machines are identical. Let OPT (k) be an optimal
schedule for k identical machines. Let A be any algorithm for one machine. Dene by A (k) (or
by (k) when A is known) the approximation factor of A compared with OPT (k). Note that the
comparison is done between an algorithm that uses one machine and an optimal schedule that uses
machines. Let A(k) be the algorithm that applies algorithm A, machine by machine, k times. In
the next theorem we bound the performance of A(k) using (k).
Theorem 3.3 Algorithm A(k) achieves an (k) k
approximation factor for k identical
machines.
Proof: Let A i be the set of jobs chosen by A(k) for the i-th machine. Suppose that the algorithm
has already chosen the sets of jobs A Consider the schedule given by removing from
OPT (k) all the jobs in A were also chosen by the optimal solution. Clearly, this is
still a feasible schedule of cardinality at least jOPT (k)j
Therefore, by the denition
of (k), the set A i satises jA i j  (1=(k))(jOPT (k)j
Rearranging the terms gives
us the equation,
We prove by induction on i that
. Assume the claim holds for i 1. Applying the
induction hypothesis to Equation (1) we get,
Rearranging terms yields the inductive claim. Setting proves the theorem, namely,
We now apply the above theorem to algorithm k-GREEDY. We compute the value of (k) for
algorithm 1-GREEDY, and observe that algorithm k-GREEDY indeed applies algorithm 1-GREEDY
k times, as assumed by Theorem 3.3.
Theorem 3.4 The approximation factor of k-GREEDY is
, in the unweighted jobs
and identical machines model.
Proof: Recall that algorithm 1-GREEDY scans all the intervals ordered by their end points and
picks the rst possible interval belonging to a job that was not picked before. Suppose this greedy
strategy picks set G, and consider the schedule of machines numbered
Similar to the arguments of Proposition 3.1, in each of the machines, if a particular job of H was
not chosen, then there must be a job in progress in G. Also this job must nish before the particular
job in H nishes. Thus, the number of jobs in H executed on any single machine by the optimal
schedule has to be at most jGj. Since the jobs executed by the optimal schedule on dierent
machines are disjoint, we get jHj  kjGj. Consequently, jOPT (k)j
The theorem follows by setting this value for (k) in Theorem 3.3. 2
3.4 Tight bounds for GREEDY
In this subsection we construct an instance for which our bounds in the unweighted model for
algorithm GREEDY are tight. We rst show that for one machine (where the unrelated and identical
models coincide) the 2-approximation is tight. Next, we generalize this construction for the
unrelated model, and prove the tight bound of 2 for k > 1 machines. Finally, we generalize the
construction for one machine to k > 1 identical machines and prove the tight bound of (k).
Recall that in the unweighted model each job is characterized by a triplet (r in the
identical machines model and by a triplet (r g, in the unrelated
machines model.
3.4.1 A single machine
For a single machine the system contains two jobs: G
1-GREEDY schedules the instance G 1 (0) of job G 1 and cannot schedule any instance of H 1 . An
optimal solution schedules the instances H 1 (0) and G 1 (2). Clearly, the ratio is 2. We could repeat
this pattern on the time axis to obtain this ratio for any number of jobs.
This construction demonstrates the limitation of the approach of Algorithm 1-GREEDY. This
approach ignores the deadlines and therefore does not capitalize on the urgency in scheduling job
H 1 in order not to miss its deadline. We generalize this idea further for k machines.
3.4.2 Unrelated machines
For machines the job system contains 2k jobs: G . The release time
of all jobs is 0. The deadline of all the G-type jobs is 3 and the deadline of all the H-type jobs is
2. The length of job G i on machine M i is 1 and it is 4 on all other machines. The length of job H i
on machine M i is 2 and it is 3 on all other machines.
Note that only jobs G i and H i can be scheduled on machine M i , since all other jobs are too
long to meet their deadline. Hence, Algorithm k-GREEDY considers only these two jobs while
constructing the schedule for machine M i . As a result, k-GREEDY selects the instance G i (0) of
to be scheduled on machine M i and cannot schedule any of the H-type jobs. On the other
hand, an optimal solution schedules the instances H i (0) and G i (2) on machine M i .
Algorithm k-GREEDY schedules k jobs while an optimal algorithm schedules all 2k
jobs. This yields a tight approximation factor of 2 in the unweighted jobs and unrelated machines
model.
3.4.3
We dene job systems J (k) for any given k  1. We show that on J (k) the performance of
k-GREEDY(J (k)) is no more than (1=(k))  OPT(J (k)). The J (1) system is the one dened in
Subsection 3.4.1. The J (2) job system contains
2). If we set
and Algorithm 2-GREEDY to make the following selections:
On the rst machine, 2-GREEDY schedules all the 6 jobs of type G 1 . This is true since these
jobs are of length less than the lengths of the jobs of type G 2 and the jobs of type H. The
last G 1 -type interval terminates at time 60. Hence, there is no room for a G 2 -type (H-type)
interval, the deadline of which is 70 (48), and the length of which is 11 (12).
On the second machine, 2-GREEDY schedules all the 4 jobs of type G 2 since they are shorter
than the jobs of type H. The last G 2 -type job terminates at time 44 which leaves no room
for another job of type H.
jobs. We show now an optimal solution that schedules all
jobs. It schedules 9 jobs on each machine as follows:
Note that all the instances terminate before their deadlines. As a result we get a ratio
We are ready to dene J (k) for any k  1. The job system contains k(k jobs. Algorithm
k-GREEDY is able to schedule only k(k+1) k k k+1 out of them and there exists an optimal solution
that schedules all of them. As a result we get the ratio
The J (k) system is composed of k
jobs (0; d setting ' as a large enough number
and then xing d and d, we force Algorithm k-GREEDY to select for machine i all the jobs
of type G i but no other jobs. Thus k-GREEDY does not schedule any of the H-type jobs. On the
other hand, an optimal solution is able to construct the same schedule for all the k machines. It
starts by scheduling 1=k of the H-type jobs with their rst possible instance. Then, it schedules in
turn 1=k of the jobs from G k ; G k order. The values of d; d allow for such
a schedule.
We omit the details of how to set ' and how to determine the deadlines. We just remark that
to validate the optimal schedule, we get lower bounds for the deadlines and to force the k-GREEDY
schedule we get upper bounds for the deadlines. If ' is large enough, then these upper bounds are
larger than the lower bounds.
For could check the following values:
and d
Weighted jobs
In this section we present approximation algorithms for weighted jobs. We rst present algorithms
for a single machine and for unrelated machines that are based on rounding a linear programming
relaxation of the problem. Then, we re-apply the analysis of Theorem 3.3 to get better approximation
factors for the identical machines model. We conclude with a combinatorial algorithm
for unrelated machines which is e-cient and easy to implement. However, it achieves a weaker
approximation guarantee.
4.1 Approximation via linear programming
In this subsection we describe a linear programming based approximation algorithm. We rst
describe the algorithm for the case of a single machine, and then generalize it to the case of
multiple machines. Our linear programming formulation is based on discretizing time. Suppose
that the time axis is divided into N time slots. The complexity of our algorithms depends on N .
However, we assume for now that N is part of the input, and that the discretization of time is ne
enough so as to represent any feasible schedule (up to small shifts). Later, we show how to get rid
of these assumptions at the expense of a slight increase in the approximation factor.
The linear program relaxes the scheduling problem in the following way. A fractional feasible
solution is one which distributes the processing of a job between the job instances or intervals
belonging to it with the restriction that at any given point of time t, the sum of the fractions
assigned to all the intervals at t (belonging to all jobs) does not exceed 1. To this end, for each job
for each interval [t; t belonging to it, i.e., for which t  r i and
It would be convenient to assume that x other value of t between 1 and
N . The linear program is as follows.
maximize
subject to:
For each time slot t, 1  t
For each job i, 1  i  n:
x it  1
For all i and t: 0  x it  1
It is easy to see that any feasible schedule denes a feasible integral solution to the linear program
and vice versa. Therefore, the value of an optimal (fractional) solution to the linear program is an
upper bound on the value of an optimal integral solution.
We compute an optimal solution to the linear program and denote the value of variable x it in
this solution by q it . Denote the value of the objective function in an optimal solution by OPT. We
now show how to round an optimal solution to the linear program to an integral solution.
To show how the linear program is used we dene a coloring of intervals. The collection of all
intervals belonging to a set of jobs J can be regarded as an interval representation of an interval
graph I. We dene a set of intervals in I to be independent if: (i) No two intervals in the set
in the set belong to the same job. (Note that this denition is more
restrictive than the regular independence relation in interval graphs.) Clearly, an independent set
of intervals denes a feasible schedule. The weight of an independent set P , w(P ), is dened to be
the sum of the weights of the jobs to which the intervals belong.
Our goal is to color intervals in I such that each color class induces an independent set. We
note that not all intervals are required to be colored and that an interval may receive more than one
color. Suppose that a collection of color classes (independent sets) non-negative
coe-cients
there exists a color class P i , 1  i  m, for which w(P i )  OPT=2. This color class is dened to
be our approximate solution, and the approximation factor is 2. It remains to show how to obtain
the desired coloring.
We now take a short detour and dene the group constrained interval coloring problem. Let
be an interval representation in which the maximum number of mutually overlapping
intervals is t 1 . Suppose that the intervals are partitioned into disjoint groups
group contains at most t 2 intervals. A legal group constrained coloring of the intervals in Q is a
coloring in which: (i) Overlapping intervals are not allowed to get the same color; (ii) Intervals
belonging to the same group are not allowed to get the same color.
Theorem 4.1 There exists a legal group constrained coloring of the intervals in Q that uses at
most
Proof: We use a greedy algorithm to obtain a legal coloring using at most t 1
the intervals in Q by their left endpoint and color the intervals from left to right with respect to
this ordering. When an interval is considered by the algorithm it is colored by any one of the free
colors available at that time. We show by induction that when the algorithm considers an interval,
there is always a free color.
This is true initially. When the algorithm considers interval Q i , the colors that cannot be used
for Q i are occupied by either intervals that overlap with Q i , or by intervals that belong to the
same group as Q i . Since we are considering the intervals sorted by their left endpoint, all intervals
overlapping with Q i also overlap with each other, and hence there are at most t 1 1 such intervals.
There can be at most t 2 1 intervals that belong to the same group as Q i . Since the number of
available colors is there is always a free color. 2
We are now back to the problem of coloring the intervals in I. Let N . We can round
each fraction q it in the optimal solution to the closest fraction of the form a=N 0 , where 1  a  N 0 .
This incurs a negligible error (of at most 1=(Nn) factor) in the value of the objective function. We
now generate an interval graph I 0 from I by replacing each interval J i (t) 2 I by q it  N 0 \parallel"
intervals. Dene a group constrained coloring problem on I 0 , where group
all instances of job J i . Note that in I 0 , the maximum number of mutually overlapping intervals is
bounded by N 0 , and the maximum number of intervals belonging to a group is also N 0 .
By Theorem 4.1, there exists a group constrained coloring of I 0 that uses at most 2N 0 1 colors.
Attach a coe-cient of 1=N 0 to each color class. Clearly, the sum of the coe-cients is less than 2.
Also, by our construction, the sum of the weights of the intervals in all the color classes, multiplied
by the coe-cient 1=N 0 , is OPT. We conclude,
Theorem 4.2 The approximation factor of the algorithm that rounds an optimal fractional solution
is 2.
We note that the technique of rounding a fractional solution by decomposing it into a convex
combination of integral solutions was also used by Albers et al. [2]
4.1.1 Strongly polynomial bounds
The di-culty with the linear programming formulation and the rounding algorithm is that the
complexity of the algorithm depends on N , the number of time slots. We now show how we choose
N to be a polynomial in the number of jobs, n, at the expense of losing a bit in the approximation
factor.
First, we note that in case the release times, deadlines, and processing times are integral, we
may assume without loss of generality that each job is scheduled at an integral point of time. If,
in addition, they are restricted to integers of polynomial size, then the number of variables and
constraints is bounded by polynomial.
We now turn our attention to the case of arbitrary inputs. Let p(n) be a (n 2 ) polynomial.
Partition the jobs in J into two classes:
Big slack jobs: J
Small slack jobs: J
We obtain a fractional solution separately for the big slack jobs and small slack jobs. We rst
explain how to obtain a fractional solution for the big slack jobs. For each big slack job J
nd p(n) non-overlapping job instances and assign a value of 1=p(n) to each such interval. Note
that this many non-overlapping intervals can be found since d i r i is large enough. We claim that
this assignment can be ignored when computing the solution (via LP) for the small slack jobs.
This is true because at any point of time t, the sum of the fractions assigned to intervals at t
belonging to big slack jobs can be at most n=p(n), and thus their eect on any fractional solution
is negligible. (In the worst case, scale down all fractions corresponding to small slack jobs by a
factor of (1 n=p(n)).) Nevertheless, a big slack job contributes all of its weight to the fractional
objective function.
We now restrict our attention to the set of small slack jobs and explain how to compute a
fractional solution for them. For this we solve an LP. To bound the number of variables and
constraints in the LP we partition time into at most n  (p(n) slots. Instead of having a
variable for each job instance we consider at most n 2 (p(n)+1) variables, where for each job J
there are at most n  (p(n) and the j-th variable \represents" all the job instances
of J i that start in the j-th time slot. Similarly, we consider at most n  (p(n)
where the j-th constraint \covers" the j-th time slot. For each small slack job J
along the time axis at points r
p(n) , for dening
all the n  (p(n) dividers, the time slots are determined by the adjacent dividers. The main
observation is that for each small slack job J i , no interval can be fully contained in a time slot, i.e.,
between two consecutive dividers.
The LP formulation for the modied variables and constraints is slightly dierent from the
original formulation. To see why, consider a feasible schedule. As mentioned above, a job instance
cannot be fully contained in a time slot t. However, the schedule we are considering may consist of
two instances of jobs such that one terminates within time slot t and the other starts within t. If
we keep the constraints that stipulate that the sum of the variables corresponding to intervals that
intersect a time slot is bounded by 1, then we would not be able to represent such a schedule in
our formulation. To overcome this problem, we relax the linear program, and allow that at every
time slot t, the sum of the fractions assigned to the intervals that intersect t can be at most 2. The
relaxed linear program is the following.
maximize
subject to:
For each time slot t:
For each job i, 1  i  n:
x it  1
For all i and t: 0  x it  1
It is easy to see that our relaxation guarantees that the value of the objective function in the
above linear program is at least as big as the value of an optimal schedule. We round an optimal
fractional solution in the same way as in the previous section. Since we relaxed our constraints, we
note that when we run the group constrained interval coloring algorithm, the number of mutually
overlapping intervals can be at most twice the number of intervals in each group. Therefore, when
we generate the color classes , we can only guarantee that:
yielding an approximation factor of 3. We
conclude,
Theorem 4.3 The approximation factor of the strongly polynomial algorithm that rounds a fractional
solution is 3.
4.1.2 Unrelated machines
In this section we consider the case of k unrelated machines. We rst present a linear programming
formulation. For clarity, we give the LP formulation for polynomially bounded integral inputs.
However, the construction given above that achieves a strongly polynomial algorithm for arbitrary
inputs can be applied here as well. Assume that there are N time slots. For each job J
machine j, dene a variable x itj for each instance [t; t
maximize
subject to:
For each time slot t and machine j:
For each job i, 1  i  n:
For all i, j, and t: 0  x itj  1
The algorithm rounds the fractional solution machine by machine. Let
the rounded solution. When rounding machine i, we rst discard from its fractional solution all
intervals belonging to jobs chosen to S denote the approximation factor that can
be achieved when rounding a single machine. Namely, inputs and
arbitrary inputs.
Theorem 4.4 The approximation factor of the algorithm that rounds a k-machine solution is
Proof: Let F i , 1  i  k, denote the fractional solution of machine i, and let w(F i ) denote its
value. Denote by F 0
i the fractional solution of machine i after discarding all intervals belonging to
jobs chosen to S
We know that for all i, 1  i  k,
c
Adding up all the inequalities, since the sets S i
are mutually disjoint, we get that,
c
Recall that for each job i, the sum of the values of the fractional solution assigned to the intervals
belonging to it in all the machines does not exceed 1. Therefore,
Yielding that
w(S)
In this subsection we apply Theorem 3.3 for the case of weighted jobs and identical machines. We
distinguish between the cases of polynomially bounded integral input and arbitrary input.
Theorem 4.5 There exists an algorithm for the weighted jobs and identical machines case that
achieves an approximation factor of
polynomially bounded integral input, and
, for arbitrary input.
Proof: As shown above, a linear program can be formulated such that the value of its optimal
solution is at least as big as the value of an optimal schedule. Let N 0 be chosen in the same way as
in the discussion preceding Theorem 4.2. We claim that using our rounding scheme, this feasible
solution denes an interval graph that can be colored by (k+1)N 0 1 colors for integral polynomial
size inputs and by (2k colors for arbitrary inputs.
Consider rst the case of integral polynomial size input. In the interval graph that is induced
by the solution of the LP, there are at most N 0 intervals (that correspond to the same job) in
the same group, and at most kN 0 intervals mutually overlap at any point of time. Applying our
group constrained interval coloring, we get a valid coloring with (k Similarly,
for arbitrary inputs, in the interval graph which is induced by the solution of the LP, there are at
most N 0 intervals (that correspond to the same job) in the same group, and at most 2kN 0 intervals
mutually overlap. Applying our group constrained interval coloring, we get a valid coloring with
This implies that polynomial size input and arbitrary
input. In other words, this is the approximation factor that can be achieved with a single machine
when compared to an optimal algorithm that uses k identical machines. Setting these values of
in our paradigm for transforming an algorithm for a single machine to an algorithm for k
identical machines, yields the claimed approximation factors. 2
Remark: Note that as k tends to innity, the approximation factor is e
1:58192 for both
unweighted jobs and for weighted jobs with integral polynomial size inputs. For arbitrary input,
the approximation factor is
e
2:54149. Setting we get that these bounds coincide with
the bounds for a single machine. For every k > 2 and for both cases these bounds improve upon
the bounds for unrelated machines (of 3 and 4).
4.2 A combinatorial algorithm
In this section we present a combinatorial algorithm for the weighted machines model. We rst
present an algorithm for the single-machine version and then we show how to extend it to the case
where there are k > 1 machines, even in the unrelated machines model.
4.2.1 A single machine
The algorithm is inspired by on-line call admission algorithms (see [12, 7]). We scan the jobs
instances (or intervals) one by one. For each job instance, we either accept it, or reject it. We note
that rejection is an irrevocable decision, where as acceptance can be temporary, i.e., an accepted
job may still be rejected at a later point of time. We remark that in the case of non-preemptive
on-line call admission, a constant competitive factor cannot be achieved by such an algorithm. The
reason is that due to the on-line nature of the problem jobs must be considered in the order of
their release time. Our algorithm has the freedom to order the jobs in a dierent way, yielding a
constant approximation factor.
We now outline the algorithm. All feasible intervals of all jobs are scanned from left to right (on
the time axis) sorted by their end points. The algorithm maintains a set A of currently accepted
intervals. When a new interval, I, is considered according to the sorted order, it is immediately
rejected if it belongs to a job that already has an instance in A, and immediately accepted if it
does not overlap with any other interval in A. In case of acceptance, interval I is added to A. If
I overlaps with one or more intervals in A, it is accepted only if its weight is more than  (to be
determined later) times the sum of the weights of all overlapping intervals. In this case, we say that
I \preempts" these overlapping intervals. We add I to A and discard all the overlapping intervals
from A. The process ends when there are no more intervals to scan.
A more formal description of our algorithm, called Algorithm ADMISSION is given in Figure 2.
The main di-culty in implementing the above algorithm is in scanning an innite number of
intervals. After proving the performance of the algorithm we show how to overcome this di-culty.
Informally, we say that an interval I \caused" the rejection or preemption of another interval J ,
Algorithm ADMISSION:
1. Let A be the set of accepted job instances.
Initially,
2. Let I be the set of the yet unprocessed job instances.
Initially, I is the set of all feasible job instances.
3. While I is not empty repeat the following procedure:
Let I 2 J i be the job instance that terminates earliest among all instances in I
and let w be its weight.
Let W be the sum of the weights of all instances I I h in A that overlap I.
(a) I := I n fIg.
(b) If J i \ A 6= ; then reject I.
(c) Else if
A := A [ fIg.
(d) Else if w
W >  then accept I and preempt I
g.
reject I.

Figure

2: Algorithm ADMISSION
if either interval I directly rejected or preempted interval J , or if it preempted another interval that
caused the rejection or preemption of interval J . (Note that this relation is dened recursively, as
an interval I may preempt another interval, that preempted other intervals, which in turn rejected
other intervals. In this case interval I caused the rejection or preemption of all these intervals.)
Fix an interval I that was accepted by the algorithm, and consider all the intervals chosen by the
optimal solution, the rejection or preemption of which was caused by interval I. We prove that the
total weight of these intervals is at most f() times the weight of the accepted interval I, for some
function f . Optimizing , we get the 3
Theorem 4.6 The approximation factor of Algorithm ADMISSION is 3
2.
Proof: Let O be the set of intervals chosen by an optimal algorithm OPT. Let the set of intervals
accepted by Algorithm ADMISSION be denoted by A. For each interval I 2 A we dene a set R(I)
of all the intervals in O that are \accounted for" by I. This set consists of I in case I 2 O, and of
all the intervals in O the rejection or preemption of which was caused by I. More formally:
Assume I is accepted by rule 3(c). Then, the set R(I) is initialized to be I in case I 2 O and
the empty set ;, otherwise.
Assume I is accepted by rule 3(d). Then R(I) is initialized to contain all those intervals from
O that were directly preempted by I and the union of the sets R(I 0 ) of all the intervals I 0
that were preempted by I. In addition, R(I) contains I in case I 2 O.
Assume J 2 O is rejected by rule 3(b). Let I 2 A be the interval that caused the rejection of
J . Note that both I and J belong to the same job. In this case add J to R(I).
Assume J 2 O was rejected by rule 3(e) and let I I h be the intervals in A that overlapped
with J at the time of rejection. Let w be the weight of J and let w j be the weight of I j for
We view J as h imaginary intervals J where the weight of J j is w j w
g. Note that due to the rejection rule it follows that
the weight of J j is no more than  times the weight of I j .
It is not hard to see that each interval from O, or a portion of it if we use rule 3(e), belongs exactly
to one set R(I) for some I 2 A. Thus, the union of all sets R(I) for I 2 A covers O.
We now x an interval I 2 A. Let w be the weight of I and let W be the sum of weights of all
intervals in R(I). Dene
w . Our goal is to bound  from above.
Interval I may directly reject at most one interval from O. Let w r be the weight of (the portion
of) the interval I r 2 O\R(I) that was directly rejected by I, if such exists. Otherwise, let w
Observe that w r  w, since otherwise I r would not have been rejected. Let I 0 2 O be the interval
that belongs to the same job as the one to which I belongs (it maybe I itself), if such exists. By
denition, the weight of I 0 is w. Let W r be the sum of the weights of the rest of the
intervals in R(I). Dene
w . It follow that
We now assume inductively that the  bound is valid for intervals with earlier end point than
the end point of I. Since the overall weight of the jobs that I directly preempted is at most w=, we
get that w
This implies that ++1
. Therefore,
. This equation is minimized for
which implies that
2.
Finally, since the  bound holds for all the intervals in A and since the union of all R(I) sets covers
all the interval taken by OPT, we get that the value of OPT is at most  times the value of A.
Hence, the approximation factor is 3
2. 2
Implementation: Observe that Step (3) of the algorithm has to be invoked only when there is a
\status" change, i.e., either a new job becomes available (n times) or a job in the schedule ends (n
times). Each time Step (3) is invoked the total number of jobs instances that have to be examined
is at most n (at most one for each job). To implement the algorithm we employ a priority queue
that holds intervals according to their endpoint. At any point of time it is enough to hold at most
one job instance for each job in the priority queue. It turns out that the total number of operations
for retrieving the next instance is O(n log n), totalling to O(n 2 log n) operations.
4.2.2 Unrelated machines
If the number of unrelated machines is k > 1, we call Algorithm ADMISSION k times, machine by
machine, in an arbitrary order, where the set of jobs considered in the i-th call does not contain
the jobs already scheduled on machines M . The analysis that shows how the 3
5:828 bound carries over to the case of unrelated machines is very similar to the analysis presented
in the proof of Theorem 4.6. The main dierence is in the denition of R(I). For each interval
I 2 A that was executed on machine M i , we dene the set R(I) to consist of I in case I 2 O,
and of all the intervals that (i) were executed on machine M i in the optimal schedule, and (ii) the
rejection or preemption of these jobs was caused by I.
5 The MAX-SNP hardness
We show that the problem of scheduling unweighted jobs on unrelated machines is MAX-SNP Hard.
This is done by reducing a variant of Max-2SAT, in which each variable occurs at most three times,
to this problem. In this variant of Max-2SAT, we are given a collection of clauses, each consisting
of two (Boolean) variables, with the additional constraint that each variable occurs at most three
times, and the goal is to nd an assignment of values to these variables that would maximize the
number of clauses that are satised (i.e., contain at least one literal that has a \true" value). This
problem is known to be MAX-SNP Hard (cf. [26]).
Given an instance of the Max-2SAT problem we show how to construct an instance of the
problem of unweighted jobs, unrelated machines, such that the value of the Max-2SAT problem is
equal to the value of the scheduling problem. Each variable x i is associated with a machine M i .
Each clause C j is associated with a job. The release time of any job is 0 and its deadline is 3.
The job can be executed only on the two machines corresponding to the variables the clause C j
contains. (In other words, the processing time of the job in the rest of the machines is innite.)
Suppose that clause C j contains a variable x i as a positive (negative) literal. The processing
time of the job corresponding to C j on M i is 3=k, where k 2 f1; 2; 3g is the number of occurrences
of variable x i as a positive (negative) literal. Note that in case variable x i occurs in both positive
and negative forms, it occurs exactly once in one of the forms since a variable x i occurs at most
three times overall. It follows that in any feasible schedule, machine M i cannot execute both a job
that corresponds to a positive literal occurrence and a job that corresponds to a negative literal
occurrence.
We conclude that if m jobs can be scheduled, then m clauses can be satised. In the other
direction, it is not hard to verify that if m clauses can be satised, then m jobs can be scheduled.
Since Max-2SAT with the restriction that each variable occurs at most three times is MAX-SNP
Hard, the unweighted jobs and unrelated machines case is MAX-SNP Hard as well.

Acknowledgment

We are indebted to Joel Wein for many helpful discussions, and especially for his suggestion to
consider the general case of maximizing the throughput of jobs with release times and deadlines.



--R

Scheduling time-constrained communication in linear networks
Minimizing stall time in single and parallel disk systems
Scheduling jobs with


Competitive Bandwidth Allocation with Preemption
On the competitiveness of on-line real-time task scheduling
Scheduling in Computer and Manufacturing Systems
Location of bank accounts to optimize oat
Note on scheduling intervals on-line


Two processor scheduling with start times and deadlines
Computers and Intractability: A Guide to the Theory of NP- Completeness

Patience is a Virtue: The E
Maximizing the value of a space mission
A solvable case of one machine scheduling problem with ready and due dates
An optimal on-line scheduling algorithm for overloaded real-time systems
Sequencing to minimize the weighted number of tardy jobs
A dynamic programming algorithm for preemptive scheduling of a single machine to minimize the number of late jobs
"Sequencing and Schedul- ing: Algorithms and Complexity"
Online interval scheduling
Algorithms for scheduling independent tasks

On the approximation of maximum satis
--TR

--CTR
Cash J. Costello , Christopher P. Diehl , Amit Banerjee , Hesky Fisher, Scheduling an active camera to observe people, Proceedings of the ACM 2nd international workshop on Video surveillance & sensor networks, October 15-15, 2004, New York, NY, USA
Lixin Tang , Gongshu Wang , Jiyin Liu, A branch-and-price algorithm to solve the molten iron allocation problem in iron and steel industry, Computers and Operations Research, v.34 n.10, p.3001-3015, October, 2007
Thomas Erlebach , Klaus Jansen, Implementation of approximation algorithms for weighted and unweighted edge-disjoint paths in bidirected trees, Journal of Experimental Algorithmics (JEA), 7, p.6, 2002
Randeep Bhatia , Julia Chuzhoy , Ari Freund , Joseph (Seffi) Naor, Algorithmic aspects of bandwidth trading, ACM Transactions on Algorithms (TALG), v.3 n.1, February 2007
Thomas Erlebach , Frits C. R. Spieksma, Interval selection: applications, algorithms, and lower bounds, Journal of Algorithms, v.46 n.1, p.27-53, January
Laura Barbulescu , Jean-Paul Watson , L. Darrell Whitley , Adele E. Howe, Scheduling SpaceGround Communications for the Air Force Satellite Control Network, Journal of Scheduling, v.7 n.1, p.7-34, January-February 2004
Julia Chuzhoy , Joseph (Seffi) Naor, New hardness results for congestion minimization and machine scheduling, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, June 13-16, 2004, Chicago, IL, USA
Julia Chuzhoy , Rafail Ostrovsky , Yuval Rabani, Approximation Algorithms for the Job Interval Selection Problem and Related Scheduling Problems, Mathematics of Operations Research, v.31 n.4, p.730-738, November 2006
Amotz Bar-Noy , Reuven Bar-Yehuda , Ari Freund , Joseph (Seffi) Naor , Baruch Schieber, A unified approach to approximating resource allocation and scheduling, Journal of the ACM (JACM), v.48 n.5, p.1069-1090, September 2001
Thomas Erlebach , Klaus Jansen, Conversion of coloring algorithms into maximum weight independent set algorithms, Discrete Applied Mathematics, v.148 n.1, p.107-125,
Amotz Bar-Noy , Sudipto Guha , Yoav Katz , Joseph (Seffi) Naor , Baruch Schieber , Hadas Shachnai, Throughput maximization of real-time scheduling with batching, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.742-751, January 06-08, 2002, San Francisco, California
Julia Chuzhoy , Joseph (Seffi) Naor, New hardness results for congestion minimization and machine scheduling, Journal of the ACM (JACM), v.53 n.5, p.707-721, September 2006
Reuven Bar-Yehuda , Keren Bendel , Ari Freund , Dror Rawitz, Local ratio: A unified framework for approximation algorithms. In Memoriam: Shimon Even 1935-2004, ACM Computing Surveys (CSUR), v.36 n.4, p.422-463, December 2004
Faisal Z. Qureshi , Demetri Terzopoulos, Surveillance camera scheduling: a virtual vision approach, Proceedings of the third ACM international workshop on Video surveillance & sensor networks, November 11-11, 2005, Hilton, Singapore
parallel machines scheduling;approximation algorithms;throughput;multiple machines scheduling;scheduling;real-time scheduling