Finding a Schedule That Works

You have a set of tasks for a robot. There is no precedence constraint requiring any task to be completed before another. Each requires a certain amount of time and has a certain deadline. Your predecessor assures you there is enough time for the robot to do everything, but he doesn’t remember how. (His lack of organization explains why he is your predecessor and not your boss.) You have to arrange things so your robot finishes each task by its deadline.

1. In which order do you schedule the tasks starting from current day 0?

   • Task T1 takes 4 days with deadline on day 45

   • Task T2 takes 4 days with deadline on day 48

   • Task T3 takes 5 days with deadline on day 25

   • Task T4 takes 2 days with deadline on day 49

   • Task T5 takes 5 days with deadline on day 36

   • Task T6 takes 2 days with deadline on day 31

   • Task T7 takes 7 days with deadline on day 9

   • Task T8 takes 5 days with deadline on day 39

   • Task T9 takes 4 days with deadline on day 13

   • Task T10 takes 6 days with deadline on day 17

   • Task T11 takes 4 days with deadline on day 29

   • Task T12 takes 1 day with deadline on day 19

Hint: 

The best algorithm for this problem has the very suggestive name: “Earliest Deadline First.”

Solution to Finding a Schedule That Works

1. In which order do you schedule the tasks starting from current day 0?

This is a situation where you don’t want the computer to explore all cases, trying all 12! Orderings might take a while and would be completely impractical if there were even 20 tasks. As alluded to in the hint, there is an efficient scheduling algorithm with a very suggestive name: Earliest Deadline First. In fact, the name is the algorithm. That is, you first do the task with the earliest deadline and continue to do every other task in deadline order. In this case, the algorithm gives us an ordering:

 T7 T9 T10 T12 T3 T11 T6 T5 T8 T1 T2 T4

Call a schedule in which every task completes by its deadline a “good schedule.” Earliest Deadline First has the following excellent property: If there is a good schedule for a set of tasks, then using Earliest Deadline First on those same tasks will find one. The proof is simple and elegant. See if you can think how it might go before reading on.

Suppose that in a good schedule S, task T executes just before T’ even though T has a later deadline than T’. Suppose further that T is the first task for which this is true. Because both T and T’ complete before their deadlines, swapping the two will still enable them to complete before their deadlines. (To be concrete, suppose that T has deadline d and T’ has deadline d’. By assumption d’ < d. In the original schedule, both T and T’ complete by their deadlines, so both finish by time d’. Swapping them will preserve that property.) Thus, we can always transform a good schedule into another one in which tasks execute in deadline order.

Unfortunately, sometimes a system is overloaded, and that can change Earliest Deadline First from a great strategy to a really poor one. For example, what is the shortest task you could add to the above list to cause Earliest Deadline First to miss every deadline? For now, assume that your robot will continue working on a task T even after its deadline has passed, provided T has the earliest deadline of all uncompleted tasks. Give it a try.

A task requiring 3 days with deadline 2 or earlier will do it. That new task will fail to complete by its deadline and will cause every other task to miss its deadline as well.

Working on a task after its deadline has passed may seem foolish. It would be far better to drop some tasks and complete others. We’ll work on such a strategy in the puzzle “Overloaded Scheduling and Freezing Crystals.” The fundamental point here is that a naive greedy approach can be brittle, that is, it may work well until a certain load and then cease to work entirely.