A Polynomial Time Approximation Scheme for General Multiprocessor Job Scheduling.
Recently, there have been considerable interests in the multiprocessor job scheduling problem, in which a job can be processed in parallel on one of several alternative subsets of processors.  In this paper, a polynomial time approximation scheme is presented for the problem in which the number of processors in the system is a fixed constant.  This result is the best possible because of the strong NP-hardness of the problem and is a significant improvement over the past results: the best previous result was an approximation algorithm of ratio $7/6 + \epsilon$ for 3-processor systems based on Goemans's algorithm for a restricted version of the problem.
Introduction
. One of the assumption made in classical scheduling theory is
that a job is always executed by one processor at a time. With the advances in parallel
algorithms, this assumption may no longer be valid for job systems. For example, in
semiconductor circuit design workforce planning, a design project is to be processed
by a group of people. The project contains n jobs, and each job can be worked
on by one of a set of alternatives, where each alternative consists of one or more
persons in the group working simultaneously on the particular job. The processing
time of each job depends on the subgroup of people being assigned to handle the
job. Note that the same person may belong to several different subgroups. Now the
question is how we can schedule the jobs so that the project can be finished as early
as possible. Other applications include (i) the berth allocation problem [21] where
a large vessel may occupy several berths for loading and unloading, (ii) diagnosable
microprocessor systems [20] where a job must be performed on parallel processors in
order to detect faults, (iii) manufacturing, where a job may need machines, tools, and
people simultaneously, and (iv) scheduling a sequence of meetings where each meeting
requires a certain group of people [11]. In the scheduling literature [17], this kind of
problems are called multiprocessor job scheduling problems.
Among the others, two types of multiprocessor job scheduling problems have
been extensively studied [7, 22]. The first type is the Pm jfixjC max problem, in which
the subset of processors and the processing time for parallel processing each job are
fixed. The second type is a more general version, the Pm jsetjC max problem, in which
each job may have a number of alternative processing modes and each processing
mode specifies a subset of processors and the job processing time on that particular
processor subset. The objective for both problems is to construct a scheduling of
minimum makespan on the m-processor system for a given list of jobs. The jobs are
supposed to be non-preemptive.
Approximability of the multiprocessor job scheduling problems has been studied.
The problem is a generalized version of the classical job scheduling prob-
Department of Computer Science, Texas A&M University, College Station,
Email: chen@cs.tamu.edu. Supported in part by the National Science Foundation under Grant
CCR-9613805.
y Department of Computer Science, Bucknell University, Lewisburg, Pennsylvania 17837, Email:
amiranda@eg.bucknell.edu.
J. CHEN and A. MIRANDA
lem on a 2-processor system [13], thus it is NP-hard. Hoogeveen et al. [18] showed
that the P 3 jfixjC max problem (thus also the P 3 jsetjC max problem) is NP-hard in the
strong sense thus it does not have a fully polynomial time approximation scheme
5]). Blazewicz et al. [4] developed a polynomial time approximation
algorithm of ratio 4=3 for the problem P 3 jfixjC max , which was improved
later by Dell'Olmo et al. [10], who gave a polynomial time approximation algorithm of
ratio 5=4 for the same problem. Both algorithms are based on the study of a special
type of schedulings called normal schedulings. Goemans [14] further improved the
algorithms by giving a polynomial time approximation algorithm of ratio 7=6 for the
recently, Amoura et al. [1] developed a polynomial time
approximation scheme for the problem Pm jfixjC max for every fixed integer m.
Approximation algorithms for the Pm jsetjC max problem were not as successful as
that for the Pm jfixjC max problem. Bianco et al. [3] presented a polynomial time
approximation algorithm for the Pm jsetjC max problem whose approximation ratio is
bounded by m. Chen and Lee [8] improved their algorithm by giving a polynomial
time approximation algorithm for the Pm jsetjC max problem with an approximation
showed that the problem P 3 jsetjC max can be approximated
in polynomial time with a ratio 7=6 ffl. Before the present paper, it was
unknown whether there is a polynomial time approximation algorithm with ratio c
for the problem Pm jsetjC max , where c is a constant independent of the number m of
processors in the system.
In this paper, we present a polynomial time approximation scheme for the problem
Pm jsetjC max . Our algorithm combines the techniques developed by Amoura et
al. [1], who split jobs into large jobs and small jobs, and the techniques developed by
Bell'Olmo et al. [10] and Goemans [14] on normal schedulings, plus the standard dynamic
programming and scaling techniques. More precisely, based on a classification
of large jobs and small jobs, we introduce the concept of (m; ffl)-canonical schedulings,
which can be regarded as a generalization of the normal schedulings. We show that
for any job list, there is an (m; ffl)-canonical scheduling whose makespan is very close
to the optimal makespan. Then we show how this (m; ffl)-canonical scheduling can be
approximated. Combining these two steps gives us a polynomial time approximation
scheme for the Pm jsetjC max problem.
Our result is the best possible in the following sense: because the problem
Pm jsetjC max is NP-hard in the strong sense, it is unlikely that our algorithm can
be further improved to a fully polynomial time approximation scheme [13]. More-
over, the polynomial time approximation scheme cannot be extended to the more
general problem P jsetjC max , in which the number m of processors in the system is
given as a parameter in the input: it can be shown that there is a constant
such that the problem P jsetjC max has no polynomial time approximation algorithms
whose approximation ratio is bounded by n ffi [23].
The paper is organized as follows. Section 2 gives necessary background and
preliminaries for the problem. In section 3 we introduce (m; ffl)-canonical schedulings
and study their properties. Section 4 presents the polynomial time approximation
scheme for the problem Pm jsetjC max , and section 5 concludes with some remarks and
further research directions.
2. Preliminaries. The Pm jsetjC max problem is a scheduling problem minimizing
the makespan for a set of jobs, each of which may have several alternative processing
modes. More formally, an instance J of the problem Pm jsetjC max is a list of jobs:
each job J i is associated with a list of alternative processing
modes: Each processing mode (or simply mode) M ij is specified
by a a subset of processors in the m-processor system and
ij is an integer indicating the parallel processing time of the job J i on the processor
In case there is no ambiguity, we also say that the processor set Q ij is a
mode for the job J i . For each job J
min i be the . The value min i will be called the
minimum parallel processing time for the job J i .
Given a list of jobs, a scheduling \Gamma(J ) of J on the m-processor
system consists of two parts: (1) determination of a processing mode for each job
J i in J ; and (2) determination of the starting execution time for each job under the
assigned mode so that at any moment, each processor in the system is used for (maybe
parallel) processing at most one job (assuming that the system starts at time
The makespan of the scheduling \Gamma(J ) is the latest finishing time of a job in J under
the scheduling \Gamma(J ). Let Opt(J ) denote the minimum makespan over all schedulings
for J . The Pm jsetjC max problem is for a given instance J to construct a scheduling
of makespan Opt(J ) for J .
Let Pm be the set of the m processors in the m-processor system. A collection
k g of k nonempty subsets of Pm is a k-partition of Pm if
collection of subsets of Pm is a partition of Pm if it is
a k-partition for some integer k  1. The total number Bm of different partitions of
the set Pm is called the mth Bell number [16]. Using the formula of Comtet [9], we
have
A looser but simpler upper bound for Bm , Bm  m!, can be easily proved by induction.
Another combinatorial fact we need for analysis of our scheduling algorithm is
the "cut-index" in a nonincreasing sequence of integers.
Lemma 2.1. Let be a nonincreasing sequence of integers, let
be a fixed integer and ffl ? 0 be an arbitrary real number. Then there is an
(with respect to m and ffl) such that
is an integer; and
(2) for any subset T 0 of at most 3j 0 mBm integers t q in T with q ? j 0 , we have
Proof. To simplify expressions, let b 1. Decompose the sum
4 J. CHEN and A. MIRANDA
Since
there are at most bm=fflc subsums A j larger than
be the first subsum such that A k+1  (ffl=m)
. Since the sum of the first b k+1
integers t q in T with q ?
m is bounded by (ffl=m)
(ffl=m)
and the sequence is nonincreasing, we conclude that for any subset
T 0 of T of at most 3j 0 mBm integers t q with q ? j 0 , we must have
This completes the proof.
For the nonincreasing sequence T of integers, we will denote by j m;ffl the smallest
index that satisfies conditions (1) and (2) in Lemma 2.1. The index j m;ffl will be called
the cut-index for the sequence T .
3. On (m; ffl)-canonical schedulings. In this section, we first assume that the
mode assignment for each job in the instance J is decided, and discuss how we
schedule the jobs in J under the mode assignment to the processor set Pm . By this
assumption, the job list J is actually an instance for the Pm jfixjC max problem (recall
that the Pm jfixjC max problem is the problem Pm jsetjC max with the restriction that
every job in an instance has only one processing mode).
be an instance for the Pm jfixjC max problem, where each
job J i requires a fixed set Q i of processors for parallel execution with processing time
loss of generality, assume that the processing time
sequence is nonincreasing.
For the fixed number m of processors in the system, and for an arbitrarily given
real number ffl ? 0, let j m;ffl be the cut-index for the sequence T , as defined in
Lemma 2.1. That is, is an integer bounded by bm=fflc,
and for any subset T 0 of at most 3j m;ffl mBm integers t q in T with q ? j m;ffl , we have
We split the job set J into two subsets:
(1)
The jobs in JL will be called large jobs and the jobs in JS will be called small jobs.
Let \Gamma(J ) be a scheduling for the job set J . Consider the nondecreasing sequence
of integers, where  h,
are the starting or finishing times of the j m;ffl large jobs in \Gamma(J ). A small job block
in \Gamma(J ) consists of a subset P 0 ' Pm of processors and a time interval [
such that the subset of processors are exactly those that are
executing large jobs in the time interval [ will be called
the height and the processor set P 0 will be called the type of the small job block .
Therefore, the subset P 0 of processors associated with the small job block  are
those processors that are either idle or used for executing small jobs in the time
interval Note that the small job block  can be of height 0 when
The small job block of time interval [ is the latest finish time
of a large job, will be called the "last small job block". Note that the last small job
block has type Pm .
Let  be a small job block associated with a processor set P 0 and a time interval
The small job block at any time moment  in the time interval [
can be characterized uniquely as a collection [Q of pairwise disjoint subsets
of the processor set P 0 such that at the time  , for processors in
the subset Q i are used for parallel execution on the same small job (thus, the subset
is the subset of idle processors at time  ). The collection [Q
will be called the type of the time moment  . A layer in the small job block  is a
such that all time moments  between  i
and  j are of the same type. The type of the layer is equal to the type of any time
moment in the layer and the height of the layer is
Let L 1 and L 2 be two layers in the small job block  of types [Q
respectively. We say that layer L 1 covers layer L 2 if fR
g. In particular, if L 1 and L 2 are two consecutive layers in the small job
block  such that layer L 2 starts right after layer L 1 finishes and L 1 covers L 2 , then
layer L 2 is actually a continuation of the layer L 1 with some of the small jobs finished.
Definition 3.1. A floor oe in the small job block  is a sequence fL
of consecutive layers such that (1) for h, layer L i starts right after layer
and (2) all small jobs interlacing layer
in layer L 1 and all small jobs interlacing layer L h finish in layer L h .
An example of a floor is given in Figure 1(a). Note that a small job block may
not have any nonempty floor at all, as shown in Figure 1(b).
Remark 1. There are a few important properties of floors in a small job block.
Suppose that the layer L 1 starts at time  1 while layer L h finishes at time  2 . Then
by property (2) in the definition, no small jobs cross the floor boundaries  1 and  2 .
Therefore, the floor oe can be regarded as a single job that uses the processor set P 0 ,
starts at time  1 and finishes at time  2 . The height of the floor oe is defined to be
which is equal to the sum of the heights of the layers L 1 Secondly,
since all floors in the small job block  are for the same processor subset P 0 and
there are no small jobs crossing the starting and finishing times of any floors, the
floors in the same small job block  can be rearranged in any order but can still fit
into the small job block without exceeding the height of the small job block. Finally,
property (1) in the definition ensures that no matter how the small jobs in a floor are
rearranged, a simple greedy algorithm is sufficient to refit the small jobs into the floor
without exceeding the floor height. The greedy algorithm is based on the idea of the
well-known Graham's scheduling algorithm for the classical job scheduling problem
[15].
Definition 3.2. Let J be an instance of the problem Pm jfixjC max and let  be
any permutation of the jobs in J . The list scheduling algorithm based on the ordering
is to schedule each job J i of mode Q i in J , following the ordering of , at the
earliest time when the processor subset Q i becomes available.
Lemma 3.3. Let J oe be the set of small jobs in the floor oe. The list scheduling
algorithm based on any ordering  of the jobs in J oe will always reconstruct the floor
oe.
Proof. Suppose that the first layer L 1 in the floor oe is of type
According to property (1) in the definition, every job in J oe must have a mode Q i
for some i. By the definition, each layer covers the layer L j , therefore, in the
floor oe, no processor subset Q i can become idle before its final completion time. Now
6 J. CHEN and A. MIRANDA
(b)
c
small
job
block
(a)
small
job
block
c
floor
s
Fig. 1. (a) A floor fL1 ; L2 ; L3g; (b) a small job block with no floor.
since the subsets Q are pairwise disjoint, the jobs of mode Q i in J oe can be
executed by the processor subset Q i in any order without changing the completion
time of Q i . Therefore, regardless of the ordering of the jobs in J oe , as long as the list
scheduling algorithm starts each job at its earliest possible time (thus no subset
can become idle before its final completion time), the completion time for each subset
will not be changed. Therefore, the list scheduling algorithm will construct a floor
with exactly the same layers L 1
Definition 3.4. Let [Q be a partition of the processor subset P 0 . We
say that we can assign the type [Q to a floor if the type of
the layer L 1 is a subcollection of fQ g.
Note that it is possible that we can assign two different types to the same floor as
long as the type of the floor is a subcollection of the assigned floor types. For example,
let be a partition of the processor subset P 0 . If the first layer L 1 in a
floor oe is of type [Q then we can assign either type
to the floor oe.
Definition 3.5. A small job block  is a tower if it is constituted by a sequence
of floors such that we can assign types to the floors so that no two floors in the tower
are of the same type.
Note that since each floor type is a partition of the processor subset P 0 , a tower
contains at most Bm floors, where Bm , the mth Bell number, is the number of different
partitions of a set of m elements.
In our discussion, we will be concentrating on schedulings of a special form, in
the following sense.
Definition 3.6. Let J be an instance of the problem Pm jfixjC max , which is
divided into large job set JL and small job set JS as given in Equation (1) for a fixed
fixed constant ffl ? 0. A scheduling \Gamma(J ) of J is (m; ffl)-canonical
if every small job block in \Gamma(J ) is a tower.
Remark 2. Note that in an (m; ffl)-canonical scheduling, no small jobs cross the
boundary of a tower. Therefore, a tower of height t and associated with a processor
set Q can be simply regarded as a job of mode (Q; t).
We first show that an (m; ffl)-canonical scheduling \Gamma(J ) of J can be constructed
by the list scheduling algorithm when large jobs and towers in \Gamma(J ) are given in a
proper order.
Lemma 3.7. Let \Gamma(J ) be an (m; ffl)-canonical scheduling for the job set J . Let
be the sequence of the large jobs and towers in \Gamma(J ), ordered in terms of their
starting times in \Gamma(J ). Then the list scheduling algorithm based on the ordering ,
which regards each tower as a single job, constructs a scheduling of J with makespan
not larger than that of \Gamma(J ).
Proof. Let be any prefix of the ordered sequence , where each
J j is either a large job or a tower. Let \Gamma(J i ) be the scheduling of J i obtained from
\Gamma(J ) by removing all large jobs and towers that are not in J i , and let \Gamma 0 (J i ) be the
scheduling by the list scheduling algorithm on the jobs in J i . It suffices to prove
that for all i, the completion time of any processor in \Gamma 0 (J i ) is not larger than the
completion time of the same processor in \Gamma(J i ). We prove this by induction on i.
The case Now suppose that the mode for the job (or tower)
requires the processor subset Q i+1 for parallel processing time t i+1 . Let  be
the earliest time in the scheduling \Gamma(J i ) at which the processor subset Q
available and let  0 be the earliest time in the scheduling \Gamma 0 (J i ) at which the processor
subset available. The list scheduling algorithm will start J i+1 at time
thus in the scheduling \Gamma 0 (J i+1 ), the completion time of each processor in the subset
. On the other hand, in the scheduling \Gamma(J i+1 ), the job J i+1
cannot start earlier than  since according to the definition of the ordered sequence
, J i+1 cannot start until all jobs in J i have started. Therefore, in the scheduling
\Gamma(J i+1 ), the completion time of each processor in Q i+1 is at least  which is
not smaller than  since the inductive hypothesis assumes that    0 . Finally,
for each processor not in the subset Q i+1 , the completion time in \Gamma 0 (J i+1 ) is equal to
that in \Gamma 0 (J i ), which by the induction is not larger than that in \Gamma(J i ), which is equal
to the completion time of the same processor in \Gamma(J i+1 ).
Thus, once the ordering of large jobs and towers is decided, it is easy to construct
a scheduling that is not worse than the given (m; ffl)-canonical scheduling. In the
following, we will prove that for any instance J for the problem Pm jfixjC max , there is
an (m; ffl)-canonical scheduling whose makespan is very close to the optimal makespan.
Theorem 3.8. Let J be an instance for the problem Pm jfixjC max . Then for
any ffl ? 0, there is an (m; ffl)-canonical scheduling \Gamma(J ) of J such that the makespan
of \Gamma(J ) is bounded by (1
Proof. be an optimal scheduling of makespan Opt(J ) for J . We
construct an (m; ffl)-canonical scheduling for J based on the optimal scheduling
8 J. CHEN and A. MIRANDA
Let JL and JS be the set of large jobs and the set of small jobs in J , respectively,
according to the definition in Equation (1). Consider a small job block  in the
scheduling
Assume that the small job block  is associated with a processor set P 0 of r
processors, r  m, and a time interval [ be the list of all
partitions of the processor set P 0 , where We divide the layers in the
small job block  into groups, each corresponding to a partition of P 0 , as follows.
A layer of type T 0 is put in the group corresponding to a partition T j if T 0 is a
subcollection of T j . Note that a layer type T 0 may be a subcollection of more than
one partition of P 0 . In this case, we put the layer arbitrarily into one and only one of
the groups to ensure that each layer belongs to only one group.
For each partition T j of P 0 , we construct a floor frame oe j whose type is T j and
height is equal to the sum of heights of all layers belonging to the group corresponding
to the partition T j . Note that so far we have not actually assigned any small jobs to
any floor frames oe 1 yet. Moreover, since each layer belongs to exactly one of
the groups, it is easy to see that the sum
of the heights of the floor
frames oe 1 is equal to the sum of the heights of all layers in the small job block
, which is equal to the height of the small job block .
The construction for the floor frames for the last small job block in \Gamma 1 (J ) is
slightly different: for which we only group layers in which not all processors are idle.
Thus, the sum of the heights of all floor frames in the last small job block is equal to
is the latest finish time for some large job in the scheduling
After the construction of the floor frames for each small job block in the scheduling
the small jobs in JS to the floor frames using the following greedy
method. For each small job J that requires a parallel processing by a processor subset
Q, we assign J to an arbitrary floor frame oe in a small job block as long as the floor
frame oe satisfies the following conditions: (1) the type of the floor frame oe contains
the subset Q; and (2) adding the job J to oe does not exceed the height of the floor
frame oe (if there are more than one floor frames satisfying these conditions, arbitrarily
pick one of them). Note that we assign a job to a floor frame only when the mode
of the job is contained in the type of the floor frame. Therefore, this assignment will
never leave a "gap" between two jobs in the same floor frame.
The above assignment of small jobs in JS to floor frames stops when none of the
small jobs left in JS can be assigned to any of the floor frames according to the above
rules. Now each floor frame becomes a floor.
For each small job block  in \Gamma 1 (J ), let S be the set of floor frames in . Since
the height of a resulting floor is not larger than the height of the corresponding floor
frame, the sum of the heights of the floors resulting from the floor frames in S is
not larger than the height of the small job block . Therefore, we can put all these
floors into the small job block  (in an arbitrary order) to make  a tower. Doing this
for all small job blocks in \Gamma 1 (J ) gives an (m; ffl)-canonical scheduling
the job set JL [ J 0
S is the set of small jobs that have been assigned to the
floor frames in the above procedure. The makespan of the scheduling
is bounded by Opt(J ). Now the only thing left is that we still need to schedule the
small jobs that have not been assigned to any floor frames. Let J 00
S be the
set of small jobs that are not assigned to any floor frames by the above procedure.
We want to demonstrate that there are not many jobs in the set J 00
S .
By the definition, the number of small job blocks in the scheduling \Gamma 1 (J ) is
2j m;ffl +1  3j m;ffl . Since each small job block is associated with at most m processors,
the number of floor frames constructed in each small job block is bounded by Bm .
Therefore, the total number of floor frames we constructed from the scheduling
is bounded by 3Bm j m;ffl . Moreover, each floor type is a collection of at most m
processor subsets.
If the set J 00
contains more than 3mBm j m;ffl small jobs, then there must be a
subset Q of processors such that the number of small jobs of mode Q in J 00
S is larger
than the number of the constructed floor frames whose type contains the subset Q.
be the set of floor frames whose type contains the subset Q.
By our assignment rules, assigning any job of mode Q in J 00
S to a floor frame in
would exceed the height of the corresponding floor frame. Since there
are more than d small jobs of mode Q in J 00
S , the sum of processing times of all small
jobs of mode Q in JS is larger than
On the other hand, by our
construction of the floor frames in each small job block , the sum of the heights of
the floor frames in  whose type contains Q should not be smaller than the sum of
the heights of the layers in  whose type contains Q. Summarizing this over all small
job blocks, we conclude that the sum
smaller than the sum
of processing times of all small jobs of mode Q in JS (since each small job of mode
Q must be contained in consecutive layers whose type contains Q). This derives a
contradiction. The contradiction shows that there are at most 3mBm j m;ffl small jobs
in the set J 00
S .
Now we assign the small jobs in J 00
S to the floor frames in the last small job block
in the scheduling \Gamma 2 (JL [J 0
S ). For each small job J of mode Q in J 00
S , we arbitrarily
assign J to a floor frame whose type contains Q in the last small job block, even this
assignment exceeds the height of the floor frame. Note that the last small job block
is associated with the whole processor set Pm , so for any mode Q, there must be a
floor frame in the last small job block whose type contains the processor subset Q.
This procedure stops with all small jobs in J 00
S assigned to floor frames in the last
small job block. It is easy to see that the resulting scheduling is an (m; ffl)-canonical
scheduling of the original job set J . Moreover, since the makespan of the
scheduling
S ) is bounded by Opt(J ), the makespan of the (m; ffl)-canonical
scheduling \Gamma 3 (J ) is bounded by
where t(J) is the parallel processing time of the small job J . Since there are at most
small jobs in the set J 00
S , by Lemma 2.1,
It is easy to see that Opt(J )  (
Therefore, the makespan of the (m; ffl)-
canonical scheduling \Gamma 3 (J ) is bounded by (1 This completes the proof
of the theorem.
Before we close this section, we introduce one more definition.
Definition 3.9. Let oe be a floor of type
are pairwise disjoint subsets of processors in the processor set Pm . Then each
subset plus the height l is called a room in the floor oe, whose type is Q i .
J. CHEN and A. MIRANDA
4. The approximation scheme. Now we come back to the original problem
Pm jsetjC max . Recall that an instance J of the problem Pm jsetjC max is a set of jobs
each job J i is given by a list of alternative processing modes
in which the pair (Q specifies the parallel processing
time t i;j of the job J i on the subset Q i;j of processors in the m-processor system.
In order to describe our polynomial time approximation scheme for the problem,
let us first discuss why this problem is more difficult than the classical job scheduling
problem.
In the classical job scheduling problem, each job is executed by one processor in
the system. Therefore, the order of executions of jobs in each processor is not crucial:
the running time of the processor is simply equal to the sum of the processing times
of the jobs assigned to the processor. Therefore, the decision of which job should
be assigned to which processor, in any order, will uniquely determine the makespan
of the resulting scheduling. This makes it possible to use a dynamic programming
approach that extends a scheduling for a subset of jobs to that for a larger subset.
The situation in the general multiprocessor job scheduling problem Pm jsetjC max ,
on the other hand, is more complicated. In particular, the makespan of a scheduling
depends not only on the assignment of processing modes to jobs, but also on the order
in which the jobs are executed. Therefore, the techniques of extending a scheduling
for a subset of jobs in the classical job scheduling problem are not directly applicable
here.
Theorem 3.8 shows that there is an (m; ffl)-canonical scheduling whose makespan
is very close to the optimal makespan. Therefore, constructing a scheduling whose
makespan is not larger than the makespan of a good (m; ffl)-canonical scheduling will
give a good approximation to the optimal schedulings.
Nice properties of an (m; ffl)-canonical scheduling are that within the same tower,
the order of the floors does not affect the height of the tower, and that within the same
floor, the order of the small jobs does not affect the height of the floor (see Remark
1 and Remark 2 in the previous section). Therefore, the only factor that affects the
heights of towers and floors are the assignments of jobs to towers and floors. This
makes it become possible, at least for small jobs, to apply the techniques in classical
job scheduling problem to our current problem. This is described as follows.
First suppose that we can somehow divide the job set J into large job set JL
and small job set JS . Let us start with an (m; ffl)-canonical scheduling \Gamma(J ) of the
set J . The scheduling \Gamma(J ) gives a nondecreasing sequence f of
integers, where  are the starting
or finishing times of the j m;ffl large jobs in JL . Let the corresponding towers
be g, where the tower  j consists of a subset P 0
j of processors and the
We suppose that the subset P 0
j of processors associated with each tower  j is
known, and that the large jobs and towers of the scheduling \Gamma(J ) are ordered into a
sequence  in terms of their starting times. However, we assume that the assignment
of small jobs to the rooms of the scheduling \Gamma(J ) is unknown. We show how this
information can be recovered.
For each tower  j associated with the processor set P 0
, the number of floors in
the tower  j is q r is the number of processors in the set P 0
.
Let oe j;1 be the floors of all possible different types in the tower  j . For
each floor oe j;q , let fl j;q;1 jq be the rooms in the floor oe j;q , where r jq  m.
Therefore, the configuration of the small jobs in the (m; ffl)-canonical scheduling \Gamma(J )
Algorithm. Schedule-Small
Input: The set JS of small jobs and an order  of the large jobs
and towers in \Gamma(J )
Output: A scheduling for the job set J
1.
2. for to nS do
for each mode Q ij of the small job J 0
for each True such that the job J 0
under mode Q ij is addable to the room fl j;q;r
3. for each
call the list scheduling algorithm based on the order  to
construct a scheduling for J in which the room fl j;q;r has
running time t j;q;r for all t j;q;r  0;
4. return the scheduling constructed in step 3 with the minimum makespan.
Fig. 2. Scheduling small jobs in floors
can be specified by a ((2j m;ffl
where t j;q;r specifies the running time of the room fl j;q;r (for index fj; q; rg for which
the corresponding room fl j;q;r does not exists, we can simply set t
Suppose that an upper bound T 0 for the running time of rooms is derived, then
we can use a Boolean array D of (2j m;ffl dimensions to describe the
configuration of a subset of small jobs in a scheduling:
-z
is the number of small jobs in J , such that
if and only if there is a scheduling on the first i small jobs to the floors in \Gamma(J ) such
that the running time of the room fl j;q;r is t j;q;r (recall that the running time of a
room is dependent only on the assignment of small jobs to the room and independent
of the order in which the small jobs are executed in the room). Initially, all array
elements in the array
Suppose that a configuration of a scheduling for the first small jobs is given
(2)
We say that the ith small job J 0
under mode Q i is addable to a room fl j;q;r in the
configuration in (2) if the room fl j;q;r is of type Q i and adding the job J 0
i to the room
does not exceed the upper bound T 0 of the running time of the room fl j;q;r .
Now we are ready to present our dynamic programming algorithm for scheduling
small jobs into the rooms in the (m; ffl)-canonical scheduling \Gamma(J ). The algorithm is
given in Figure 2.
Note that the algorithm Schedule-Small may not return an (m; ffl)-canonical
scheduling for the job set J . In fact, there is no guarantee that the height of the towers
constructed in the algorithm does not exceed the height of the corresponding towers
J. CHEN and A. MIRANDA
in the original (m; ffl)-canonical scheduling \Gamma(J ). However, we can show that the
scheduling constructed by the algorithm Schedule-Small has its makespan bounded
by the makespan of the original (m; ffl)-canonical scheduling \Gamma(J ).
Lemma 4.1. For all i, 0  i  nS , the array element
if and only if there is a way to assign modes to the first i small jobs and arrange them
into the rooms such that the room fl j;q;r has running time t j;q;r for all fj; q; rg.
Proof. We prove the lemma by induction on i. The case can be easily
verified.
Suppose that there is a way W to assign modes to the first i small jobs and
arrange them into the rooms such that the room fl j;q;r has running time t j;q;r for all
rg. Suppose that W assigns the ith small job J 0
i of processing time t ij to the
room
of Removing the job J 0
i from W , we obtain a way that assigns
modes to the first arrange them into the rooms such that the
room fl j;q;r has running time t j;q;r for all fj; q; rg 6= and the room fl j0 ;q 0 ;r 0
has running time t j0 ;q 0 ;r 0
. By the inductive hypothesis, we have
Now in the ith execution of the for loop in step 2 in the algorithm Schedule-Small,
when the mode of the small job J 0
i is chosen to be Q ij with processing time t ij , the
algorithm will assign
The other direction of the lemma can be proved similarly. We omit it here.
The above lemma gives us directly the following corollary.
Corollary 4.2. If the sequence  of large jobs and towers is ordered in terms
of their starting times in the (m; ffl)-canonical scheduling \Gamma(J ), then the algorithm
Schedule-Small constructs a scheduling for job set J whose makespan is bounded
by the makespan of the (m; ffl)-canonical scheduling \Gamma(J ).
Proof. Note that the (m; ffl)-canonical scheduling \Gamma(J ) gives a way to assign
and arrange all small jobs in JS into the rooms. According to Lemma 4.1, the
corresponding array element in the array D must have value True:
For this array element, step 3 of the algorithm will construct the towers that have exactly
the same types and heights as their corresponding towers in the (m; ffl)-canonical
scheduling \Gamma(J ) (this may not give exactly the same assignment of small jobs to
rooms. However, the running times of the corresponding rooms must be exactly the
same). Now since the sequence  is given in the order sorted by the starting times of
the large jobs and towers in the (m; ffl)-canonical scheduling \Gamma(J ), by Lemma 3.7, the
call in step 3 to the list scheduling algorithm based on the order  and this configuration
will construct a scheduling whose makespan is not larger than the makespan
of the (m; ffl)-canonical scheduling \Gamma(J ).
Finally, since step 4 of the algorithm returns the scheduling of the minimum
makespan constructed in step 3, we conclude that the algorithm returns a scheduling
whose makespan is not larger than the makespan of \Gamma(J ).
We analyze the algorithm Schedule-Small.
Lemma 4.3. Let T 0 be the upper bound used by the algorithm Schedule-Small
on the running time of the rooms. Then the running time of the algorithm Schedule-
Small is bounded by O(n2 m  m;ffl T  m;ffl
Proof. The number nS of small jobs in JS is bounded by the total number n of
jobs in J , each small job may have at most 2 different modes. Also as we
indicated before, the number of rooms is bounded by
the running time for each room is bounded by T 0 , for each fixed i, there cannot be more
than T  m;ffl
Finally, for each
we can check each of the  m;ffl component values t j;q;r to decide if the job J 0
under
is addable to the room fl j;q;r . In conclusion, the running time of step 2 in
the algorithm Schedule-Small is bounded by
O(n
We will also attach the mode assignment and room assignment of the job J 0
to each element True. With this information, from a given
configuration True, a corresponding scheduling for the small
jobs in the rooms can be constructed easily by backtracking the dynamic programming
procedure and its makespan can be computed in time  m;ffl . Therefore, step 3 of the
algorithm takes time
In conclusion, the running time of the algorithm Schedule-Small is bounded
by O(n2 m  m;ffl T  m;ffl
We now discuss how an upper bound T 0 for the running time of rooms can
be derived. Given an instance of the problem Pm jsetjC max
and a positive real number ffl ? 0, where each job J i is specified by a list of alternative
processing modes J Recall that
g. Then the sum T
obviously an
upper bound on the makespan of the (m; ffl)-canonical schedulings for J (T 0 is the
makespan of a straightforward scheduling that assigns each job J i the mode corresponding
to min i then starts each job J i when the previous job J finishes. There-
fore, if no (m; ffl)-canonical scheduling has makespan better than T 0 , we simply return
this straightforward scheduling). In particular, the value is an upper bound for the
running time for all rooms. Moreover, since the job set J takes at least T 0 amount of
"work" (the work taken by a job is equal to the parallel processing time multiplied by
the number of processors involved in this processing) and the system has m processors,
the value T 0 also provides a lower bound for the optimal makespan Opt(J
In order to apply algorithm Schedule-Small, we need to first decide how the
set J is split into large job set JL and small job set JS , what are the modes for the
large jobs, what are the types for the towers, and what are the ordering  for the large
jobs and towers on which the list scheduling algorithm can be applied. According to
Lemma 2.1, the number of large jobs is of form j
k  bm=fflc, and by the definition, the number of towers is 2j m;ffl + 1. When m and
ffl are fixed, the number of large jobs and the number of towers are both bounded
by a constant. Therefore, we can use any brute force method to exhaustively try all
possible cases.
To achieve a polynomial time approximation scheme for the problem Pm jsetjC max ,
we combine the standard scaling techniques [19] with the concept of (m; ffl)-canonical
schedulings, as follows.
14 J. CHEN and A. MIRANDA
Algorithm. Approx-Scheme
Input: An instance J for the problem Pm jsetjCmax and
Output: A scheduling of J
2. let J 0 be the job set obtained by scaling the job set J by K;
3. for to bm=fflc do
3.1. for each subset J 0
L of j 0 jobs in J 0
3.2. for each mode assignment A to the jobs in J 0
3.3. for each possible sequence of 2j0
3.4. for each ordering  of the j 0 jobs in J 0
L and the 2j0
call Schedule-Small on small job set J 0
S and the ordering
to construct a scheduling for the job set J 0 (use T 0
as the upper bound for the running time of rooms);
4. be the scheduling constructed in step 3 with the
minimum makespan;
5. replace each job J 0
by the corresponding job J i to obtain
a scheduling \Gamma 0 (J ) for the job set J ;
6. return the job scheduling \Gamma 0 (J ).
Fig. 3. The approximation scheme
be an instance of the Pm jsetjC max problem, where J
We let construct another
instance
n g for the problem, where J 0
That is, the jobs in J 0 are identical to those in J except that all
processing times t ij are replaced by bt ij =Kc. We say that the job set J 0 is obtained
from the job set J by scaling the processing times by K. We apply the algorithm
discussed above to the instance J 0 to construct a scheduling for J 0 from which a
scheduling for J is induced. The formal algorithm is presented in Figure 3.
We explain how step 5 converts the scheduling \Gamma 0 (J 0 ) for the job set J 0 into a
scheduling for the job set J . We first multiply the processing time and the
starting time of each job J 0
i in the scheduling \Gamma 0 (J 0 ) by K (but keeping the processing
mode). That is, for the job J 0
i of mode Q ij and processing time bt ij =Kc that starts at
time  i in \Gamma 0 (J 0 ), we replace it by a job J 00
i of mode Q ij and processing time K
and let it start at time K i . This is equivalent to proportionally "expanding" the
scheduling K. Now on this expansion of the scheduling \Gamma 0 (J 0 ),
following the order in terms of their finish times, we do "correction" on processing
times by increasing the processing time of each job J 00
i from K
that this increase in processing time may cause many jobs in the scheduling to delay
their starting time by units. In particular, this increase may cause
the makespan of the scheduling to increase by units.) After the
corrections on the processing time for all jobs in J , we obtain a scheduling \Gamma 0 (J ) for
the job set J .
Lemma 4.4. For fixed m  2 and ffi ? 0, The running time of the algorithm
Approx-Scheme for the problem Pm jsetjC max is bounded by O(n  m;ffl +j m;ffl +1 ), where
Proof. Since the integer k is bounded by bm=fflc, the number j 0 of large jobs in J 0
is bounded by j . Therefore, there are at most
ways to choose the large job set J 0
L . Since each job may have up to 2
alternative mode assignments, the total number of mode assignments to each large
set J 0
L is bounded by Each tower is associated with a subset
of the processor set Pm of m processors. Thus, each tower may be associated with
different subsets of Pm . Therefore, the number of different sequences of
up to 2j m;ffl +1 towers is bounded by . Finally, the number of
permutations of the j 0 large jobs and 2j 0 +1 towers is (3j 0 +1)!. Summarizing all these
together, we conclude that the number of times that the algorithm Schedule-Small
is called is bounded by:
O(bm=fflc
When the algorithm Schedule-Small is applied to the job set J 0
S , the upper
bound on the running time of the rooms is
According to Lemma 4.3, each call to the algorithm Schedule-Small takes time
where
Combining Equations (3) and (4), and noting that m and ffi thus ffl are fixed
constants, we conclude that the running time of the algorithm Approx-Scheme is
bounded by O(n  m;ffl +j m;ffl +1 ).
Now we are ready to present our main theorem.
Theorem 4.5. The algorithm Approx-Scheme is a polynomial time approximation
scheme for the problem Pm jsetjC max .
Proof. As proved in Lemma 4.4, the algorithm Approx-Scheme runs in polynomial
time when m and ffi are fixed constants. Therefore, we only need to show
that the makespan of the scheduling \Gamma 0 (J ) constructed by the algorithm Approx-
Scheme for an instance J of the problem Pm jsetjC max is at most (1 times the
optimal makespan Opt(J ) for the instance J . Again let
Let \Gamma(J ) be an optimal scheduling of makespan Opt(J ). Under the scheduling
\Gamma(J ), the mode assignments of the jobs are fixed. Thus, this particular mode assignment
makes us able to split the job set J into large job set JL and small job set
JS according the job processing time. According to Theorem 3.8, there is an (m; ffl)-
canonical scheduling for the instance J , under the same mode assignments,
such that the makespan of \Gamma 1 (J ) is bounded by (1
Consider a room fl j;q;r in the (m; ffl)-canonical scheduling \Gamma 1 (J ). Suppose that
are the small jobs assigned to the room fl j;q;r by the scheduling \Gamma 1 (J ).
Then
is the processing time for the job J p i under
which is the same as under \Gamma(J ). Thus we must have
0Therefore, under the same mode assignments (with processing time replaced by
and the same room assignments, the corresponding scheduling \Gamma 1 (J 0 ) for the
set J 0 has no rooms with running time exceeding T 0
. Thus, by Lemma 4.1, when
step 3 of the algorithm Approx-Scheme loops to the stage in which the large job set
and their mode assignments, the tower types, and the ordering of the large jobs and the
towers all match that in the scheduling \Gamma 1 (J 0 ), the array element
J. CHEN and A. MIRANDA
corresponding to the room configurations of the scheduling must have value
True. Thus, a scheduling \Gamma 0
based on this configuration is constructed and its
makespan is calculated. Note that the scheduling \Gamma 0
may not be exactly the
scheduling must have exactly the same makespan.
Since step 4 of the algorithm Approx-Scheme picks the scheduling \Gamma 0 (J 0 ) that
has the smallest makespan over all schedulings for J 0 constructed in step 3, we conclude
that the makespan of the scheduling \Gamma 0 (J 0 ) is not larger than the makespan of
the scheduling \Gamma 0
larger than the makespan of the scheduling
As we described in the paragraph before Lemma 4.4, to obtain the corresponding
scheduling for the job set J , we first expand the scheduling \Gamma 0 (J 0 ) by K (i.e.,
multiplying the job processing times and starting times in \Gamma 0 (J 0 ) by K). Let the
resulting scheduling be \Gamma 0 (J 00 ). Similarly we expand the scheduling \Gamma 1 (J 0 ) by K to
obtain a scheduling \Gamma 1 (J 00 ). The makespan of the scheduling \Gamma 0 (J 00 ) is not larger
than the makespan of the scheduling \Gamma 1 (J 00 ) since they are obtained by proportionally
expanding the schedulings respectively, by the same factor K.
Moreover, the makespan of \Gamma 1 (J 00 ) is not larger than the makespan of the (m; ffl)-
canonical scheduling This is because these two schedulings use the same large
job set under the same mode assignment, the same small job set under the same mode
assignment and room assignment, and the same order of large jobs and towers. The
only difference is that the processing time t ij of each job J i in \Gamma 1 (J ) is replaced by a
possibly smaller processing time K of the corresponding job J 00
In
consequence, we conclude that the makespan of the scheduling \Gamma 0 (J 00 ) is not larger
than the makespan of the (m; ffl)-canonical scheduling \Gamma 1 (J ), which is bounded by
Finally, to obtain the scheduling \Gamma 0 (J ) for the job set J , we make corrections on
the processing times of the jobs in the scheduling \Gamma 0 (J 00 ). More precisely, we replace
the processing time K
which is the processing time of the
job J i in the job set J . Correcting the processing time for each job J 00
may make the makespan of the scheduling increase by
Therefore, after the corrections of processing time for all jobs in J 00 , the makespan of
the finally resulting scheduling \Gamma 0 (J ) for the job set J , constructed by the algorithm
Approx-Scheme, is bounded by
the makespan of
Here we have used the fact that Opt(J )  T 0 =m.
This completes the proof of the theorem.
5. Conclusion and remarks. In this paper, we have developed a polynomial
time approximation scheme for the Pm jsetjC max problem for any fixed constant m.
The result is achieved by combinations of the recent techniques developed in the area
of multiprocessor job schedulings plus the classical dynamic programming and scaling
techniques. Note that this result is a significant improvement over the previous results
on the problem: no previous approximation algorithms for the problem Pm jsetjC max
have their approximation ratio bounded by a constant that is independent of the
number m of processors in the system. Our result also confirms a conjecture made
by Amoura et al. [1]. In the following we make a few remarks on further work on the
problem.
The multiprocessor job scheduling problem seems an intrinsically difficult prob-
lem. For example, if the number m of processors in the system is given as a variable
in the input, then the problem becomes highly nonapproximable: there is a constant
ffi such as no polynomial time approximation algorithm for the problem can have an
approximation ratio smaller than n [23]. Observing this plus the
difficulties in developing good approximation algorithms for the problem, people had
suspected whether the Pm jsetjC max problem for some fixed m should be MAX-NP
hard [8]. The present paper completely eliminates this possibility [2].
The current form of our polynomial time approximation scheme may not be practically
useful, yet. Even for a small integer m and a reasonably small constant ffl, the
time complexity of our algorithm is bounded by a polynomial of very high degree.
On the other hand, our algorithm shows that there are very "normalized" schedul-
ings whose makespan is close to the optimal ones, and that these "good" normalized
schedulings can be constructed systematically. We are interested in investigating the
tradeoff between the degree of this kind of normalization and the time complexity
of approximation algorithms. In particular, we are interested in developing more
practical polynomial time algorithms for systems with small number of processors,
such as P 4 jsetjC max . Note that currently there is no known practical approximation
algorithm for the P 4 jsetjC max problem whose approximation ratio is smaller than 2
(a ratio 2 approximation algorithm for the problem follows from Chen and Lee's recent
work on general Pm jsetjC max problem [8]). Moreover, so far all approximation
algorithms for the Pm jsetjC max problem are involved in the technique of dynamic
programming, which in general results in algorithms of high complexity. Are there
any other techniques that may avoid dynamic programming?

Acknowledgement

. The authors would like to thank Don Friesen and Frank
Ruskey for their helpful discussions.



--R

Scheduling independent multiprocessor tasks
Proof verification and the hardness of approximation problems
Scheduling multiprocessor tasks on a dynamic configuration of dedicated processors
Scheduling multiprocessor tasks on the three dedicated processors
"Scheduling multiprocessor tasks on the three dedicated processors, Information Processing Letters 41, (1992), pp. 275-280."
Scheduling multiprocessor tasks to minimize scheduling length
Scheduling multiprocessor tasks - a survey
General multiprocessor tasks scheduling

Efficiency and effectiveness of normal schedules on three dedicated processors
Simultaneous resource scheduling to minimize weighted flow times
Complexity of scheduling parallel task systems
Computers and Intractability: A Guide to the Theory of NP-Completeness
An approximation algorithm for scheduling on three dedicated machines
Bounds for certain multiprocessing anomalies
Concrete Mathematics
Approximation algorithms for scheduling
Complexity of scheduling multi-processor tasks with prespecified processor allocations
Fast approximation algorithms for the Knapsack and sum of subset problems
An approximation algorithm for diagnostic test scheduling in multicomputer systems
Scheduling multiprocessor tasks without prespecified processor allo- cations
Current trends in deterministic scheduling
Approximation algorithms in multiprocessor task scheduling
--TR

--CTR
C. W. Duin , E. Van Sluis, On the Complexity of Adjacent Resource Scheduling, Journal of Scheduling, v.9 n.1, p.49-62, February  2006
Klaus Jansen , Lorant Porkolab, Polynomial time approximation schemes for general multiprocessor job shop scheduling, Journal of Algorithms, v.45 n.2, p.167-191, November 2002
Jianer Chen , Xiuzhen Huang , Iyad A. Kanj , Ge Xia, Polynomial time approximation schemes and parameterized complexity, Discrete Applied Mathematics, v.155 n.2, p.180-193, January, 2007
multiprocessor processing;polynomial time approximation scheme;job scheduling;approximation algorithm