4

Let's say I have a set of tasks that need to be done. I have two identical workers that will process them, and (for simplicity's sake) let's assume that I have perfect information on the complexity of the tasks: there are not tasks I don't know about, and I know exactly how long each one will take to complete. (But different tasks will take different amounts of time.) Each worker can only work on one task at a time, and once begun, must continue to work on it until the task is complete. There are no dependencies between tasks, such that one must be finished before another can be worked on.

Given these constraints, is there any known-best algorithm to divide the work between the two workers so that the total time to complete all tasks is minimized? The obvious, naive solution is that each time a worker is free, always assign it the longest (or shortest) remaining task, but is there any method that is more efficient?

Mason Wheeler
  • 82,511
  • 50
  • 270
  • 477

1 Answers1

5

This is the partition problem, which is NP-Complete, but if the tasks times are given in relatively low integers - there is a pseudo-polynomial time Dynamic programming solution to solve it.

In your case, you are basically given a set of numbers - and you want to assign them to two subsets, such that the sum of subsets is equal (or closest as possible to being equal, which is the optimization variant of partition problem).

The recursive formula for the DP solution should be something similar to this:

DP[0, 0] = true
DP[0, x] = false | x != 0
DP[i, x] = DP[i-1, x-value[i]]   OR      DP[i-1, x]
              ^                              ^
      assigned i to S1                   Assigned i to S2

Calculate all values needed for DP[n+1, SUM] (where SUM is the total sum of tasks and n is the number of tasks), and you are looking for a value DP[n+1, SUM/2] to see if that can be done perfectly.

Getting the actual tasks for each subset is done by retracing your steps, similar to explained here.

amit
  • 175,853
  • 27
  • 231
  • 333