Proficiency Assignment: Scheduling with Duration and

Deadline $($This is NOT a coding problem$)$

Topic: Greedy Algorithms.

In class, we discussed one version of the classic Scheduling problem in which we are presented with tasks and try to schedule them so as to complete them as efficiently as possible. This assignment is another variation on the same problem.

In this version of the Scheduling problem, we are given N tasks, each task defined by a Duration and a Deadline. All tasks must be completed. Tasks may be run at any time, but once started a task must continue for its full duration. For a given schedule, each task is assigned a "Lateness" score $($the difference between its finishing time and its Deadline, minimum zero. No bonus points for finishing a task early!$)$ The Lateness of an entire schedule is the maximum lateness among individual jobs in the schedule.

Claim: "Earliest Deadline First" is a greedy algorithm that minimizes the lateness of the schedule.

Your task is to complete an Exchange proof for this greedy algorithm. You may find the following Lemma useful: If there are two jobs $\backslash ($ A $\backslash )$ and $\backslash ($ B $\backslash )$ that are out of order within the schedule, then there are two jobs $\backslash ($ A $\backslash )$ and $\backslash ($ B $\backslash )$ that are not only out of order but also adjacent within the schedule. $($In other words: A$-$then$-$B with no other jobs inbetween.$)$

Once you have written and submitted your proof via Canvas, schedule a $10$ minute meeting with me to present your proof.

I will ask you about

$-$ Your OPT and OPT$*($what exchange are you making?$)$

$-$ The cases that you need to cover

$-$ Why OPT$*$ works in each case