load balancing algorithms - special example

Let´s pretend i have two buildings where i can build different units in. A building can only build one unit at the same time but has a fifo-queue of max 5 units, which will be built in sequence. Every unit has a build-time. I need to know, what´s the fastest solution to get my units as fast as possible, considering the units already in the build-queues of my buildings. "Famous" algorithms like RoundRobin doesn´t work here, i think.

Are there any algorithms, which can s开发者_开发知识库olve this problem?

This reminds me a bit of starcraft :D

I would just add an integer to the building queue which represents the time it is busy. Of course you have to update this variable once per timeunit. (Timeunits are "s" here, for seconds)

So let's say we have a building and we are submitting 3 units, each take 5s to complete. Which will sum up to 15s total. We are in time = 0. Then we have another building where we are submitting 2 units that need 6 timeunits to complete each.

So we can have a table like this:

Time 0 
Building 1, 3 units, 15s to complete.
Building 2, 2 units, 12s to complete.

Time 1
Building 1, 3 units, 14s to complete.
Building 2, 2 units, 12s to complete.

And we want to add another unit that takes 2s, we can simply loop through the selected buildings and pick the one with the lowest time to complete. In this case this would be building 2. This would lead to Time2...

Time 2
Building 1, 3 units, 13s to complete
Building 2, 3 units, 11s+2s=13s to complete

...

Time 5
Building 1, 2 units, 10s to complete (5s are over, the first unit pops out)
Building 2, 3 units, 10s to complete

And so on.

Of course you have to take care of the upper boundaries in your production facilities. Like if a building has 5 elements, don't assign something and pick the next building that has the lowest time to complete.

I don't know if you can implement this easily with your engine, or if it even support some kind of timeunits.

This will just result in updating all production facilities once per timeunit, O(n) where n is the number of buildings that can produce something. If you are submitting a unit this will take O(1) assuming that you keep the selected buildings in a sorted order, lowest first - so just a first element lookup. In this case you have to resort the list after manipulating the units like cancelling or adding.

Otherwise amit's answer seem to be possible, too.

This is NPC problem (proof at the end of the answer) so your best hope to find ideal solution is trying all possibilities (this will be 2^n possibilities, where n is the number of tasks).

possible heuristic was suggested in comment (and improved in comments by AShelly): sort the tasks from biggest to smallest, and put them in one queue, every task can now take element from the queue when done.
this is of course not always optimal, but I think will get good results for most cases.

proof that the problem is NPC:
let S={u|u is a unit need to be produced}. (S is the set containing all 'tasks')
claim: if there is a possible prefect split (both queues finish at the same time) it is optimal. let this time be HalfTime
this is true because if there was different optimal, at least one of the queues had to finish at t>HalfTime, and thus it is not optimal.

proof: assume we had an algorithm A to produce the best solution at polynomial time, then we could solve the partition problem at polynomial time by the following algorithm:

1. run A on input
2. if the 2 queues finish exactly at HalfTIme - return True.
3. else: return False

this solution solves the partition problem because of the claim: if the partition exist, it will be returned by A, since it is optimal. all steps 1,2,3 run at polynomial time (1 for the assumption, 2 and 3 are trivial). so the algorithm we suggested solves partition problem at polynomial time. thus, our problem is NPC
Q.E.D.

Here's a simple scheme:

Let U be the list of units you want to build, and F be the set of factories that can build them. For each factory, track total time-til-complete; i.e. How long until the queue is completely empty.

• Sort U by decreasing time-to-build. Maintain sort order when inserting new items
• At the start, or at the end of any time tick after a factory completes a unit runs out of work:
  • Make a ready list of all the factories with space in the queue
    • Sort the ready list by increasing time-til-complete
    • Get the factory that will be done soonest
    • take the first item from U, add it to thact factory
    • Repeat until U is empty or all queues are full.

Googling "minimum makespan" may give you some leads into other solutions. This CMU lecture has a nice overview.

It turns out that if you know the set of work ahead of time, this problem is exactly Multiprocessor_scheduling, which is NP-Complete. Apparently the algorithm I suggested is called "Longest Processing Time", and it will always give a result no longer than 4/3 of the optimal time.

If you don't know the jobs ahead of time, it is a case of online Job-Shop Scheduling

The paper "The Power of Reordering for Online Minimum Makespan Scheduling" says

for many problems, including minimum makespan scheduling, it is reasonable to not only provide a lookahead to a certain number of future jobs, but additionally to allow the algorithm to choose one of these jobs for processing next and, therefore, to reorder the input sequence.

Because you have a FIFO on each of your factories, you essentially do have the ability to buffer the incoming jobs, because you can hold them until a factory is completely idle, instead of trying to keeping all the FIFOs full at all times.

If I understand the paper correctly, the upshot of the scheme is to

1. Keep a fixed size buffer of incoming jobs. In general, the bigger the buffer, the closer to ideal scheduling you get.
2. Assign a weight w to each factory according to a given formula, which depends on buffer size. In the case where buffer size = number factories +1, use weights of (2/3,1/3) for 2 factories; (5/11,4/11,2/11) for 3.
3. Once the buffer is full, whenever a new job arrives, you remove the job with the least time to build and assign it to a factory with a time-to-complete < w*T where T is total time-to-complete of all factories.
4. If there are no more incoming jobs, schedule the remainder of jobs in U using the first algorithm I gave.

The main problem in applying this to your situation is that you don't know when (if ever) that there will be no more incoming jobs. But perhaps just replacing that condition with "if any factory is completely idle", and then restarting will give decent results.