MAT021 – Example Exam Questions - Solutions
Scheduling
Question 1

A company has to complete the following jobs:

Job A B C D E F
Processing Time 27 38 35 24 42 30
Due Date 93 88 120 71 140 97

They wish to minimise the number of tardy jobs. Find the optimal ordering
using Moore’s algorithm.

Use EDD:

Job Processing Time Completion Time Due Date Tardiness
D 24 24 71 0
B 38 62 88 0
A 27 89 93 0
F 30 119 97 22
C 35 154 120 34
E 42 196 140 56

3 tardy jobs. First tardy job is F. Choose the longest of {D, B, A, F} = B and
move it last. New sequence:

Job Processing Time Completion Time Due Date Tardiness
D 24 24 71 0
A 27 51 93 0
F 30 81 97 0
C 35 116 120 0
E 42 158 140 18
B 38 196 88 108

2 tardy jobs. First tardy job is E and longest job of {D, A, F, C, E} is E. Move E
last but as B and E have now been moved last, the best solution we can get is
2 tardy jobs. Therefore the algorithm stops.


Question 2

i) Explain the flow shop scheduling problem.

See notes.

ii) 7 parts need to be constructed on two machines. Each job must be
processed on Machine 1 before being processed on Machine 2. The
processing time of each part on each machine is as follows:

Part Time on Machine 1 Time on Machine 2
1 6 3
2 2 9
3 4 5
4 1 3
5 7 1
6 6 5
7 7 6
Use Johnson’s algorithm to schedule the parts on each machine. What is the
makespan?

Sequence is 4-2-3-7-6-1-5

See Figure One. Makespan = 34.

Location Problem
A company has to decide where to locate their main office. They wish to locate it on
the following road network that links towns A to F. Roads connect :
A and B – length 24
A and D – length 10
A and E – length 27
A and F – length 5
B and C – length 17
B and D – length 12
B and E – length 21
Given the office should be located somewhere along the road connecting A and B,
and the company wish to minimise the maximal distance anyone has to travel from
any of the towns, use Hakimi’s Algorithm to find the optimal location. State in your
answer the distance from the optimal location to the furthest town.

See Figure 2 and 3.
Note that in the formula Ti’ = d(A, B) + d(B, A) – ε the first value d(A,B) is the length
of the arc AB (24) and the second value d(B, A) is the length of the shortest path
between B and A which is 22 in this case. Usually the two values are the same but
not in this case.

TA = d(A,A) + ε = ε TA’ = d(A,B) + d(B, A) – ε = 46 – ε
TB = d(A, B) + ε = 22 + ε TB’ = d(A, B) + d(B, B) – ε = 24- ε
TC = d(A, C) + ε = 39 + ε TC’ = d(A, B) + d(B, C) – ε = 41- ε
TD = d(A, D) + ε = 10 + ε TD’ = d(A, B) + d(B, D) – ε = 36- ε
TE = d(A, E) + ε = 27 + ε TE’ = d(A, B) + d(B, E) – ε = 45- ε
TF = d(A, F) + ε = 5 + ε TF’ = d(A, B) + d(B, F) – ε = 51- ε
Optimal solution is where TF meets TE’ so 5 + ε = 45 – ε so ε = 20 and the distance =
25.

Dynamic Programming
A political campaign is nearing the election and one candidate has sufficient funding
to purchase 6 adverts on TV stations located in three different areas. There must be
at least one advert in each area but it is believed that showing more than three
adverts in a single area will not produce any additional votes. Based on polling
information, an estimate has been made of the number of additional votes that will
be won in the different areas depending on the number of adverts. The estimates are
as follows (in thousands):

Area
No. Adverts 1 2 3
1 4 6 5
2 7 8 9
3 9 10 11

Use dynamic programming to determine how the 6 adverts should be distributed
among the three areas in order to maximise the estimated number of votes won.
Give all optimal solutions.
N = areas left to consider, I = remaining adverts, k = number of adverts allocated at
current area.
See Figure 4
n i k r(n,I,k) f(n,i)
0 1 - 0 0 f(0,1)
0 0 - 0 0 f(0,0)
1 4 3 11 11 f(1,4)
1 3 3 11 11 f(1,3)
1 2 2 9 9 f(1,2)
1 1 1 5 5 f(1,1)
2 5 1 6 6 + f(1,4) = 17
2 8 8 + f(1,3) = 19 *f(2,5)
3 10 10 + f(1,2) = 19 * f(2,5)
2 4 1 6 6 + f(1,3) = 17 * f(2,4)
2 8 8 + f(1,2) = 17 * f(2,4)
3 10 10 + f(1,1) = 15
2 3 1 6 6 + (1,2) = 15 f(2,3)
2 8 8 + f(1,1) = 13
3 6 1 4 4 + f(2,5) = 23
2 7 7 + f(2,4) = 24 * f(3,6)
3 9 9 + f(2,3) = 24 * f(3,6)

Solution = 36.
From (3,6) there are 2 solutions – allocate 2 or 3 to the first area.
If we allocate 2 to the first area we are then at (2,4) so should allocate 1 or 2 to area
2.
If we allocate 3 to the first area we are then at (2,3) and we should allocate 1 to the
second area.
When we come to the remaining area we allocate all of the remaining adverts. Our
solutions are 2-1-3, 2-2-2 and 3-1-2. All have a value of 24.














































































































































学霸联盟