Oliver Braun
CSE 101 (Summer Session 2021)
Homework 2: Bin Packing and Scheduling
Instructions
Homework questions will be similar to your future exam questions. The homework will not be graded,
however, you are highly recommended to practice using these questions for better preparations of the
exams.
Key Concepts Bin Packing and Scheduling: Proving the Optimality of Greedy Algorithms, Analyzing
the Worst-case behavior of Approximation Algorithms.
If you live in a city apartment, finding room to store your possessions is a major problem – there never
seems to be enough room. Suburban residents must be having similar problems because the growth in
using off-site storage facilities is on the rise. Metaphorically, there never seem to be enough bins for all
one needs to store. Mathematics comes to the rescue with the bin packing problem and its relatives. The
bin packing problem raises the following question: given a finite collection of n weights w1, w2, w3, . . . , wn,
and a collection of identical bins with capacity C (which exceeds the largest of the weights), what is the
minimum number k of bins into which the weights can be placed without exceeding the bin capacity C?
Stripped of the mathematical formulation, we want to know how few bins are needed to store a collection
of items. This problem, known as the 1-dimensional bin packing problem, is one of many mathematical
packing problems which are of both theoretical and applied interest in mathematics. It is important to
keep in mind that weights are to be thought of as indivisible objects rather than something like oil or
water. For oil one can imagine part of a weight being put into one container and any left over being put
into another container. However, in the problem being considered here we are not allowed to have part
of a weight in one container and part in another. [Source: Joseph Malkevitch York College (CUNY),
http://www.ams.org/publicoutreach/feature-column/fcarc-bins1]
Scheduling Problems arise in many practical circumstances and under a wide variety of guises. Many are
basically optimization problems having the following form: Given a collection of tasks to be scheduled
on a particular processing system, subject to various constraints, find a feasible schedule that minimizes
(or in some cases maximizes) the value of a given objective function. Thus it is not surprising that much
of the work on scheduling theory has been devoted to the design and analysis of optimization algorithms-
algorithms that, when given a particular instance of a scheduling problem, construct an optimal feasible
schedule for that instance. Unfortunately, although it is not difficult to design optimization algorithms
(e.g., exhaustive search is usually applicable), the goal of designing efficient optimization algorithms
has proved much more difficult to attain. In fact, all but a few schedule-optimization problems are
considered insoluble except for small or specially structured problem instances. For these scheduling
problems no efficient optimization algorithm has yet been found and, indeed, none is expected. This
pessimistic outlook has been bolstered by recent results showing that most scheduling problems belong
to the infamous class of NP-complete problems. For these reasons practitioners often are willing to settle
merely for a feasible schedule, as long as they have some indication that it is a reasonably good one.
Though there are problems for which finding even a feasible schedule seems computationally hopeless,
for most schedule-optimization problems there do exist simple heuristic algorithms that find feasible
schedules quickly. One particularly attractive approach to analyzing how good, relative to optimal
schedules, are the schedules constructed by such heuristics deals with proving performance guarantees
by performing a Worst-case analysis of Approximation algorithms. [Source: Garey, Michael R., Graham,
Ronald L., Johnson, David S.: Performance Guarantees for Scheduling Algorithms, Operations Research
26, 3-21, 1978].
1
Problem 1. Bin Packing. Items with sizes {8, 7, 2, 3, 5, 4} need to be packed into bins with capacity 10. Mini-
mize the number of bins used. Apply the following heuristics and give the number of bins used as
well as items in each bin.
(a) Next Fit.
(b) First Fit Decreasing.
Solution:
(a) Given order: 8,7,2,3,5,4
0
10
0
10
0
10
0
10
8
7
2
3
5
4
4 bins used.
(b) Sorted: 8,7,5,4,3,2
0
10
0
10
0
10
8
2
7
3
5
4
3 bins used.
2
Problem 2. Bin Packing. Consider the following Bin Packing problem. k items with size 1 and k − 1 items
with size 100, where k is a number smaller than 100. Bin capacity 100.
(a) Show that the worst-case Next Fit solution is 2− 1
k
times the optimal.
(b) Find a worst-case Next Fit solution that is 3
2
of the optimal.
Solution:
(a) The lower bound for the number of bins that have to be used is
⌈
k+(k−1)×100
100
⌉
= k−1+
⌈
k
100
⌉
,
which is k − 1 + 1 = k because k is a number smaller than 100. This can be actually obtained
by putting all k size-1 items into one bin and the size-100 items into their own bins. Thus it
must be the optimal. It remains to find the ordering that would result in the worst-case Next
Fit solution. The size-100 items must have the bins to themselves, so what we want is all size-1
items having their own bins. This can be achieved by alternating between size-1 and size-100
items with a size-1 item going first as (1, 100, 1, 100, . . . , 1. By the Next Fit algorithm, this
ordering would result in each item having its own bin which is k + k − 1 = 2k − 1 in total.
NextFit
OPT
= 2k−1
k
= 2− 1
k
.
(b) Using the same setting as above, take k = 2, i.e. 2 size-1 items and 1 size-100 item,
which gives us the desired worst-case-to-optimal ratio: NextFit = (1,100,1) results in 3 bins.
OPT=(1,1,100) results in 2 bins.
3
Problem 3. Bin Packing. Consider the following problem. Given are n items with weights w1, w2, . . . , wn ≤ 1.
You are tasked with the problem of putting these items into bins so that the total weight of all
items in any one bin is at most 1. For example, if you had items of weights 0.6, 0.5 and 0.3, you
could put then all in different bins, or put the first and third in a bin together and the second in a
different bin, but you could not put the first and second in the same bin, because 0.6+0.5 > 1. Your
objective is to do this while minimizing the total number of bins used. The following algorithm
solves that problem:
1. put each item in a separate bin
2. while there exist two bins whose total weight is less than 1
3. combine the items from those two bins into a single bin
(a) Analyze the algorithm’s time complexity.
(b) Prove that the algorithm is a 2-approximation for Bin Packing.
Solution:
(a) The order bins are combined is not specified, so the run time of this algorithm partly depends
on the implementation of the while-loop. A naive implementation takes O(n3) time, since we
can combine bins at most n−1 times, and in each iteration, we can check whether or not there
are two combinable bins using a nested for-loop, which runs in O(n2) time.
In fact a clever implementations can be made to run in O(n log n): after placing each item in its
own bin, we sort the bins by the weight of item inside, which takes O(n log n). The while-loop
runs at most n−1 iterations, we check if the first two bins (containing the smallest weight) can
be combined. If they are combinable, combine and insert the new bin to its position, keeping
the bins sorted. Each iteration takes at most O(log n), so the while-loop takes O(n log n) as
well.
(b) Suppose that the algorithm provides a solution with k final bins. It must be the case that for
any 2 bins the total weight of all the items in either bin is more than 1, since otherwise we
would have combined those bins. Let x1, x2, . . . , xk be the total weights of each bin. If k = 1,
then we use only one bin, which clearly cannot be improved upon. Otherwise, xi + xj ≥ 1 for
all i 6= j. Therefore, we have that
2(k − 1)
∑
i
xi =
∑
i6=j
(xi + xj) ≥
∑
i 6=j
1 = k(k − 1)
Therefore, we have that the total weight of all items is
∑
i xi, which is at least k/2. Since no
packing is allowed to put more than one unit of weight in any bin, any packing must use at
least k/2 bins. Therefore, the ratio between what our algorithm achieves and the optimal is at
most k/(k/2) = 2. Therefore, we have a 2-approximation.
4
Problem 4. Bin Packing. Generalize a Bin Packing problem as follows. Suppose there are k distinct items
and each repeats 2i times in the pool of items to be put into bins of capacity C, the ith dis-
tinct object repeats 2i−1 times. Example: k = 4 distinct items 7, 5, 9, 2, resulting input is then
7, 5, 5, 9, 9, 9, 9, 2, 2, 2, 2, 2, 2, 2, 2.
(a) How many items are there, i.e. what is n?
(b) How many different lists are there?
(c) This problem can be solved with Branch and Bound. Describe an idea how to computer Lower
and Upper Bounds. Is a feasible solution an Upper Bound or a Lower Bound?
Solution:
(a) There are a total of n =
∑k−1
i=0 2
i = 2k − 1 items.
(b)
(2k−1)!∏k−1
i=0
(2i)!
(c) The initial upper bound: UB1 = 2
k − 1, i.e. all items in their own bin.
With an ordering of items we denote the way to pack the items using Next Fit.
Branch: enumerate on the ith level for which is the ith item in the ordering.
Lower bound: LB = the number of bin used to pack the current ordering (should be length
i if the node is on the ith level) with Next Fit (in fact, you can further increase this lower
bound by b sum of weights for remaining items / bin capacity c and it’s still a lower bound.
Can you see why?).
Upper bound: UB = the number of bin used to pack the current ordering + the number
of remaining items (i.e. create a feasible solution by putting each of the rest items in its own bin)
Since this is a minimization problem, a feasible solution is an Upper Bound.
5
Problem 5. EDD for 1||Lmax and Moore/Hodgson for 1||
∑
Uj. The following n = 8 jobs with given processing
times pj and deadlines dj have to be scheduled on a single processor.
A B C D E F G H
pj 3 7 4 6 4 6 3 2
dj 6 20 6 17 5 18 36 22
(a) Calculate the values of Lmax and
∑
Uj , if you schedule the jobs in the given order A,B,. . .,H.
(b) Determine the optimal schedule for minimizing the maximum lateness 1||Lmax using the EDD
algorithm.
(c) Determine the optimal schedule for minimizing the number of late jobs 1||
∑
Uj using the
Moore/Hodgson algorithm.
Solution:
(a) Just scheduled in that order would give Lmax = 19 (job E) and
∑
Uj = 5 (jobs C, D, E, F, H).
A B C D E F G H
pj 3 7 4 6 4 6 3 2
dj 6 20 6 17 5 18 36 22
Cj 3 10 14 20 24 30 33 35
Lj -3 -10 8 3 19 12 -3 13
Uj 0 0 1 1 1 1 0 1
(b) Scheduling using the EDD algorithm would give: Lmax = 10 (job B) which is the optimal
solution for 1||Lmax.
E A C D F B H G
pj 4 3 4 6 6 7 2 3
dj 5 6 6 17 18 20 22 36
Cj 4 7 11 17 23 30 32 35
Lj -1 1 5 0 5 10 10 -1
(c) Scheduling using Moore’s algorithm would give
∑
Uj = 3 (jobs E, C, B) which is the optimal
solution for 1||
∑
Uj .
E A C D F B H G
pj 4 3 4 6 6 7 2 3
dj 5 6 6 17 18 20 22 36
C1j 4 7 – – – – – –
C2j X 3 7 – – – – –
C3j X 3 X – – – – –
C4j X 3 X 9 15 22 – –
C5j X 3 X 9 15 X 17 20
6
Problem 6. EDD for 1||Lmax. Prove that EDD is optimal for 1||Lmax.
Solution:
Please watch video BS-3d for the interchange argument proof.
We use an interchange argument to prove that the schedule constructed by EDD is optimal. Assume
without loss of generality that all due dates are distinct, and number the jobs so that d1 < d2 <
. . . < dn. Among all optimal schedules, we consider the one with the fewest inversions, where an
inversion is a pair of jobs j, k such that j < k but k is scheduled before j.
Suppose the given optimal schedule S is not the EDD schedule. Then there is a pair of jobs j and
k such that dj < dk but k immediately precedes j in the schedule.
Suppose we exchange jobs j and k. This does not change the completion time or lateness of any
job other than j and k.
We claim that we can only decrease max(Lj , Lk), so we do not increase the maximum lateness.
Furthermore, since j < k, swapping jobs j and k decreases the number of inversions in the schedule.
It follows that the new schedule has the same or better lateness than the original one but fewer
inversions, a contradiction.
To prove the claim, note that in schedule S CSj > C
S
k but dj < dk. It follows that max(L
S
j , L
S
k ) =
CSj − dj . Under the exchange, job j’s completion time, and thus lateness, decreases. Job k’s
completion time rises to CSj , but this gives it a lateness of C
S
j −dk < C
S
j −dj . Thus, the maximum
of the two latenesses has decreased.
7
Problem 7. List Scheduling, LPT and SPT for P ||Cmax and McNaughton’s algorithm for P |pmtn|Cmax. The
following n = 12 jobs with given processing times have to be scheduled on m = 3 parallel and
identical processors with the objective of minimizing the makespan. Cj is the completion time of
job j.
A B C D E F G H I J K L
4 9 12 1 3 5 9 10 8 11 6 6
(a) Draw the List-Scheduling-schedule as a Gantt-Chart. How much is Cmax and how much is∑
Cj?
(b) Draw the LPT-schedule as a Gantt-Chart. How much is Cmax and how much is
∑
Cj?
(c) Draw the SPT-schedule as a Gantt-Chart. How much is Cmax and how much is
∑
Cj?
(d) Find the optimal and the worst list concerning the objective of minimizing the makespan.
(e) Find the optimal and the worst list concerning the objective of minimizing the sum of the
processing times.
(f) Draw McNaughton’s schedule (preemptions allowed).
Solution:
(a) List-Scheduling: Cmax = 29 and
∑
Cj = 78 + 56 + 62 = 196
P1
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31
A D E F I K
P2
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31
B G J
P3
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31
C H L
(b) LPT: Cmax = 29 and
∑
Cj = 85 + 85 + 82 = 252
P1
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31
C I L D
P2
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31
J G F A
P3
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31
H B K E
(c) SPT: Cmax = 31 and
∑
Cj = 45 + 59 + 64 = 168
P1
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31
D F I H
P2
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31
E K B J
P3
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31
A L G C
8
(d) Optimal schedule: Lower Bound LB = max{12, 84/3} = 28. This lower bound is actually
achievable: (C,J,H,B,I,K,L,F,G,E,A,D).
P1
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31
C K L E D
P2
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31
J I F A
P3
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31
H B G
To get the worst list concerning the objective of minimizing the makespan, remove the job
with max processing time C(= 12), then schedule the remaining jobs in an optimal way. Then
add the job C to one of the machines to get the makespan to be 24 + 12 = 36. One such
example is {J,H,I,K,B,G,L,F,E,A,D,C}.
P1
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36
J G E D C
P2
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36
H B F
P3
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36
I K L A
(e) SPT minimizes the sum of completion times at 168 and LPT has the maximum at 252.
(f) The Gantt-Chart for McNaughton’s schedule is:
P1
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31
A B C D E
P2
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31
E F G H I
P3
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31
I J K L
9
Problem 8. McNaughton’s algorithm for P |pmtn|Cmax. Given n jobs J1, . . . , Jn with processing times
p1, . . . , pn and m processors, McNaughton’s algorithm creates a schedule that minimizes the
makespan Cmax = max{C1, . . . , Cn} where Cj is the completion time of job Jj .
procedure McNaughton(p1, . . . , pn: a sequence of integers with n ≥ 1, m: an integer with m ≥ 1)
1. Cmax := max
{
p1, . . . , pn, (
∑n
j=1 pj)/m
}
2. i := 1 // processor index
3. l := 0 // current load of processor Pi
4. for j := 1 to n
5. if l + pj < Cmax
6. Schedule job Jj on the current processor Pi
7. in the interval [l, l + pj ] and set l := l + pj .
8. else
9. Schedule the first part of job Jj on the current processor Pi
10. in the interval [l, Cmax].
11. Schedule the remaining of job Jj on the next processor Pi+1
12. in the interval [0, l + pj − Cmax] and set i := i + 1 and l := l + pj − Cmax.
(a) Prove the correctness of McNaughton’s algorithm.
(b) Perform a time analysis for McNaughton’s algorithm.
(c) Prove that McNaughton’s algorithm needs never more than m− 1 preemptions to produce an
optimal solution.
Solution:
(a) We need to prove: 1. all jobs will be able to be assigned and no processor has makespan larger
than Cmax 2. the assignment is valid, i.e. there’s no overlapping of a job’s processing time on
different processors.
First, we move on to a new processor if and only if the makespan of current processor reaches
Cmax = max
(∑n
i=1 pi
m
,max(pi)
)
. So in total the m processors can handle m ·Cmax ≥
∑n
i=1 pi
time units of jobs, which means all jobs are able to be assigned, and the makespan for processors
won’t exceed Cmax.
Then, to show the assignment is valid, we do it by showing the loop invariant:
Loop invariant: After the jth iteration of the loop, the first j jobs have been assigned with no
overlap between processors on the same job.
Initialization: Before the first iteration, 0 elements have been assigned. Thus this satisfies the
loop invariant.
Assume the loop invariant is true after j−1 iterations, then during the jst iteration, the jst job
is assigned. If it fits the current processor, then it would only be assigned to this processor and
is trivially valid. If it does not, then a part of it would be assigned so the current processor’s
makespan reaches Cmax, assume this is k time units. Then the remaining pt+1 − k units are
assigned at the beginning of the next processor. Since k + pj − k = pj ≤ max(pi) ≤ Cmax,
assigning the jst job won’t introduce overlap. By induction the overall assignment is valid.
(b) Time analysis: Computing Cmax = max{pj ,
∑
pj/m} needs time O(n). Since all statements
inside the for-loop only take constant time, we only need to find out how many iterations the for
loop has. The Schedule functions can be implemented by setting sj and Cj to the corresponding
values and storing the information [j, sj , Cj ] what takes constant time. In addition, we possibly
have to increase the processor index (in line 12) by 1, and we do this exactly m − 1 times.
Therefore the total runtime is O(n + m) which is O(n), because we always can assume that
m ≤ n.
Remark: McNaughton’s algorithm is different from many scheduling algorithms in that it
creates the schedule machine by machine, rather than over time. Therefore an alternative
formulation of McNaughton’s algorithm would use a for-loop over the number of processors
and run from 1 to m.
10
(c) By the McNaughton’s algorithm, preemption can only happen at the end of a processor other
than the last one (which must finish the last job scheduled exactly). This leads to at most
m− 1 preemptions.
11
Problem 9. List Scheduling for P ||Cmax. Think about how you would implement List Scheduling and perform
a time analysis of your algorithm.
Example: Given are n = 8 jobs with the corresponding processing times pj . In the following table
the earliest available timepoints of the processors are denoted - always after the scheduling of the
next job of the list.
What data structure would you use and what operations do you need?
Jobs A B C D E F G H
pj 6 3 4 2 6 5 8 3
Processors P1 0 6 6 6 6 6 6 14 14
P2 0 0 3 3 5 5 10 10 13
P3 0 0 0 4 4 10 10 10 10
Solution:
Our primary data structure will be a priority queue implemented with a min-heap. It will have
the functions: Push and pop. Push inserts an element into the queue. Pop removes the minimum
element in the priority queue and returns the value.
Our input consists of n = the number of jobs, with processing times p1..pn, and m = number of
processors. We initially push m 0’s into the priority queue. Then, for each job i from 1...n, we
will pop off the current minimal element in the priority queue and update it with the processing
time of i. We will update the priority queue by pushing (min element + pj) back into the priority
queue. This continues for all elements in n.
Time analysis: Creating the priority queue/heap costs O(m). Push has a worst case time com-
plexity of O(logm) but has an average time complexity of O(1). Pop removes the smallest element
which takes O(logm). This runs for each element. Thus, the total runtime is O(n logm + m). As
m ≤ n, this results in O(n logm) time complexity.
12
Problem 10. List Scheduling for P ||Cmax. Let CLSmax be the makespan of the List Schedule and let C∗max be the
optimum makespan.
(a) Explain why
∑n
j=1 pj/m and pmax = max{pk} (for any k ∈ {1, . . . , n}) are Lower Bounds for
the makespan of any optimal algorithm solving P ||Cmax.
(b) Find Upper Bounds for the makespan of List Scheduling for P ||Cmax.
(c) Find a tight worst-case example for the makespan achieved by List Scheduling in comparison
to the optimum makespan for m = 5 processors.
Solution:
(a) Case 1: A processor can process only one job at a time. This means, a job can be completed
no earlier than it’s given processing time (note again that in our model it is not allowed that
a job is processed by more than one processor at any point in time). Hence, C∗max ≥ pmax.
Case 2:
∑n
j=1 pj is the total amount of processing that must be done across all machines.
Then for m machines,
∑n
j=1 pj
m
would be the average processing that needs to be done. By
properties of the average, at least one machine then must process at least this average (and the
best possible makespan is when all processors are completely filled from 0 to
∑n
j=1 pj). Hence,
C∗max ≥
∑n
j=1
pj
m
.
(b) One upper bound is the sum of all processing times (e.g. if all jobs ran sequentially on a single
machine). This bound is not tight at all. We can go further and lower this upper bound when
we schedule the jobs according to the List Scheduling procedure: schedule the next job always
on that processor that has done the least amount of work so far. Let Jk denote the job that
completes last across all machines, say on machine Pi. This job (by definition) was assigned
when machine Pi had the least load, so that:
CLSmax = Ck = sk + pk
where sk is the amount of load on machine Pi when Jk was assigned to it. But this, by
definition, must have been the least load among the machines when this happened. Therefore:
sk ≤
n∑
j=1
pj , j 6= k
/m
=
n∑
j=1
pj − pk
/m
=
n∑
j=1
pj
/m− pk/m
So we come to
CLSmax = Ck = sk + pk ≤
∑n
j=1
pj
m
− pk
m
+ pk
and so to
CLSmax ≤
∑n
j=1
pj
m
+ pk
(
1− 1
m
)
By part (a) it follows that:
CLSmax ≤ C∗max + C∗max
(
1− 1
m
)
=
(
2− 1
m
)
C∗max
13
(c) To achieve a tight worst-case for the makespan, by List-Scheduling for m = 5 processors,
Cmax =
(
2− 1
5
)
C∗max =⇒ Cmax =
9
5
· C∗max. One example can be a list with 20 jobs having
processing times pj = 1 and one job with time pj = 5. The Gantt-Chart for this list using
List-Scheduling in comparison to the optimum makespan is:
P1
0 1 2 3 4 5 6 7 8 9 10
1 1 1 1 5
P2
0 1 2 3 4 5 6 7 8 9 10
1 1 1 1
P3
0 1 2 3 4 5 6 7 8 9 10
1 1 1 1
P4
0 1 2 3 4 5 6 7 8 9 10
1 1 1 1
P5
0 1 2 3 4 5 6 7 8 9 10
1 1 1 1
P1
0 1 2 3 4 5 6 7 8 9 10
5
P2
0 1 2 3 4 5 6 7 8 9 10
1 1 1 1 1
P3
0 1 2 3 4 5 6 7 8 9 10
1 1 1 1 1
P4
0 1 2 3 4 5 6 7 8 9 10
1 1 1 1 1
P5
0 1 2 3 4 5 6 7 8 9 10
1 1 1 1 1
Using List-Scheduling Cmax = 9, while the optimum makespan is C
∗
max = 5. Cmax =
9
5
C∗max.
14
Problem 11. LPT for P ||Cmax. Note that the original proof by Ron Graham from 1969 is by contradiction. We
use here a prove by case distinction. Let CLPTmax and C
∗
max be the makespans of an LPT-schedule
and an optimal schedule. We are interested in an upper bound for
CLPTmax
C∗max
. Suppose that Jk is the
last job to finish the LPT-schedule, i.e. CLPTmax = Ck.
(a) Prove: CLPTmax ≤ C∗max + pk(1− 1/m).
(b) Suppose that Jk is not the last job to start.
Prove: Removing all jobs that start after time sk (i) does not affect the makespan of our
schedule, and (ii) it can only decrease the optimal makespan for the modified instance with
the truncated job list.
(c) Prove: If pk ≤ C∗max/3, then CLPTmax ≤ C∗max(4/3− 1/(3m)).
(d) Prove: If pk > C
∗
max(T2)/3, then C
LPT
max (T2) = C
∗
max(T2).
(e) Does LPT has the same time complexity as List Scheduling?
Solution:
(a) We know already that an upper bound for the start time of the job Jk that determines the
makespan is sk ≤ ((
∑
pj) − pk)/m. Then it follows directly that CLPTmax = sk + pk ≤ C∗max +
pk(1− 1/m).
(b) (i) Removing all jobs that start after time sk does not affect the makespan of our schedule,
since these jobs must have run on other processors.
(ii) Furthermore, it can only decrease the optimal makespan for the modified instance, since
the total processing time will be the same or decreased (and definitely not increased). Thus, if
we prove an approximation bound for this new instance (with the truncated job set), it applies
a fortiori to our original instance (with all jobs). We can therefore assume that the last job to
finish is the last to start and that it is the smallest job.
CLPTmax
C∗max
≤
CLPTmax (T2)
C∗max(T2)
(c) If pk ≤ C∗max/3, then CLPTmax ≤ C∗max + C∗max/3(1− 1/m) = C∗max(4/3− 1/(3m)).
(d) If pk > C
∗
max(T2)/3, then all jobs have pj > C
∗
max/3, and hence in the optimal schedule there
are at most 2 jobs per processor. Number the jobs in order of nonincreasing pj . If n ≤ m, then
the optimal schedule trivially puts one job on each machine. We thus consider the remaining
case with m < n ≤ 2m. In this case, we claim that, for each j = 1, . . . ,m the optimal schedule
pairs job j with job 2m+ 1− j if 2m+ 1− j ≤ n and places job j by itself otherwise. This can
be shown to be optimal via a simple interchange argument. We finish the proof by observing
that this is exactly the schedule that LPT would construct: CLPTmax (T2) = C
∗
max(T2).
(e) LPT uses the same procedure as List Scheduling but the jobs have to be sorted at first which
takes O(n log n). Therefore it has the same time complexity (in terms of n) as List Scheduling.
15