xuebaunion@vip.163.com

3551 Trousdale Rkwy, University Park, Los Angeles, CA

留学生论文指导和课程辅导

无忧GPA：https://www.essaygpa.com

工作时间：全年无休-早上8点到凌晨3点

微信客服：xiaoxionga100

微信客服：ITCS521

运筹学代写-MAT021

时间：2021-02-14

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.

学霸联盟

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.

学霸联盟