Algorithms For Dummies

Meeting deadlines

Sometimes, more than just wanting to make your customers wait less time, you 

also have to respect their time requirements, meaning that you have deadlines. 

When you have deadlines, the greedy mechanism changes. Now you don’t start 

from the shortest task but with the task that you must deliver the earliest, accord-

ing to the principle the earliest, the better. This is the problem of hard deadlines, 

and  it’s  a  problem  you  can  actually  fail  to  solve.  (Some  deadlines  are  simply 

impossible to meet.)

If you try a greedy strategy and can’t solve the problem, you can acknowledge that 

no solution to the required deadline exists. When hard deadlines can’t work, you 

can try to solve the problem using soft deadlines instead, meaning that you have 

to respect a priority (executing certain tasks first).

In this example, you have both the lengths of the tasks, as discussed in the previ-

ous  section,  and  you  have  a  value  (a  weight)  that  defines  the  task  importance 

(larger weights, higher priority). It’s the same problem, but this time you must 

minimize the weighted average completion time. To achieve this goal, you create 

a priority score by dividing the time lengths by the weights, and you start with the 

tasks that have the lowest score. If a task has the lowest score, it’s because it is 

high priority or very short.

For instance, reprising the previous example, you now have tuples of both weights 

and lengths: (40,8), (30,4), (20,12), (10,3), where 40 in the first tuple is a weight 

and 8 is a length. Divide each length by the weight and you get priority scores of: 

0.20, 0.13, 0.60, and 0.30. Start from the lowest-priority score and, adding the 

---

294