SCHEDULING ON PARELLEL MACHINES

(PART I)

In typical process-type plant layouts, machines are grouped according to a common function
and are placed in the same department. For instance, milling machines are grouped together.
When multiple jobs (parts) arrive at a department to be processed, a job sequence is made and
the jobs are assigned to the machines accordingly.

When the number of jobs is less than or equal to the number of available machines in the
department, sequencing the jobs on the machines becomes a trivial task (assigning one job to
every machine). However, the problem becomes very complex when the number of jobs is
large.

In parallel processing, the decision is two fold:

• Which machine processes the job (job allocation)
• Which sequence of jobs should be used on each machine (job sequencing)

Theorem 3.1: In any parallel machines scheduling problem ( P, Q, R γ ) for any performance
measure γ , there exists an optimal schedule in which there exists no idle time between the
processing of the jobs on every machine.

Theorem 3.2: In the identical parallel machines scheduling problem ( Pm γ ) for any
performance measure γ , if m ≥ n , then there exists an optimal schedule in which each job is
assigned to a different machine.

1. IDENTICAL PARALLEL MACHINES

Minimizing Makespan: Pm C max

This problem is of interest because minimizing the makespan (time to complete all jobs) has
the effect of balancing the load over the various machines, which is important in practice.
Suppose that we have Cmax jobs to be processed by any one of Cmax identical parallel
machines. The objective is to develop a job schedule on each machine that will minimize the
makespan.

Theorem 3.3: Pm C max is NP-hard.

The following mathematical programming model can be used to solve the makespan
minimization problem.

Decision Variables:
1 if job j is assigned to machine k
X jk = 
0 otherwise
Cmax = Makespan

1
Constraints:
1. Each job should be assigned to one machine only.
m
∑ X jk = 1 j = 1,..., n
k =1

2. Makespan should be equal to the maximum processing load assigned to one of the
 n n n 
machines (i.e., Cmax = max ∑ p j X j1 , ∑ p j X j 2 ,..., ∑ p j X jm  . Equivalently,
 j =1 j =1 j =1 
n
Cmax ≥ ∑ p j X jk k = 1,..., m
j =1

3. Nonnegativity and binary variables.

Cmax ≥ 0 , X jk ∈ {0,1} j = 1,..., n ; k = 1,..., m

Objective Function:
Minimize Cmax

*
Let LB be the lower bound on the makespan where Cmax ≥ LB . Then,
 n 
∑ p j 
 j =1 
LB = max  , max p j 
 m j =1,..., n

 
 

One of the most used general approximation strategies for solving parallel machines
scheduling problems is list scheduling, whereby a priority list of tasks is given, and at each
step the first available machine is selected to process the first available job in the list.

The accuracy of a given list scheduling algorithm depends on the order in which jobs appear
in the list. For list scheduling, the following result provides a performance guarantee.

Theorem 3.4: If any list scheduling (SPT, LPT, etc.) algorithm is used to solve problem
Pm C max then
List
C max 1
*
≤ 2−
C max m
Proof:

Consider a schedule produced by a list scheduling algorithm that achieves a makespan of

List List
C max . Let k denote a job that is completed at time C max , so that job k starts at time

2
 List
C max − pk , where pk is the processing time of job k . At this point, all m machines must
have been occupied continuously since time zero, and the amount of completed work must
have been at most all the work in the set of jobs, exclusive of job k . Hence,
n
List
m × (C max − pk ) ≤ ∑ p j − pk
j =1
Algebraic rearrangement yields
List
n pj p k (m − 1)
C max ≤∑ +
j =1 m m
n
*
From the lower bound calculated above, we know that C max is at least as large as ∑ pj / m
j =1

and at least as large as pk . It follows that

*
List * C max (m − 1) *  1
C max ≤ Cmax + = C max 1 + 1 − 
m  m
List
C max 1
Or, equivalently, *
≤ 2− . 
C max m

One of the simplest list scheduling algorithm is the LPT-list algorithm, which is described
below.

LPT-List ALGORITM for Pm C max

Step 1: Arrange the jobs in longest processing time (LPT) order.

Step 2: Schedule the job with the longest processing time on the machine with the smallest
processing load (i.e., first available machine).
Repeat Step 2 until all jobs are scheduled.

Example: A manufacturer of integrated circuits (ICs) uses five parallel testing machines to
perform different tests on circuits. The duration of the test depends on the function
of the IC and the test objectives. Assume that 16 ICs are to be tested, and their
testing times are as follows:

Integrated Circuit A B C D E F G H I J K L M N O P
Test Time 4 5 8 10 10 12 16 16 17 20 23 26 30 31 33 35

Using the LPT-List algorithm, find a schedule to minimize the makespan where
ICs are not preempted.

3
Solution: Arranging the jobs in LPT order of their processing times gives the sequence
below:
LPT sequence: P-O-N-M-L-K-J-I-H-G-F-E-D-C-B-A

Starting from the first job of the LPT sequence, the assignment of each job to the
machine having the smallest processing load gives the schedule in the Gantt chart
below. The makespan value is equal to 60.

Note that this solution is optimal although the LPT-List algorithm does not always
guarantee optimality.

M/C1 P G B A
35 51 56 60

M/C2 O H E
33 49 59

M/C3 N I F
31 48 60

M/C4 M J C
30 50 58

M/C5 L K D
26 49 59

Theorem 3.5: If the LPT-List algorithm is used to solve problem Pm C max then
LPT
C max 4 1
≤ −
* 3 3m
C max

Suppose we wish to determine whether we can construct a schedule that is consistent with the
lower bound. Thus, an even more effective heuristic algorithm than LPT-List is First-fit
Decreasing (FFD) algorithm, but it requires somewhat more computational effort.

FFD ALGORITHM for Pm C max

n
Step 0: Calculate LB = ∑ p j / m , and round LB to the smallest integer greater than LB if
j =1
LB is not an integer.

4
 Set the remaining cumulative times on all machines to the lower bound. i.e.,
RCTk = LB for k = 1,..., m .

Step 1: Arrange the jobs in longest processing time (LPT) order.

Step 2: Schedule the job with the longest processing time on the first available machine.

Step 3: Continue scheduling the remaining unscheduled jobs to the machine under
consideration until one of the following happens:
a. The sum of processing times of the jobs assigned to the machine under
consideration becomes equal to the lower bound LB .
b. The sum of processing times of the jobs assigned to the machine under
consideration becomes greater than the lower bound LB .

If (a) happens, then start assigning jobs to the next available machine.

If (b) happens, then the job that has caused the sum (total work load) to be greater
than the lower bound and subsequent jobs are allocated in the following manner:
Sweep across the available machines (in order 1, 2, 3, …).
• If the sum of processing times on the next machine is less than the
lower bound and allocation of the job there will not increase the
cumulative processing time on the machine beyond lower bound, then
assign the job there.
• If not, continue the check with the next available machine. If on all
available machines, the assignment of the present job will increase the
sum beyond the lower bound, assign the job to the machine on which
such increase would be minimum (i.e., assign the job to the machine
having least work load already assigned).

Once all the jobs are assigned, the makespan is the maximum of the sum of
processing times on each machine.

Example: Consider data given in the previous example. Find a schedule to minimize the
makespan where ICs are not preempted.

Integrated Circuit A B C D E F G H I J K L M N O P
Test Time 4 5 8 10 10 12 16 16 17 20 23 26 30 31 33 35

Solution: The application of the FFD algorithm on the data given above is as follows:

n
4 + ... + 35
Step 0: LB = ∑ pj /m = = 59.2 ≈ 60
j =1 5
RCTk = 60 for k = 1,...,5 .

5
Step 1: Arranging the jobs in LPT order of their processing times gives the sequence
below:
LPT sequence: P-O-N-M-L-K-J-I-H-G-F-E-D-C-B-A

Step 2: The first job, Job P, in the list above can be assigned to any one of the five
machines since their remaining cumulative times are same and 60. Suppose that
we schedule it to machine 1. Then the remaining cumulative time for machine 1
becomes RCT1 = RCT1 − p P = 60 − 35 = 25 . The remaining cumulative times for
other machines do not change.

The next job to be scheduled is Job O. It can not be scheduled to machine 1 since
its processing time is 33, which is greater than RCT1 = 25 . Thus, it has to be
scheduled to machine 2, which has the remaining cumulative time greater than the
processing time of Job O. That is, RCT2 = 60 > pO = 33 . Then, the remaining
cumulative time for machine 2 becomes RCT2 = RCT2 − pO = 60 − 33 = 27 .

The third job to be scheduled is Job N, which has a processing time of 31 time
units. Job N can not be scheduled to both machines 1 and 2 since
RCT1 = 25 < p N = 31 and RCT2 = 27 < p N = 31 . Thus, it has to be scheduled to
machine 3, which has the remaining cumulative time greater than the processing
time of Job N. Thus, the remaining cumulative time for machine 3 becomes
RCT3 = 60 − p N = 60 − 31 = 29 .

Similarly, the fourth job, Job M, can not be scheduled to the machines 1, 2, and 3
since their remaining cumulative times is not greater than its processing time of 30
time units. Thus, it has to be scheduled to machine 4. Then, the remaining
cumulative time for machine 4 becomes RCT4 = 60 − p M = 60 − 30 = 30 .

The fifth job, Job L, has the processing time of 26, and can be assigned to the
current machine, which is machine 4. Thus, the remaining cumulative time for
machine 4 becomes RCT4 = 30 − p L = 30 − 26 = 4 .

The sixth job, Job K, cannot be assigned to the current machine, which is machine
4 since RCT4 = 4 < p K = 23 . Then we have to check machine 1 first. When we
assign Job K to machine 1, then the cumulative processing time on this machine
becomes 35 + 23 = 58 that is greater than the cumulative processing time on
machine 4, which is 56. Thus, Job K cannot be assigned to machine 1, and we
have to check machine 2. When we assign Job K to machine 2, then the
cumulative processing time on this machine becomes 33 + 23 = 56 , which is not
greater than the cumulative processing time on machine 4. Thus, Job K can be
assigned to machine 2. Thus, the remaining cumulative time for machine 2
becomes RCT2 = 27 − p K = 27 − 23 = 4 .

The application of the FFD algorithm to the remaining jobs yields the schedule
given in the Gantt chart below:

6
 M/C1 P J B
35 55 60

M/C2 O K
33 56

M/C3 N I D
31 48 58

M/C4 M L A
30 56 60

M/C5 H G F E C
16 32 44 54 62

C max

Minimizing Makespan with Sequence Dependent Setups: Pm sij C max

Decision Variables:
1 if job j is assigned to machine k
X jk = 
0 otherwise
1 if job j immediatel y follows job j on machine k
Yijk = 
0 otherwise
Cmax = Makespan

Constraints:
1. Each job should be assigned to one machine only.
m
∑ X jk = 1 j = 1,..., n
k =1

2. A job must be processed at one and only one position on a machine.

n m
∑ ∑ Yijk =1 j = 1,..., n
j =0 k =1
i≠ j

3. If a job is assigned to a machine, it should come after one of the jobs including job
0.
n m
∑ ∑ Yijk = X jk j = 1,..., n ; k = 1,..., m
j = 0 k =1
i≠ j

7
 4. If a job is assigned to a machine, at least 1 job immediately follows it.
n m
∑ ∑ Yijk ≤ X ik i = 1,..., n ; k = 1,..., m
j =1 k =1
i≠ j

5. If a job is assigned to a machine, its completion time can not be less than the sum
of the completion time of the preceding job and its setup and processing times.
C j ≥ Ci + sij + p j + M (1 − Yijk ) i = 1,..., n ; j = 1,..., n ; i ≠ j ; k = 1,..., m

C j ≥ (s0 j + p j ) × X jk j = 1,..., n ; k = 1,..., m

6. The makespan of the schedule should be greater than or equal to the completion
time of each job.
C max ≥ C j j = 1,..., n

7. Nonnegativity and binary variables.

Cmax ≥ 0 , X jk ∈ {0,1} , Yijk ∈ {0, 1} i = 1,..., n ; j = 1,..., n ; k = 1,..., m

Objective Function:
Minimize Cmax

Minimizing Makespan with Setups Performed by a Single Worker:

The following mathematical programming model can be used to solve the makespan
minimization problem with setups performed by a single worker.

Decision variables:
1 if job j is assigned to position t of the sequence
X j ,t = 
0 otherwise
1 if job in position t is processed on machine k
Yt ,k = 
0 otherwise
STt = Start time of the setup for the job in position t of the sequence
CTt = Completion time for the job in position t of the sequence
C max = Makespan

Constraints:
1. Each job should be assigned to only one position of the sequence.
n
∑ X j,t = 1 j = 1,..., n
t =1
2. Only one job can be assigned to each position of the sequence.

8
 n
∑ X j,t = 1 t = 1,..., n
j =1
3. The job assigned to each position of the sequence has to be processed on one of the
machines.
m
∑ Yt , m = 1 t = 1,..., n
k =1
4. The setup of the job assigned to a position of the sequence may be started only
after the setup of the job assigned to the previous position of the sequence is
completed by the worker.
n
STt ≥ STt −1 + ∑ s j X j , t −1 t = 1,..., n
j =1
5. The job assigned to a position of the sequence can be started only after the
processing of the job assigned to the previous position of the sequence is
completed on the same machine.
STt ≥ CTh − M ( 2 − Yt , k − Yh , k ) t = 1,..., n ; h = 1,..., n − 1 and h < t ; k = 1, ..., m

6. The completion time of the job assigned to a position of the sequence is equal to
the sum of its setup’s start time, setup time and processing time.
N
CTt = STt + ∑ ( s j + p j ) X j ,t t = 1,..., n
j =1
7. The makespan of the schedule should be greater than or equal to the completion
time of the job assigned to each position of the sequence.
Cmax ≥ CTt t = 1,..., n

8. Nonnegativity and integrality restrictions.

STt ≥ 0 , CTt ≥ 0 t = 1,..., n
X j ,t ∈ {0, 1} j = 1,..., n ; t = 1,..., n
Yt ,k ∈ {0, 1} t = 1,..., n ; k = 1, ..., m

Objective Function:

Minimize C max

Minimizing Makespan with Preemptions: Pm prmp Cmax

Usually, but not always, allowing preemptions simplifies the analysis of a problem.

The following mathematical programming model can be used to solve the makespan
minimization problem where jobs can be preempted.

Decision Variables:
Y jk = Amount of processing time of job j allocated to machine k
Cmax = Makespan

9
Constraints:
1. For each job, the sum of the processing times allocated to all machines should be
equal to the processing time of the job.
m
∑ Y jk = p j j = 1,..., n
k =1
2. Makespan should be at least equal to the maximum processing load assigned to
one of the machines.
n
C max ≥ ∑ Y jk k = 1,..., m
j =1
3. Nonnegativity and binary variables.
Cmax ≥ 0 , Y jk ≥ 0 j = 1,..., n ; k = 1,..., m

Objective Function:
Minimize Cmax

The solution of the LP above does not prescribe an actual schedule; it specifies the amount of
time job j should spend on machine k and the optimal value of the makespan. The following
theorem gives the optimal value of the makespan.

Theorem 3.6: The optimal makespan for Pm prmp Cmax is

 1 n 
*
Cmax { }
= max  max p j , ∑ p j 
m j =1 
 j =1,..., n
n

j =1,..., n
{ }
where max p j is the maximum processing time, and the ∑ p j / m is the equal work load
j =1
allocation among the machines.

Using Theorem 3.6, an optimal schedule for Pm prmp Cmax can easily be constructed by
following algorithm.

McNaughton ALGORITHM for Pm prmp Cmax

 1 n 
*
Step 0: Calculate Cmax { }
= max  max p j , ∑ p j  .
m j =1 
 j =1,..., n

Step 1: Schedule any unscheduled job on the first machine at time zero.

10
Step 2: Choose any unscheduled job and schedule it as early as possible on the same
*
machine. Repeat this process until the machine is occupied beyond Cmax or until all
jobs are scheduled.

*
Step 3: Reassign the processing of a job beyond Cmax to the next machine starting at time
zero. Go to Step 2.

Example: Consider data given in the previous example. Find a schedule to minimize the
makespan where ICs are preempted.

Solution: The optimal makespan is

*
C max = max{35, (4 + .... + 35) / 5} = 59.2

The optimal schedule obtained by the McNaughton algorithm is as shown in the

Gantt chart below.

M/C1 A B C D E F G
4 9 17 27 37 49 59.2

M/C2 G H I J K
5.8 21.8 38.8 58.8 59.2

M/C3 K L M
22.6 48.6 59.2

M/C4 M N O
19.4 50.4 59.2

M/C5 O P
24.2 59.2

Minimizing Makespan with Precedence Relations and Unit-length

Tasks: Pm prec, p j = 1Cmax

The first special case requires that the precedence relations take the form of an assembly tree.
In an assembly tree (sometimes called an intree), no job has more than one direct successor.
Furthermore, in such a tree, the final job—the job without any successors—is called a
terminal job.

11
In addition, let p j = 1 for all jobs, so that we have unit-length tasks. For this special case, we
can solve the makespan problem with an algorithm consisting of a labeling phase followed by
a scheduling phase.

Labeling Phase ALGORITHM for Pm intree, p j = 1 Cmax

Step 1: Assign the label zero to the terminal job.

Step 2: Suppose labels 1, 2, . . . , j − 1 have been assigned. Assign the label j to all jobs with
no unlabeled successors.
Step 3: Repeat Step 2 until labels have been assigned to all jobs.

The scheduling phase is essentially a list-scheduling procedure, with jobs in non-increasing

label order to the extent the precedence constraints allow. The labeling phase assigns to each
job j a label equal to the length of time required to process the jobs that follow job j on the
(unique) path connecting job j and the terminal job. Then, when the scheduling phase places
the jobs with the largest labels into the schedule, it essentially gives priority to the jobs that
initiate the longest paths in the remaining tree.

In the figure below, job 1 receives the label 0, jobs 2–4 are labeled 1, jobs 5–7 are labeled 2,
jobs 8–11 are labeled 3, jobs 12–16 are labeled 4, and job 17 receives the highest label, 5.

In the scheduling phase, job 17 is processed on one of the machines in the first period, and we
can select any two additional jobs with label 4, except job 13 (which is not yet feasible), and
so on.

12
Labeling Phase algorithm provides an optimal schedule when the problem contains unit-
length jobs and a tree structure. Although a tree has just one terminal job, we can apply the
algorithm to the scheduling of several trees by creating a dummy terminal job to serve as
successor to the terminal jobs of each of the trees. If we assign the label zero to the dummy
job, then each label represents the work remaining on the direct path from the node until
completion (including the node itself).

Minimizing Total Completion Time (Total Flow Time): Pm ∑C j

The following mathematical programming models can be used to solve the total completion
time minimization problem.

Model 1:

Decision Variables:
1 if job j is assigned at position t on machine k
X jtk = 
0 otherwise
C jtk = Completion time of job j assigned to position t on machine k

Constraints:
1. Each job should be assigned to one machine only.
m n
∑∑ X jtk = 1 j = 1,..., n
k =1 t =1

2. Each position on each machine should be occupied by at most one job.

n
∑ X jtk ≤ 1 k = 1,..., m ; t = 1,..., n
j =1

3. Completion time of a job occupying a position on a machine should be equal to the

sum of the completion time of the job in the proceeding position plus the
processing time of the job.
t −1 n
C jtk = ∑∑ pi X irk + p j X jtk j = 1,..., n ; t = 1,..., n ; k = 1,..., m
r =1 i =1

4. Nonnegativity and integrality restrictions.

C jtk ≥ 0 , X jtk ∈ {0,1} j = 1,..., n ; t = 1,..., n ; k = 1,..., m

Objective Function:
n m n
Minimize ∑∑∑ C jtk
j =1 k =1 t =1

13
Model 2:

Decision Variables:
1 if job j is assigned at position t on machine k
X jtk = 
0 otherwise
Ctk = Completion time of job assigned to position t on machine k

Constraints:
1. Each job should be assigned to one machine only.
m n
∑∑ X jtk = 1 j = 1,..., n
k =1 t =1

2. Each position on each machine should be occupied by at most one job.

n
∑ X jtk ≤ 1 k = 1,..., m ; t = 1,..., n
j =1

3. Completion time of a job occupying a position on a machine should be equal to the

completion time of the job in the proceeding position plus the processing time of
the job.
n
Ctk = Ct −1,k + ∑ p j X jtk j = 1,..., n ; t = 1,..., n ; k = 1,..., m
j =1
4. Nonnegativity and integrality restrictions.
Ctk ≥ 0 , X jtk ∈ {0,1} j = 1,..., n ; t = 1,..., n ; k = 1,..., m

Objective Function:
m n
Minimize ∑ ∑ Ctk
k =1 t =1

Theorem 3.7: In the optimal schedule for Pm ∑ C j , jobs in every machine are in Shortest
Processing Time (SPT) order.

The following algorithm optimally solves the problem Pm ∑C j .

Conway-Maxwell-Miller ALGORITHM for Pm ∑C j
Step 1: Arrange the jobs in shortest processing time (SPT) order.

Step 2: Schedule the job with the smallest processing time on the machine with the smallest
processing load (i.e., smallest total processing time assigned).
Repeat Step 2 until all jobs are scheduled.

14
Note the above algorithm is the SPT-List algorithm that assigns the jobs to machines in
rotation. That is, if the j th job in the job list is assigned to machine k (1 ≤ k ≤ m − 1 ), then
the j + 1 st job will be assigned to machine k + 1 ; and if the j th job in the job list is assigned
to machine m , then the j + 1 st job will be assigned to machine 1.

Example: Consider data given in the previous example. Find a schedule to minimize the
mean completion of ICs.

Solution: The first step of the algorithm gives the SPT sequence as:

SPT: A-B-C-D-E-F-G-H-I-J-K-L-M-N-O-P

The application of the second step yields the optimal schedule below:

M/C1 A F K P
4 16 39 74

M/C2 B G L
5 21 47

M/C3 C H M
8 24 54

M/C4 D I N
10 27 56

M/C5 E J O
10 30 63

Minimizing Total Flow Time with Machine Availability: Pm ak ∑C j

Now, assume that the machines may not be readily available at time zero. Therefore, each
machine has a specific time ak at which it becomes available.

The following mathematical programming model can be used to solve the total completion
time minimization problem.

15
Decision Variables:
1 if job j is assigned at position t from last on machine k
X jtk = 
0 otherwise

Constraints:
1. Each job should be assigned to one machine only.
m n
∑∑ X jtk = 1 j = 1,..., n
k =1 t =1

2. Each position on each machine should be occupied by at most one job.

n
∑ X jtk ≤ 1 k = 1,..., m ; t = 1,..., n
j =1

3. Integrality restrictions.
X jtk ∈ {0,1} j = 1,..., n ; t = 1,..., n ; k = 1,..., m

Objective Function:
n m n
Minimize ∑ ∑ ∑ (ak + tp j ) X jtk
j =1 k =1 t =1

The following Theorem gives the sufficient condition for a schedule to be optimal.

Theorem 3.8: In the optimal solution of the basic multiple identical parallel machines
scheduling problem with machine availability, the unscheduled job with shortest processing
time always be assigned to the machine with the earliest current available time.

Let Ak be the time at which machine k will be available, given its initial available time ak
and the jobs currently assigned to it. The following algorithm optimally solves the problem
Pm ak ∑ C j .

Kaspi-Montreuil ALGORITHM for Pm ak ∑C j

Step 1: Arrange the jobs in shortest processing time (SPT) order.

Step 2: Set the current machine available time Ak = ak for k = 1,..., m .

Step 3: Arrange the machines in earliest machine available time order.

Step 4: Schedule the first job of the SPT sequence on machine having the earliest machine
available time.

16
 Step 5: Increase the current machine available time for the machine having the earliest
machine available time by the processing time of the job scheduled to that machine.

Step 6: Remove the scheduled job from the SPT list.

Step 7: Re-arrange the machines in earliest machine available time order.

Step 8: If the SPT list is not empty, then go to Step 4; otherwise, stop.

Example: Consider data given in the previous example. Furthermore, assume that the initial
available times for each machine is

Machine 1 2 3 4 5
Available Time 0 0 12 18 24

Find a schedule to minimize the mean completion of ICs.

Solution: The application of the Kaspi-Montreul algorithm gives the optimal schedule
below.

M/C1 A C E I O

4 16 22 39 72

M/C2 B D G L
5 15 31 57

M/C3 F J N
12 24 44 75

H M
M/C4
18 34 64

K P
M/C5
24 47 82

The mean flow time is 627 / 16 = 39.18.

17