We are given as input a set of n jobs, where job j has a processing time pj, a deadline dj. Given a schedule (i. e., an ordering of the jobs), consider that each job j has the completion time C; we define the lateness l of job j as the amount of time C - d, after its deadline that the job completes, or as 0 if C; < dj. Our goal is to minimize the maximum lateness, maxlj. Consider the following greedy rules for producing an ordering that minimizes the maximum lateness. For each rule, please explain why it gives the optimal ordering or give a counterexample. You can assume that all processing times and dead- lines are distinct.
(a) Schedule the requests in increasing order of processing time Pj.
(b) Schedule the requests in increasing order of the product d; * Pj.
(c) Schedule the requests in increasing order of deadline di.