Q1. [30] Job Scheduling Suppose a hair stylist has several customers waiting for
ID: 3606788 • Letter: Q
Question
Q1. [30] Job Scheduling Suppose a hair stylist has several customers waiting for different treatments. The treatments don't all take the same amount of time, but the stylist knows how long each takes. A reasonable goal would be to schedule the customers in such a way as to minimize the total time they spend both waiting and being served, which is called the time in the system. This is called a problem in the svstem. of minimizing the total time There are five jobs and the service times for these jobs are Jobs Service Time 4 14 10 [10] Write a recursive greedy algorithm to decide the optimal sequence of jobs to minimize the total time spent in the system. 1. 2. [10] Design an iterative greedy algorithm for the same problem of 1 3. [10] (A) What is the optimal solution of the above problem, ie. the optimal sequence of job? and (B) What is its minimum total time?Explanation / Answer
1.
2.
3. Short the jobs in increasing order
Jobs Serving Time
A 4
D 5
B 8
E 10
C 14
Follow Shortest job first algorithm:
Waiting time for A = 0 = 0
Waiting time for D = 0+4 = 4
Waiting time for B = 0+4+5 = 9
Waiting time for E = 0+4+5+8 = 17
Waiting time for C = 0+4+5+8+10 = 27
Total waiting time = 0+4+9+17+27 = 57
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.