Date: 01/19/06 (Algorithms)    Keywords: no keywords

Optimizing task load

I have a number of airplanes with known fuel capacity and a many locations to visit, the goal is to send out as few airplanes as possible and also to having their loads as balance as possible proportionally to their fuel capacity.

A greedy method is probably sort the airplane in decreasing order based on their fuel and try to assign as many locations as possible to the first airplane, after that one is out of fuel, continue with the next, …. Obviously this will be very unbalance as the first airplane has a whole bunch of locations why the last probably just has a few (especially in the case when their fuel capacities are similar).

(Note if locations 1 2 3 … n are assigned to an airplane then that airplane will go from its base -> 1 -> 2 -> 3 -> base).

Is there a polynomial time for this or it is one of NP- Hard problem time scheduling or Knapsack (that’s the thief problem right?) problems ?

Thanks

Source: http://community.livejournal.com/algorithms/71117.html