Reduction

(b) Consider the following MULTIPROCESSOR SCHEDULING problem. Input: A set of n jobs with running times ti, 12,... tn a positive integer m (number of Question: Can these jobs be scheduled on m identical processors so that all jobs finish by We assume that once a job i is assigned to a multiprocessor it runs to completion in time t processors), and a finishing time T. time T? i.e., no swapping /time sharing). i. Give an example of a yes instance with n-5, T-5 and m3 where all the times ti 2 marks ii. Explain why there is no possible scheduling for n 5. T-10 and m 3 where the job 2 marks] 4 marks are different. Show the scheduling times are 12,4,7,8,9) (c) Show that BIN PACKING Sp MULTIPROCESSOR SCHEdULING. (b) Consider the following MULTIPROCESSOR SCHEDULING problem. Input: A set of n jobs with running times ti, 12,... tn a positive integer m (number of Question: Can these jobs be scheduled on m identical processors so that all jobs finish by We assume that once a job i is assigned to a multiprocessor it runs to completion in time t processors), and a finishing time T. time T? i.e., no swapping /time sharing). i. Give an example of a yes instance with n-5, T-5 and m3 where all the times ti 2 marks ii. Explain why there is no possible scheduling for n 5. T-10 and m 3 where the job 2 marks] 4 marks are different. Show the scheduling times are 12,4,7,8,9) (c) Show that BIN PACKING Sp MULTIPROCESSOR SCHEdULING