20.4. Scheduling Jobs

We now look at a different Greedy Algorithm with a slightly more complicated proof of correctness. So, the problem we are looking at is called Minimizing Lateness. So, like our interval scheduling problem in the last example, we have a single resource and there are n requests to use this resource. So, now unlike the earlier situation where we had a start time and a finish time and the resource had to be scheduled within this time. Here we just know that each request i requires time t of i to complete and each request i comes with a deadline d of i, here we are going to schedule every request. So, each request j will started at time start of j, it is called s j and it will take t j, so it will end at f of j, the finish time of j which will be the start time plus the time it takes to process request j. Now, if this finish time is bigger than the deadline, then it is late, so the amount that it is late is given by the difference between the delay and the finish time and the goal is to find a schedule which minimizes the maximum lateness. So, we want to minimize the maximum value of this l j over all the jobs j.

In the Minimizing Lateness problem, we have a resource that requests for jobs with known durations and deadlines. The key focus here is on scheduling the jobs effectively such that we minimize the lateness, which is defined as the difference between the job's finish time and its deadline when the finish time exceeds the deadline. If a job finishes on or before its deadline, its lateness is zero. The goal is to create a schedule that minimizes the maximum lateness across all jobs.

Think of a delivery service where each package has a deadline for delivery. If the driver schedules deliveries with the aim to minimize delays, they must carefully consider which orders to prioritize, similar to our scheduling problem. If they finish late on one urgent package while completing a less urgent one on time, the lateness accumulates and could lead to penalties or unhappy customers.

So, since we know we are looking for greedy strategies, let us try and suggest some greedy strategies for this problem. So, suppose we want to finish jobs as quickly as possible, so we choose a shortest job first, so we choose jobs in increasing order of length. So, this could be a greedy strategy, but unfortunately there is a fairly simple counter example. So, suppose we have 2 jobs job 1 takes 1 time unit and job 2 takes 10 time units, but the deadlines are 110 and 10 respectively. In other words, the first job has a very long gap within which it can be scheduled without any penalty, whereas this second job has to finish more or less assuming it starts finishing. So, now if you pick this shortest job then we are going to incur a lateness of 1, because we are going to go from 1 and then we are going to go from 2 to the 11. So, the second job is going to finish 1 unit of time late, on the other hand if we do 1 to 10 then we do 11, then we get no lateness, we get lateness 0. So, here picking the shortest job first does not give us the best answer.

The examination of greedy strategies starts with the 'shortest job first' concept, where you would think that finishing quicker jobs first might minimize lateness. However, a counterexample demonstrates that this is not always effective. By scheduling two jobs—a short job (1 time unit) and a longer job (10 time units) with significantly different deadlines—we see that finishing the shorter task first results in a late completion of the second job, leading to non-optimal scheduling. This means that our intuitive greedy method doesn't guarantee the best outcome in all scenarios.

Imagine a restaurant with orders to complete. If the chef decides to cook all quick orders first (like a salad) before tackling a complex dish (like a roasted chicken), they might end up missing the deadline for the more urgent chicken order, causing delays, even though they moved quickly on the easier tasks.

So, the second strategy might be to pick those jobs, so earlier we saw that we had a job which had 10 time units and it will also need it had a deadline of 10. So, we need to pick those jobs perhaps whose time is closest to the deadline. So, we look at the slack how much time we can afford to delay starting my job, d j minus t j and pick those which have the smallest slack.

In this strategy, the focus is on the 'slack' which is defined as the time available before a job's deadline minus the job's processing time. The idea is to prioritize jobs based on the least amount of slack, believing they are at greater risk of lateness. However, the analysis shows that even this strategy may not yield optimal results as illustrated by another counterexample, where prioritizing the job with the smallest slack led to increased lateness overall.

Consider a final exam schedule. If a student prioritizes studying for a test that occurs soon (with little slack) over a later one, it may make sense until they realize that their preparation for the later exam was essential in the first place. Balancing urgency and importance is just as tricky in scheduling jobs as it is in academic preparation.

So, it turns out that a greedy strategy that does work is to choose the job with earliest deadline d of j first, the challenge is to proof that this strategy is in fact correct.

The successful greedy strategy involves scheduling the jobs based on their deadlines, starting with the job that has the earliest deadline. This approach ensures that we address the most urgent tasks first and minimizes the chances of incurring lateness. The proof of correctness behind this strategy involves ensuring that no job is delayed unnecessarily, solidifying this method as an optimal solution.

Think of scheduling tasks in a day. If you list your appointments or deadlines early in the morning and tackle them based on urgency (like a work meeting before social appointments), you are likely to complete tasks on time, avoiding any last-minute rush or lateness.

So, to proof that is correct we will first assume that we have actually numbered all our jobs in order of deadline. So, we number our jobs 1, 2, 3 up to n, so let that the deadline of 1 is less than or equal to deadline of 2 and so on. Now, having done this our schedule is very straightforward, we just schedule job 1 first, then job 2, then job 3 and so on.

The proof goes on to arrange jobs by their deadlines and schedule them sequentially. By doing this, where each job is scheduled based on its position in the sorted list of deadlines, it becomes evident that this approach minimizes overall lateness since no job is started too late for its deadline.

Just like stacking books to read in order of priority, if you read the most critical ones first, you ensure that you finish them on time rather than procrastinating on the more urgent reads in favor of the less critical ones.

Our strategy processes and schedules jobs in order of deadlines, so we can say that this schedule O, your optimum schedule has an inversion, if it actually has two jobs which appear out of order within deadline. Every time you have an inversion, we can swap these jobs without affecting the overall lateness, leading us to conclude that we can transform any arbitrary optimum schedule to our greedy schedule that follows the deadline-first rule.

The exchange argument states that if an optimum schedule has jobs that contradict the order of processing based on the earliest deadlines (an inversion), these two jobs can be swapped without negatively affecting the lateness. This transformation can be applied repeatedly until an equivalent schedule to our greedy approach is created, confirming its optimality.

Imagine rearranging a list of tasks; if two tasks can be swapped without altering your overall workload, you naturally improve efficiency by organizing your tasks better—similar to optimizing our job schedules.

Therefore, the trick in this problem was to actually prove that the greedy strategies was correct, the implementation and the complexity are very easy to calculate, we just have to sort the jobs by deadline and then read out in this schedule in the same order.

In summary, the greedy algorithm for scheduling jobs effectively minimizes the maximum lateness through careful selection based on deadlines, and we've shown that this method is optimal. The computational complexity remains efficient, involving sorting the jobs and scheduling them based on their sorted order.

This is akin to scheduling meetings by priority; once the schedule is sorted by time, following it becomes straightforward, enabling efficient use of a calendar without missing essential appointments.

--