20.2. Greedy Strategies

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 request 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 time 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.

This chunk introduces the Minimizing Lateness problem, where we have a single resource (like a machine) that must complete requests that come with specific deadlines. Each request takes a certain amount of time to complete and has a deadline by which it should ideally finish. If a request finishes after its deadline, it is considered 'late'. The primary goal is to create a schedule that minimizes the maximum lateness across all requests, meaning we want to ensure that the longest delay experienced by any request is as small as possible.

Imagine a pizza shop with an oven that can cook only one pizza at a time, and every pizza order has a specific delivery time. If a pizza isn't ready by its delivery time, it is considered late. The challenge for the chef is to cook the pizzas in such a way that the one with the latest delivery time is delivered as close to on time as possible, thereby minimizing overall lateness.

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.

The text discusses potential greedy strategies to minimize lateness, starting with the idea of scheduling the shortest jobs first. However, it quickly notes this is not always effective. For example, if there are two jobs: one that takes only 1 time unit with a far-off deadline and another that takes 10 time units with a near deadline, scheduling the shortest job first could result in overall lateness. Hence, just selecting the shortest jobs does not guarantee the best outcome, demonstrating that greediness does not always yield the optimal solution.

Thinking about waiting at a traffic light, if you choose to go as soon as the light turns green (like picking the shortest job first), you might bypass a longer, smoother road to avoid future traffic. It may seem like a good strategy to accelerate, but it could lead you to a longer delay overall if you enter a busier intersection.

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.

This chunk provides a specific example that undermines the 'shortest job first' strategy. It explains how choosing to finish a job that takes only 1 time unit first, when its deadline is much later than the job that takes 10 time units, can result in a late finish for the second job. This highlights the importance of deadlines in scheduling, demonstrating that the order in which jobs are done can greatly affect their overall lateness, regardless of their completion time.

Picture a student deciding to complete an easy, short assignment first, while ignoring an upcoming big project with a near deadline. While the short assignment was quick to finish, not working on the larger task could easily lead to a last-minute rush and potentially missing its deadline, resulting in a poorer outcome.

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 closes to the deadline. So, we look at the slack how much time we can effort to delay start in my job, d j minus t j and pick those which have the smallest slack.

In this chunk, the text introduces another greedy strategy that focuses on selecting jobs based on their slack time, which is the difference between the deadline and the time required to complete the job. The goal is to pick jobs that have the smallest slack, meaning they are closest to being overdue, under the assumption that managing tighter deadlines will reduce overall lateness. However, it also mentions a counterexample, proving that this strategy can also lead to poor results.

Consider planning a day with various appointments. If you prioritize meetings that are about to start but neglect those that are scheduled later but are more significant, it could cause you to run out of time and miss an important meeting, even if the first one was completed on time.

So, 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.

This chunk establishes that the optimal greedy strategy for minimizing lateness involves scheduling jobs in order of their deadlines. By prioritizing jobs with the earliest deadlines, the likelihood of incurring lateness is reduced. The expectation is that other strategies fail under specific conditions that do not consider deadlines as a primary factor.

Think of a student prioritizing assignments due soonest. By focusing on completing what's due first, the risk of late submission decreases, and the student is better organized, leading to a more successful outcome at the end of the semester.

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 then or equal to deadline of 2 and so on.

This chunk begins the process of proving that the strategy of scheduling by deadline is indeed the optimal one. By numbering the jobs according to their deadlines and examining the implications of such an arrangement, it lays the groundwork for a rigorous proof that demonstrates the effectiveness of only scheduling jobs based on their priorities (deadlines).

Imagine a student with multiple deadlines - if they list their assignments in chronological order based on when they're due and follow that list strictly, they greatly reduce the chances of forgetting or being late with any submission.

So, since we have scheduling jobs one after the other without waiting, it is very clear that this schedule has no gaps, it has no idle time. The resource that we are trying to allocate is continuously in use, until all n requests are finished.

This chunk emphasizes that by scheduling jobs back-to-back in order of deadlines, there will be no idle time for the resource (like a machine or worker). This continuous allocation of the resource is essential to minimize lateness, as it ensures every available moment is utilized for work without delays.

Think of an assembly line where each stage of production leads directly to the next without pauses. If one step stops, it causes delays for all subsequent steps. Keeping each stage moving continuously maximizes productivity, similar to scheduling jobs without idle gaps.

So, 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.

This piece discusses that for a schedule to be optimal, it should not have any 'inversions'. An inversion occurs when a job that needs to be finished earlier is scheduled after a job that has a later deadline. The text explains how we can identify and rectify these inversions by swapping jobs without altering the optimality of the schedule.

Imagine you’re organizing a cooking competition with multiple dishes, each with specific final presentation times. If you accidentally have one dish planned to be served earlier but scheduled later, swapping that with a later dish that’s not due yet keeps the competition running smoothly without changing overall timings.

So, 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 short the job is by deadline and then read out in this schedule in the same order.

The concluding chunk reflects on the effectiveness and ease of implementing the greedy strategy based on deadlines. It highlights not just the proofs of correctness but also notes the execution efficiency of the algorithm, suggesting that sorting jobs takes O(n log n) time, while the actual scheduling process would take linear time O(n), making the overall computation manageable.

Consider using a calendar app that automatically orders your tasks by their due dates. With just a bit of sorting (analogous to the complexity noted above), you can make sure everything is lined up perfectly for timely completion, allowing you to coalesce your efforts smoothly.

--