Load Balancing Algorithms - A Special Example

Question

Let's pretend that I have two buildings in which I can build different units. A building can only build one device at a time, but has a fifth turn with a maximum of 5 units, which will be built in series. Each unit has a build time. I need to know what is the quickest solution to get my units as quickly as possible, given the units that are already in the queue for the construction of my buildings. Well-known algorithms like RoundRobin don't work here, I think.

Are there any algorithms that can solve this problem?

Answer 1

It reminds me of a little starry: D

I would simply add an integer to the building's queue, which represents the time when it is busy. Of course, you need to update this variable once in a while. (Temporary units are here "here", in seconds)

So, let's say we have a building, and we send 3 units, each of which takes 5 seconds. Which summarizes up to 15 s. We are in time = 0. Then we have another building in which we send 2 units, which require 6 timeouts to complete each of them.

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 block that takes 2 seconds, we can just skip the selected buildings and choose the one with the lowest time to complete. In this case, this will be creation 2. This will result in 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 

Etc.

Of course, you must take care of the upper bounds at your production facilities. For example, if a building has 5 elements, do not assign something and choose the next building, which has the lowest time to complete.

I don’t know if you can easily implement this using your engine or even support some kind of temporary units.

This simply leads to updating all production facilities once per time, O (n), where n is the number of buildings that can create something. If you send the device, it will take O (1), assuming you save the selected buildings in sorted order, the lowest at first - so just search for the first item. In this case, you need to resort to the list after manipulating units, for example, cancel or add.

Otherwise, the answer also seems possible.

Answer 2

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

a possible heuristic was suggested in a comment (and improved in AShelly's comments): sort tasks from the largest to the smallest and put them in one queue, each task can now take an element from the queue when it is done. This, of course, is not always optimal, but I think that for most cases, good results.

proof that the problem is NPC: Let S = {u | u is the unit to be created}. (S is a set containing all the "tasks")
claim : if there is a possible split in the prefect (both lines end at the same time), this is optimal. let this time be HalfTime This is true, because if there was another optimal one, at least one of the queues should end with t> HalfTime, and therefore it would not be optimal.

proof : suppose we had algorithm A to get the best solution in polynomial time, then we could solve the partition problem in polynomial time using 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 due to a claim: if the partition exists, it will be returned to A because it is optimal. all stages 1,2,3 are performed with polynomial time (1 for the assumption, 2 and 3 are trivial). therefore, our proposed algorithm solves the partition problem in polynomial time. so our problem is NPC
QED

Answer 3

Here's a simple diagram:

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

• Sort U by reducing assembly time. Maintain sort order when inserting new items
• At the beginning or at the end of any tick after completion of the factory , the block ends its work:
  • Make a list of all plants with a space in the queue
    • Sort a finished list by increasing the time-til-complete
    • Get a factory to be completed shortly
    • take the first item from U, add it to thact factory
    • Repeat until U is empty or all queues are full.

Googling "minimum size" may give you several results in other solutions. This lecture in CMU has a good overview.

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

If you do not know the tasks ahead of time, this is the case online.

Reordering Power for Online Planning for Minimal Planning says

for many problems, including minimal scheduling, it is reasonable not only to provide a certain number of future jobs, but also to allow the algorithm to select one of these jobs for further processing and, therefore, change the input order.

Since you have FIFOs at each of your factories, you have the ability to buffer incoming jobs, because you can hold them until the factory is completely inactive, instead of trying to save all the FIFOs all the time.

If I understand the document correctly, the result of this diagram is

• Keep a buffer of fixed size inbound jobs. In general, the larger the buffer, the closer to ideal planning.
• Assign weight w to each factory according to the given formula, which depends on the size of the buffer. In the case when the buffer size = number of factories +1, use the weight (2 / 3,1 / 3) for 2 factories; (5 / 11.4 / 11.2 / 11) for 3.
• As soon as the buffer is full, whenever a new task arrives, you delete the task with the least time to create it and assign it to the factory with time, w * T, where T is the full time to time for all plants.
• If there are no more tasks, plan the remaining tasks in U using the first algorithm I gave.

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