0

I have code now that takes a list of jobs and divides it up to be worked on different job runners. The code simply takes a list of all of the jobs and divides it equally into some number of bins. The solution is based on a SO post:

How do I split a list into equally-sized chunks?

This is not a great approach though. Some jobs may take a few seconds while others may take a few hours. Given this, the work is not divided evenly across all runners, even though the total number of jobs is.

I would like to split the jobs across the runners so that the amount of work each runner gets is roughly equal. For the solution, I can format the data however it is convenient, but I imagine a list of tuples similar to:

[(job, estimate), (job, estimate), ...]

I can imagine an algorithm that would get me the behavior by looking at the average of all the estimates and the total number of jobs, but given the number of libraries available in Python, I wanted to know if there was a solution already out there before I reinvent this specific wheel.

DiB
  • 554
  • 5
  • 19
  • How do you know the amount of "work" before starting the job? You should then use dynamically sized chunks, i.e. have a function which chunks the data according to the expected "work", before passing the chunk to the worker. – Jan Christoph Terasa Aug 12 '22 at 12:26
  • 2
    Note that what you are asking for is usually referred to as [Multiway number partitioning](https://en.wikipedia.org/wiki/Multiway_number_partitioning) and is an NP-hard problem in the general case, so there is no known efficient algorithm to find the optimal solution in the general case if the input array is large. However there are many approximation algorithm known, and you can bruteforce it if the input array is small. – Stef Aug 12 '22 at 13:39
  • See also [or.stackexchange.com : Efficient solver for multiway number partitioning](https://or.stackexchange.com/questions/6113/efficient-solver-for-multiway-number-partitioning) and [pypi.org : numberpartitioning](https://pypi.org/project/numberpartitioning/) – Stef Aug 12 '22 at 13:53
  • Fantastic! Thank you. Knowing what the algorithm is called is a huge help! The problem being NP-hard is also great to know, though disappointing! – DiB Aug 12 '22 at 14:14

0 Answers0