A Scheduling Problem:

Consider that there are *n* jobs, each with a deadline di and a required processing time *ti*, and all jobs are available to be scheduled starting at time *s*. For a job i to be done, it needs to be assigned aperiod from *si* >= *s* to *fi* = *si* + *ti*, and different jobs should be assigned non overlapping intervals. In Particular, consider the case in which each job must be done by its deadline, or not at all. We'll say that a subset *J* of jobs is *schedulable* if there is a schedule for the jobs in *J* so that each of them finishes by its deadline. Select a schedulable subset of maximum possible size and give a schedule for this subset that allows each job to finish by its deadline. a. Prove that there is an optimal solution *J* (i.e., a scheduleable set of maximum size) in which the jobs in *J* are scheduled in increasing order of their deadlines. b. Assume all deadlines di and required times *ti* are integers. Give an algorithm to find an optimal solution. Your algorithm should run in time polynomial in the number of jobs n, and the maximum deadline *D* = max*i* *di*. ## Deliverables 1) Pseudocode 2) C code 3) Description of proof, in English. 4) Full Documentation. ## Platform plain text