Reputation: 1089
We have a task handling system that handles a number of tasks, between 12 and 16 at any given batch, using 4 CPU's. Each task takes a known amount of time on a single CPU.
At the moment, the order of selecting the tasks to run is arbitrary. The tasks are not interdependent. We end up with having one CPU running on its own for the last task. The entire batch is handed on to the next step only once the last task is completed.
I'm hoping to find a way to optimise the ordering of the tasks to minimise this time at the end where only one CPU is running.
As an example:
Task Time (seconds)
Oxygen 78
Air Conditioning 78
Air Contamination 79
Pneumatic 80
Electrical Power 80
Ice Rain Protection 80
Brake Temperature 82
Fuel 84
Tyre 86
SMA TMA Degradation 93
Landing Gear 110
Engine Oil 113
Bleed Leak 127
In the example above, if I take the largest-first method (i.e. reverse order to list above) then all 13 tasks are completed in 337 seconds.
However I see that our system takes the above task in the order of 1,4,9,2,5,11,12,3,13,10,8,6,7 (with 1 being the first in the list above etc.) and this gives a total time of 322 seconds.
Following the links from the first replier (many thanks) I find that my problem is known as multiprocessor scheduling and that there are algorithms for this, so I'll keep hunting.
Upvotes: 0
Views: 37