4.a. A small auto-repair shop has six cars in for repair. Only repairman Murat U

Question

4.a. 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

(a) Suppose that the cars’ owners are waiting in the rest room of the repair shop, and each car owner will leave the
shop when his/her car is finished. Furthermore, Murat Usta serves tea and cookies to his customers and this
costs him $6 per customer per hour of customer waiting time. Which sequence to repair the cars would you
recommend Murat Usta to follow?

(b) 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 same 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.

(c) Suppose that each car owner leaves the shop without waiting in the rest room of the repair shop. MuratUsta
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

In the first fit algorithm we put people or things where the space is available in order of their arrival or they come.

Now, this algorithm can be optimized by sorting the list of elements into decreasing order also known as First Fit Decreasing order.

Car        Time

Decreasing Order

Car             Time

4                   25

6                   30

3                   40

5                   70

1                  115

2                  145

A. As the question does not require any specific algorithm method, it will be wiser to use First Fit algorithm or increasing method where all the customers are serviced based on their arrival.

B. If Musta Urat appoints another repairman to fulfil his duties to repair the car then based on his repair time which is same as Musta Urat’s then the time needed to repair a car will be cut in half, only if Murat Usta and Mehmet Usta both repair the vehicles together.

Which will be

Car        Time     New Time

Now by applying FFD algorithm:

Decreasing Order

Car             Time            New Time

4                   25                12.5

6                   30                15

3                   40                 20

5                   70                 35

1                  115                 57.5

2                  145                 72.5

Recommendation:

FFD algorithm is most suited for the job.

Now, if any one of them carries the duty then also FFD algorithm is more suited for the job.

Related Questions

Navigate

• Browse (All)
• Browse 4
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.