Algorithmic approach to maximising a variable subject to some conditions (in a specific example)

user_15809563 0
Viewed 19

I have a task allocation problem that I am finding difficult.

  • Suppose we have a group of individuals who each have different skills
  • Each group member can allocate 10 hours to each of Building and Crafting
  • A person's skill effects how well they can Build or Craft, i.e. a person with a Build skill of 0.5 can create 0.5 Build output with 1 hours' work
  • The group must satisfy the condition that Building output >= 10, and Crafting output >= 5

How can the group maximise “free time” (i.e. number of total hours spent unallocated) while still satisfying the minimum output conditions)?


Example:
Person     Building Skill    Crafting Skill
Alice      0.8               0.4
Bob        0.3               0.7
Cob        0.6               0.6

If each person had identical skills, no matter how the hours were allocated (as long as the conditions were satisfied) free time would have to be the same. But when each person has different skills, an “efficient” allocation of hours could vastly increase the amount of free time.

Would anyone know of any solutions that exist to this problem, and ones that work quickly even with a large amount of people and many more types of skills?

OR alternatively some a heuristical approach that can maximise free time to a decent enough extent (even if it's not perfect)

pseudocode optimization algorithm
1 Answers

You can formulate problems like this as a linear program and then call out to a solver library to find the optimal solution.

Here's some sample Python.

from ortools.linear_solver import pywraplp

solver = pywraplp.Solver.CreateSolver("GLOP")
alice_build = solver.NumVar(0, 10, "alice_build")
alice_craft = solver.NumVar(0, 10, "alice_craft")
bob_build = solver.NumVar(0, 10, "bob_build")
bob_craft = solver.NumVar(0, 10, "bob_craft")
carol_build = solver.NumVar(0, 10, "carol_build")
carol_craft = solver.NumVar(0, 10, "carol_craft")

solver.Minimize(
    alice_build + alice_craft + bob_build + bob_craft + carol_build + carol_craft
)
solver.Add(0.8 * alice_build + 0.3 * bob_build + 0.6 * carol_build >= 10)
solver.Add(0.4 * alice_craft + 0.7 * bob_craft + 0.6 * carol_craft >= 5)

# I'm not sure exactly what you meant by "Each group member can allocate 10
# hours to each of Building and Crafting". Delete these constraints if they can
# build for 10 hours and then craft for 10 hours.
solver.Add(alice_build + alice_craft <= 10)
solver.Add(bob_build + bob_craft <= 10)
solver.Add(carol_build + carol_craft <= 10)

solver.Solve()
print("alice_build", "=", alice_build.SolutionValue())
print("alice_craft", "=", alice_craft.SolutionValue())
print("bob_build", "=", bob_build.SolutionValue())
print("bob_craft", "=", bob_craft.SolutionValue())
print("carol_build", "=", carol_build.SolutionValue())
print("carol_craft", "=", carol_craft.SolutionValue())
user_21446690
Related