6

I need to find an optimal distribution of some matching tasks on multiple jobs; each job is limited by a maximum workload and the grouped tasks should maximize the workload within the same job.

However, tasks with similar values within the same source should have a higher priority to be included in the same job.

For example: Input tasks with the expected workload

Task  Source1  Source2  Workload
  1     A        A        40
  2     A        B        15
  3     B        A        48
  4     B        B        18
  5     C        A        32
  6     C        B        24
  7     A        C        8

In case the maximum workload is 50, the tasks should be distributed as follows. 

Job1
Task  Source1  Source2  Workload
  1     A        A        40
  7     A        C        8

Job2
Task  Source1  Source2  Workload
  2     A        B        15
  6     C        B        24

Job3
Task  Source1  Source2  Workload
  3     B        A        48

Job4
Task  Source1  Source2  Workload
  4     B        B        18
  5     C        A        32

Any clues?

vanilla
  • 71
  • 2
  • "tasks with similar values" which values? The workload or...? – candied_orange Jul 23 '16 at 20:55
  • No, in my example, the A, B, C values which represents e.g. a type of the values to be matched together – vanilla Jul 23 '16 at 20:59
  • Possible duplicate of [Work load balance/Task distribution algorithm](https://softwareengineering.stackexchange.com/questions/127173/work-load-balance-task-distribution-algorithm) – gnat Feb 02 '18 at 13:16

1 Answers1

1

In your example solution, jobs 1 and 2 manage to group similar values within the same source but jobs 3 and 4 don't. All jobs keep their total workload under 50.

This example solution appears to be the result of a greedy algorithm that grabs the first possible match.

In general, greedy algorithms have five components:

  1. A candidate set, from which a solution is created
    • Tasks 1 to 7
  2. A selection function, which chooses the best candidate to be added to the solution
    • Best here seems to only mean under the workload limits we create as many source matches as possible with this next choice
  3. A feasibility function, that is used to determine if a candidate can be used to contribute to a solution
    • This is the workload limit
  4. An objective function, which assigns a value to a solution, or a partial solution
    • A count of the number of source matches in the solution (2 in your example)
  5. A solution function, which will indicate when we have discovered a complete solution
    • When all tasks have been assigned to jobs we're done

The output of this algorithm is highly dependant on the order in which the tasks are presented. Meaning better solutions may be found by permuting the task order and rerunning greedy. This is O(n!) hard but should be optimal. The complete solution with the most source matches wins.

This is hardly efficient but is an optimal solution. More efficient solutions may exist. I suspect this to be a combinatorial optimization problem. See if any of those solutions are applicable and more efficient.

candied_orange
  • 102,279
  • 24
  • 197
  • 315
  • 3
    If I understand the OP correctly, this is just the [multiprocessor scheduling problem](https://en.wikipedia.org/wiki/Multiprocessor_scheduling), which is known to be NP-hard. – 5gon12eder Sep 22 '16 at 16:25