Algorithms For Dummies

  Working with Greedy Algorithms 

     293

a  few  jobs  on  a  single  machine,  but  if  you  have  hundreds  of  them  on  multiple 

machines, that becomes a very heavy computational problem. A greedy algorithm 

can  save  the  day  without  much  planning:  just  execute  the  shortest  first.  The 

resulting average will be the smallest possible: (3+(3+4)+(3+4+8)+(3+4+8+12))/4=

13 hours on average.

To obtain the average wait time, you take the average of the cumulated sums of 

runtimes. If you instead take the average of raw times, you obtain the average 

length of a task, which doesn’t represent the customer’s waiting time.

The greedy principle is simple: Because you sum cumulative times, if you start by 

running the longest tasks, you extend the longest run to all successive execution 

times (because it is a cumulative sum). If instead you start with the shortest jobs, 

you draw the smallest times first, positively affecting the average (and your cus-

tomers’ level of satisfaction).