Optimized Task Assignments Using Constraint Programming

There are 10 tasks and 20 reasources. The duration of each task as well as the cost of assignmnet to each resource is known. Find the min cost assignment.

Data

Cost of performing each task by each resource.

[[37, 92, 28, 52, 35, 83, 77, 80, 68, 46],
 [32, 82, 23, 69, 75, 97, 20, 77, 54, 49],
 [95, 33, 60, 23, 22, 23, 89, 21, 68, 47],
 [74, 23, 87, 48, 76, 83, 90, 49, 64, 49],
 [48, 78, 57, 22, 73, 91, 32, 43, 100, 57],
 [35, 62, 84, 74, 84, 44, 58, 56, 95, 83],
 [84, 70, 95, 24, 81, 51, 71, 73, 42, 66],
 [90, 67, 31, 76, 85, 33, 40, 86, 70, 67],
 [82, 23, 80, 25, 59, 98, 95, 94, 70, 41],
 [41, 84, 49, 21, 45, 89, 90, 49, 71, 85],
 [64, 93, 65, 78, 54, 90, 97, 20, 69, 85],
 [36, 86, 91, 46, 74, 27, 81, 66, 92, 90],
 [45, 84, 72, 82, 65, 73, 64, 20, 88, 89],
 [99, 98, 62, 78, 96, 23, 49, 42, 90, 94],
 [43, 31, 90, 52, 24, 29, 30, 22, 77, 21],
 [55, 51, 54, 34, 99, 43, 64, 57, 28, 41],
 [40, 52, 87, 41, 54, 57, 78, 61, 83, 80],
 [34, 23, 59, 69, 63, 73, 44, 53, 33, 52],
 [85, 46, 97, 75, 22, 48, 22, 70, 38, 24],
 [40, 77, 84, 74, 89, 48, 100, 86, 77, 48]]        

Duration of each task (in minutes).

Problem formulation

• U_{t,w} is a binary variable which determines the assignment of task t to worker w.
• C_{t,w} is the cost of assignment of task t to worker w.
• Each task should be assigned to just 1 worker.
• The total duration of tasks assigned to each team member is 100 minutes.

Python Code:

Results

Exctra Requirements:

The business context now requires that certain tasks be handled by the same teams.

Here are some reasons why certain tasks should be handled by the same team:

• Expertise Continuity: Teams already familiar with similar tasks can apply their expertise more effectively, reducing errors and increasing efficiency.
• Task Interdependencies: Some tasks are closely related or dependent on each other, requiring the same team to ensure seamless coordination and understanding.
• Resource Efficiency: Assigning the same team can minimize the time and effort spent on onboarding or transferring knowledge between teams.
• Consistency in Quality: The same team working on related tasks ensures uniformity and consistency in the output or service delivery.
• Improved Communication: Keeping tasks within the same team reduces communication overhead and the potential for misalignment between different groups.

For instance:

Task1,7 Task9,3 Task2,4

Looking at the previous schedule, this is not satisfied.

• Task1,7 (W8,W12)
• Task9,3 (W14,W9)
• Task2,4 (W1,W18)

The question is how to formulate this requirement?

Here is the approach:

A new binary variable is defined as coupled(wi,wj) if worker wi and wj are coupled in any of the coupled tasks then it should become 1.

Python Code:

Results

Let's recheck the same groups: :

Task1,7 Task9,3 Task2,4

Looking at the previous schedule, this is not satisfied.

• Task1,7 (W2,W14)
• Task9,3 (W2,W14)
• Task2,4 (W2,W14)

So you can see the workers (W2,W14) remain together.

Total costs = $283 and 5 workers are used.

Conclusion:

Constraint programming can be used to formulate complicated constraints. Leveraging constraint programming enabled me to efficiently solve the task allocation problem by ensuring optimal alignment between tasks and resources while respecting the business rules. By incorporating preferences for certain tasks to be handled by the same teams, the solution not only met the operational requirements but also enhanced consistency and efficiency. To make the results more intuitive and actionable, I visualized the solution using Python, presenting the allocation clearly and effectively. This combination of advanced optimization techniques and visual analytics demonstrates the power of technology in solving complex resource management challenges.

Some educational resources:

• Udemy (discount code) Pyomo
• Github_repo
• ORTools