Which algorithm can I use for distributing weighted objects equally in n portions?

Question

I want to distribute x(i) objects (x E {1...n}), where each object has weight w(i), into n portions.

The distribution should be done in such a way, that for all the portions the sum of weights is as equal as possible.

Cheers! Pratik

Answer 1

Calculate the total sum of the weights, divide by n, the number of portions, to get the required portion weight. Then use a bin packing algorithm to try and fill n bins of this maximum size.

Note that all weights need to be less than the portion weight for this to work properly. Otherwise you won't be able to place items with large weight anywhere.

Answer 2

I think you are describing the Multiprocessor scheduling problem.

Here is a Julia implementation:

"""
Solves the Multiprocessor Scheduling problem using the Longest Processing Time algorithm

    PROBLEM: (NP-hard)
        Given:
            - set of jobs, each with a length
            - a number of processors
        Find:
            - divide the jobs among the processors such that none overlap
              which minimizes the total processing time

    ALGORITHM:
        - sort the jobs by processing time
        - assign them to the machine with the earliest end time so far
        Achieves an upper bound of 4/3 - 1/(3m) of optimal

    RETURNS:
        assignments, ith index → machine for the ith job
"""
function multiprocessor_scheduling_longest_processing_time{R<:Real}(
    jobs::AbstractVector{R},
    m::Integer, # number of processors
    )

    durations = zeros(R, m)
    assignments = Array(Int, length(jobs))

    for i in sortperm(jobs, rev=true) # p[1] is the index of the longest job in `jobs`
        best_index = indmin(durations)
        durations[best_index] += jobs[i]
        assignments[i] = best_index
    end

    assignments
end

You could probably do a little better if you used a priority queue.