Question

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.

Answer 1

See the explanation for the answer.

Step-by-step explanation:

a) If a job has a large processing time and a nearer deadline, it will be completed late. Hence the lateness is not minimized.

(b) A combination of deadline and processing time measures the priority better as a nearer deadline job will be processed first and if two jobs have the same deadline, the one that can be processed quicky will be processed first. So scheduling the request based on dj X pj will minimize the maximum lateness.

(c) If two jobs have the same deadline and one job takes a lot of processing time, it is better to process the shorter job first to minimize the lateness. So scheduling the request based on dj will not minimize the lateness.