1. Why is the heuristic of doing the most expensive job first
not optimal? Well, suppose that there are 5 jobs: 45 min, 40
min, 15 min, 11 min, 9 min and two machines. According to the
heuristic, they should be scheduled this way m1: 45 min, 11 min
m2: 40 min 15 min, 9 min But it would be better for m2 to do 11
and 9 when it's finished with the 40 minute job. Then all jobs
would complete in 60 minutes rather than 64 minutes. 2. Order
the items from longest to shortest. Put the trucks in a line.
For each item, put it on the first truck on which it will fit.
All trucks but one will be at least half full. Here is why: if
any two trucks A and B are less than half full and A precedes B
in line, then all the items on B would have gone on A or onto
some other truck. So this is within a factor of two of the
minimum possible number of trucks (possibly with one extra
truck). In practice, it will usually be much better. 3. Go up
and down the minimum spanning tree edges as shown in Figure 3.
Since the minimum spanning tr