carbontracking
carbontracking

Reputation: 1089

How to best organise concurrent processing of a set of processes with known duration?

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

Answers (0)

Related Questions