(a) Scheduling. IT is trying to write a scheduler for two identical machines. Th
ID: 3699649 • Letter: #
Question
(a) Scheduling. IT is trying to write a scheduler for two identical machines. They know that there are n jobs and that the ith job takes ti seconds, regardless of which machine it is assigned to (the machines are identical). Each ti is a positive integer. Each job must be assigned to one of the two machines, and we want to assign jobs so as to minimize the completion time of the last job to finish. More precisely, if we assign a set SI ? {1, . . . , n} of jobs to the first machine then we necessarily assign S2- (L ,n} S1 to the second. The finish time is F1 = ??i751 ti for machine one and F2 = ??i752 ti for machine two. The final finish time is then F max(F1,F2). Design an efficient algorithm to find the cost of the optimal schedule, which is the smallest value F attainable by an assignment of jobs to machines. You do not need to find the assignment itself. If each ti is a k-bit integer, what is the running time of your algorithm as a function n and k?Explanation / Answer
Algorithm:
Input: Job set S containing n jobs and their time durations (t1,t2,...tn).
Output: A division S into s1,s2 with minimum finish time.
1. Find sum of time duration of n jobs.
sum= t1+t2+...+tn
2. Sort jobs according to their time duration
3. Assign first k jobs to machine 1 whose sum of time duration is sum/2 as follows:
3.1 s=0
3.2 for i=1 to n
3.3 s=s+ti
3.4 if(( s)<sum/2)
3.5 assign job i to machine 1
3.6 else
3.7 break
4. assign rest jobs to machine 2
Running time:
step 1 takes O(n) time to find sum
for step 2 as each ti is k bit integer, we can sort these by applying radix sort
in O(n+k) time.
step 3 and 4 takes O(n) time
So overall time complexity of this algorithm is : O(n+k)
Note: In algorithm s is a variable with initial value 0. In for loop from line 3.2 to 3.7 in each iteration it stores sum of time duration upto ith jobs (in sorted order). Jobs for value of 's' value is less than sum/2 is assigned to machine1 and rest of the jobs are assigned to machine 2.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.