Split tests into even time slaves

Question

Split tests into even time slaves.

I have a full list of how long each test takes.

They are python behave test features.

Slaves are created via Jenkins.

---

I have tests split out on to x amount of slaves. These slaves run the tests and report back.

Problem: Some of the slaves are getting bigger longer running tests than others. eg. one will take 40 mins and another will take 5 mins.

I want to average this out.

I currently have a list of the file and time it takes.

[
    ['file_A', 501],
    ['file_B', 350],
    ['file_C', 220],
    ['file_D', 100]
]

extra... there are n number of files.

At the moment these are split in to lists by number of files, I would like to split them by the total time taken. eg... 3 slaves running these 4 tests would look like...

[
[
     ['file_A', 501],
],
[
     ['file_B', 350],
],
[
     ['file_C', 220],
     ['file_D', 100]
]
]

Something like that...

Please help

Thanks!

Answer 1

You could do something like:

def split_tasks(lst, n):
    # sorts the list from largest to smallest
    sortedlst = sorted(lst, key=lambda x: x[1], reverse=True)
    # dict storing the total time for each set of tasks
    totals = dict((x, 0) for x in range(n))
    outlst = [[] for x in range(n)]
    for v in sortedlst:
        # since each v[1] is getting smaller, the place it belongs should
        # be the outlst with the minimum total time
        m = min(totals, key=totals.get)
        totals[m] += v[1]
        outlst[m].append(v)
    return outlst

Which produces the expected output:

[[['file_A', 501]], [['file_B', 350]], [['file_C', 220], ['file_D', 100]]]

Answer 2

Sort your tests into descending order of the time taken to run, send one to each slave from the top of the list and then give them another as they finish - using this strategy if a test hangs or takes longer than usual all the other tests will still get finished in the minimum time.

If you can not distribute the tests on completion then allocate a list for each server and "deal" the tests out in same manner.

Answer 3

This can be solved using a Knapsack algorithm, using the sum of all values divided by the number of slaves.

Answer 4

It seemed to me that the problem was a Simple Assembly Line Balancing Problem. (see page 2), but I guess it is instead Multi-way number partitioning . Here is a recent related paper by Michael D. Moffitt.

I don't know if there is a python module which solves this problem, but maybe someone at StackOverflow knows?

You could implement an algorithm which approximates the solution:
(Quoting accepted answer at 6855394 )

Greedy:
1. Order the available items descending.
2. Create N empty groups
3. Start adding the items one at a time into the group that has the smallest sum in it.