Tutorial 2 solutions
Question 1
1. FIFO: The moves are carried out in the order of arrival. Therefore, they are processed in the following
order: A-B-C-D.
MOT (minimum operating time): Priority is given to the move with the shortest execution time. Thus,
moves are processed in the order D-C-B-A using the TOM method.
PD (promised date): Priority is given to the move for which the promised date to the client is the
closest. Therefore, moves are processed as follows: C-B-D-A.
2. The following performance indicators are commonly used to measure the effectiveness of different
priority rules:
∑ 𝑡𝑖𝑚𝑒 𝑠𝑝𝑒𝑛𝑡 𝑜𝑛 𝑡𝑎𝑠𝑘𝑠
𝐴𝑣𝑒𝑟𝑎𝑔𝑒 𝑡𝑖𝑚𝑒 𝑖𝑛 𝑡ℎ𝑒 𝑠𝑦𝑠𝑡𝑒𝑚 =
𝑛𝑢𝑚𝑏𝑒𝑟 𝑜𝑓 𝑡𝑎𝑠𝑘𝑠
∑ 𝑒𝑥𝑒𝑐𝑢𝑡𝑖𝑜𝑛 𝑡𝑖𝑚𝑒
𝑒𝑓𝑓𝑒𝑐𝑡𝑖𝑣𝑒 𝑢𝑡𝑖𝑙𝑖𝑧𝑎𝑡𝑖𝑜𝑛 𝑜𝑓 𝑡ℎ𝑒 𝑠𝑦𝑠𝑡𝑒𝑚 =
∑ 𝑡𝑖𝑚𝑒 𝑠𝑝𝑒𝑛𝑡 𝑜𝑛 𝑡𝑎𝑠𝑘𝑠
∑ 𝑑𝑒𝑙𝑎𝑦𝑠
𝑅𝑒𝑡𝑎𝑟𝑑 𝑚𝑜𝑦𝑒𝑛 =
𝑛𝑢𝑚𝑏𝑒𝑟 𝑜𝑓 𝑡𝑎𝑠𝑘𝑠
FIFO :
Duration Finish Promised Delay
Date
A 14 14 20 0
B 10 24 16 8
C 7 31 15 16
D 6 37 17 20
Total : 37 106 --- 44
MOT :
Duration Finish Promised Delay
Date
D 6 6 17 0
C 7 13 15 0
B 10 23 16 7
A 14 37 20 17
Total : 37 79 --- 24
DP :
Duration Finish Promised Delay
Date
C 7 7 15 0
B 10 17 16 1
D 6 23 17 6
A 14 37 20 17
Total : 37 84 --- 24
The calculations of performance indicators yields the following results:
∑ 𝑑𝑒𝑙𝑎𝑦𝑠
𝐴𝑣𝑒𝑟𝑎𝑔𝑒 𝑑𝑒𝑙𝑎𝑦 =
𝑛𝑢𝑚𝑏𝑒𝑟 𝑜𝑓 𝑡𝑎𝑠𝑘𝑠
Average time in the system Utilization Average delay
FIFO 106 37 44
= 26.5 𝑑𝑎𝑦𝑠 = 34.91% = 11 𝑑𝑎𝑦𝑠
4 106 4
MOT 79 37 24
= 19.75 𝑑𝑎𝑦𝑠 = 46.84% = 6 𝑑𝑎𝑦𝑠
4 79 4
PD 84 37 24
= 21 𝑑𝑎𝑦𝑠 = 44.05% = 6 𝑑𝑎𝑦𝑠
4 84 4
These results indicate that MOT method is better than the two other methods (FIFO & PD) in terms of the average
time that a task spends in the system as well as the system utilization.
In terms of average delay, methods MOT and PD give the same results. We can conclude that MOT method is a
good recommendation as it gives the best results of the three indicators.
Question 2
1.
Construction 25 26 27 28 29 30
formwork 2 1 5 10 5 3
concrete 4 3 7 8 2 6
Based on Johnson’s algorithm, we have the following order:
26 25 30 27 28 29
2. Johnson’s schedule :
Scheduling with the arrival order:
Time
formwork
concrete
With Johnson’s algorithm, we save 3 days (34-31) comparing with the consctructions based on the arrival order.
3. If we must consider a fixed inter-operational time of 2 days between the end of formwork and the start
of concrete pouring, the order of tasks will not change. Indeed, it is enough to assume that the duration
of each of the two operations will increase by 1 day.
Question 3
1. Denote by Setup A : « SA » ; Setup B : « SB » ; Machining A : « MA » ; Machining
B : « MB »
We cannot apply Johnson’s algorithm, as not all tasks SA, SB, MA, and MB are independent. For example, none
of the operations can be processed on any machine between SA and MA. Moreover, we are not obliged to wait
for the finishing of a part on M1 to start the setup of M2. However, machining on M2 cannot start unless we finish
machining on M1.
2. Four scheduling manners are possible.
Case 1 M1 SA MA SB MB
M2 SA MA SB MB
Case 2 M1 SA MA SB MB
M2 SB MB SA MA
Case 3 M1 SB MB SA MA
M2 SA MA SB MB
Case 4 M1 SB MB SA MA
M2 SB MB SA MA
3. Gantt chart for each case
Time
Time
Time
Time
Therefore, the best schedule is SB-MB-SA-MA over the two machines M1 and M2.
Question 4
1. Optimal schedule based on Johnson’s algorithm : E-C-B-A-D
2.
Time (min)
3. Total execution time: 43 minutes.
Question 5
1. Jackson’s algorithm because the batches are independent (we have 2 machines) and they don’t have the
same order on the two printers.
2. Scheduling of each subset :
BR (blue with red stripes): B-A-C
RB (red with blue stripes): DEF, DFE, FED, FDE
R (red): G
B (blue): H-I
Scheduling blue printer: B-A-C-H-I-D-E-F
Scheduling red printer: D-E-F-G-B-A-C
Blue
Red
Total execution time: 35hours.
Question 6
1. The objective is to minimize the total preparation time. That is, we have to determine the earliest time
station 2 is free.
C1 C2 C6 C3 C5 C4
Therefore, station 2 is free at time: 55h
2. Scheduling on 3 machines:
We note that time on station 2 is dominated by the delivery duration. Therefore, we can model the problem
as a scheduling one on two fictitious machines and then solve it using Johnson’s algorithm.
Orders C1 C2 C3 C4 C5 C6
station 1+ station 2 : A 10 17 15 13 13 20
station 2 + delivery : B 33 29 36 29 21 64
C1 C4 C5 C3 C2 C6
or
C1 C5 C4 C3 C2 C6
C1 C C5 C3 C2 C6
C1 C4 C5 C3 C2 C6
C1 C4 C5 C3 C2 C6
3 10 14 16 23 27 33 38 5 53 61 63 8 111 131 187
0 0
Question 7
Total distance traveled by Taxis.
Customers Customers Customers
A B C D Min A B C D A B C D
1 7 3 4 8 3 1 4 0 1 5
1 4 0 0 5
Taxis
2 5 4 6 5 4 2 1 0 2 1
Taxis
Taxis
3 0 1 3 0 2 1 0 1 1
3 6 7 9 6 6
4 4 2 3 0 3 0 1 2 0
4 8 6 7 4 4
Min 0 0 1 0 4 4 2 2 0
Customers
A B C D
1 4 0 0 5
2 1 0 1 1
Taxis
3 0 1 2 0
4 4 2 2 0
The optimal assignment is as follows : Taxi 1 to customer C, Taxi 2 to customer B, Taxi 3 to customer A, and
Taxi 4 to customer D.
The total distance traveled by Taxis = 6+4+4+4 = 18.
Question 8
1. To balance the assignment problem, we must add a fictitious site located at zero distances from the three
subcontractors.
Sites Sites
Sites
A B C Fic Min A B C Fic
1 50 36 16 0 A B C Fic
subcontrac
1 50 36 16 0 0
subcontrac
1 25 11 2 0
subcontrac
2 28 30 18 0
tors
2 28 30 18 0 0
tors
2 3 5 4 0
tors
3 35 32 20 0 0 3 35 32 20 0
4 25 25 14 0 3 10 7 6 0
4 25 25 14 0 0 4 0 0 0 0
Min 25 25 14 0
The solution is not optimal. The minimum uncovered is equal to 2.
We subtract 2 from all uncovered values and we add it to the double crossed values.
Sites
A B C Fic The minimum uncovered value is equal to 1.
1 23 9 0 0 We subtract 1 of all uncovered values and we add it to the double-crossed values.
Subcontr
actors
2 1 3 2 0
3 8 5 4 0
4 0 0 0 2
Sites Sites
A B C Fic Optimal Tableau A B C Fc
1 23 9 0 1 1 23 9 0 1
Subcontr
Subcontr
2 0 2 1 0
actor
2 0 2 1 0
actor
3 7 4 3 0 3 7 4 3 0
4 0 0 0 3 4 0 0 0 3
construction site
Distance
The optimal assignment is as follows:
1 C 16
Subcontr
actor
With a total distance equal to 69. 2 A 28
4 B 25
Question 9
2. First, we start by balancing the assignment problem by adding a fictitious section generating zero sales by
all salespersons, then transform it into a minimization problem to apply the Hungarian method, and finally
associate a value with the assignments to be avoided. M (penalty) which tends towards infinity in order to
force the algorithm not to retain them.
Suits Shoes Accessories Fic Min Suits Shoes Accessories Fic
Nadia -350 -350 -250 0 -350 Nadia 0 0 100 350
Jamel -650 -650 M 0 -650 Jamel 0 0 650+M 650
Sarrah -450 -450 -150 0 -450 Sarrah 0 0 300 450
Salah -250 M -550 0 -550 Salah 300 550+M 0 550
Min 0 0 0 350
Suits Shoes Accessories Fic
Suits Shoes Accessories Fic
Nadia 0 0 100 0 Nadia 0 0 100 0
Jamel 0 0 650+M 300 Jamel 0 0 650+M 300
Sarrah 0 0 300 100 Sarrah 0 0 300 100
Salah 300 550+M 0 200 Salah 300 550+M 0 200
Two optimal solutions ensuring a total of sales equal to 1650 = 650+450+550.
3. Yes, it suffices to adopt the 2nd solution: assign Jamel to
1st Solution 2nd Solution sales
shoes section, Sarrah to suits section, and Salah to accessories
Nadia - - 0 section.
Jamel Suits Shoes 650
Sarrah Shoes Suits 450
Salah Accessories Accessories 550
