4.c. A small auto-repair shop has six cars in for repair. Only repairman Murat U
ID: 363314 • Letter: 4
Question
4.c. A small auto-repair shop has six cars in for repair. Only repairman Murat Usta is available to do repairs. He
estimates the following times needed to repair cars.
Car
1
2
3
4
5
6
Repair Time (minutes)
115
145
40
25
70
30
(c) Suppose that each car owner leaves the shop without waiting in the rest room of the repair shop. Murat Usta
will call car owners when all cars are finished. Furthermore, Murat Usta decides to hire the repairman, whose
name is Mehmet Usta and his repair speed is twice as fast as Murat Usta. Apply the First-Fit Decreasing (FFD)
algorithm to develop a schedule to recommend Murat Usta to complete all car repairs in a shortest possible
time.
Car
1
2
3
4
5
6
Repair Time (minutes)
115
145
40
25
70
30
Explanation / Answer
First-Fit Decreasing algorithm takes up the jobs in the decreasing order of their processing times
Therefore sequence is
Car 4 having time 25
Total time for all cars is 425 minutes
In case of Mehmet the time taken is half as compared to Murat
Mehmet may start with car 2 and Murat with car 1
Processing of car 2 completed in 72.5 minutes
Mehmet next takes Car 5 which is processed by 107.5 minutes (72.5+35)
Therefore, Mehmet may take up car 3 next which is processed by 127.5 minutes
Car 1 processing is completed by 115 minutes so Murat takes car 6 and its processing is completed by 145 minutes
Mehmet takes car 4 at 127.5 and its processing is completed by 140 minutes (127.5+12.5)
Therefore all cars are processed in 145 minutes.
Car 2 having maximum-145 Car 1 having time-115 Car 5 having time-70 Car3 having time-40 Car 6 having time-30Car 4 having time 25
Total time for all cars is 425 minutes
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.