Algorithms and optimization Our task is to schedule jobs on multiple processors. We have access to as many processors as we'd like, and the goal is to minimize the number of processors we actually use. The processors are labelled P1, P2, .... Each job must begin running exactly at its scheduled start time and nothing else can run on the processor running this job until that job's duration has elapsed. A greedy algorithm for this task is described as follows: Input: Number of jobs n and list of descriptions of jobs ji, ..., jn: for job ji we have its start time bi and its duration di. 1. Order the jobs based on start times. 2. For each job (starting with the carliest), assign it to the lowest numbered processor that is currently available. (a) How many processors does this algorithm use when its input is n=6 and Job Start time | Duration j1 0 3 12 0 2 j3 2 2 14 3 js 3 1 16 1. 2 (b) Come up with two different sequences of jobs (by specifying their start times and durations) such that at least 5 processors are required. Choose your examples so that they have a different number of total jobs from each other. NNN80 Algorithms and optimization Our task is to schedule jobs on multiple processors. We have access to as many processors as we'd like, and the goal is to minimize the number of processors we actually use. The processors are labelled P1, P2, .... Each job must begin running exactly at its scheduled start time and nothing else can run on the processor running this job until that job's duration has elapsed. A greedy algorithm for this task is described as follows: Input: Number of jobs n and list of descriptions of jobs ji, ..., jn: for job ji we have its start time bi and its duration di. 1. Order the jobs based on start times. 2. For each job (starting with the carliest), assign it to the lowest numbered processor that is currently available. (a) How many processors does this algorithm use when its input is n=6 and Job Start time | Duration j1 0 3 12 0 2 j3 2 2 14 3 js 3 1 16 1. 2 (b) Come up with two different sequences of jobs (by specifying their start times and durations) such that at least 5 processors are required. Choose your examples so that they have a different number of total jobs from each other. NNN80