Balanced Task Assignment with Inverse Cost Scaling#
This model addresses a task assignment problem where workers are assigned to tasks based on a cost matrix. The cost of assigning a task to a worker depends inversely on the number of tasks already assigned to that worker, encouraging balanced task allocation. The objective is to minimize the total cost while ensuring:
Each task is assigned to exactly one worker.
Each worker is assigned no more than a specified maximum number of tasks.
Tags: amplpy, nonlinear, worker-task-assignment, cost-minimization, inverse-cost-scaling, task-scheduling, gurobi, global-optimization, assignment, scheduling
Notebook author: Mikhail Riabtsev <mail@solverytic.com>
1. Download Necessary Extensions and Libraries#
# Install dependencies
%pip install -q amplpy pandas numpy
import pandas as pd # Loading panda to work with pandas.DataFrame objects (https://pandas.pydata.org/)
import numpy as np # Loading numpy to perform multidimensional calculations numpy.matrix (https://numpy.org/)
# Google Colab & Kaggle integration
from amplpy import AMPL, ampl_notebook
ampl = ampl_notebook(
modules=["cbc", "highs", "gurobi"], # modules to install
license_uuid="default", # license to use
) # instantiate AMPL object and register magics
2. Mathematical Formulation#
Sets#
\((W)\): Set of workers \(W = {w_1, w_2, \ldots, w_n}\)
\((T)\): Set of tasks \(T = {t_1, t_2, \ldots, t_m}\)
Parameters#
\(cost[w, t]\): Cost of assigning worker \(w\) to task \(t\), where \(w \in W \) and \(t \in T \).
\(max\_tasks\): Maximum number of tasks that can be assigned to a single worker.
Decision Variables#
\(x[w, t] \in \{0, 1\} \): Binary variable, 1 if worker \(w\) is assigned to task \(t\), 0 otherwise.
Objective Function#
Minimize the total cost of assigning tasks to workers:
\(\text{Minimize Z }= \sum_{w \in W} \sum_{t \in T} \frac{\text{cost}[w, t]}{1 + \sum_{t' \in T} x[w, t']} \cdot x[w, t]\)
Constraints#
Task Assignment Constraint:
Each task must be assigned to exactly one worker:\( \sum_{w \in W} x[w, t] = 1, \quad \forall t \in T\)
Worker Task Limit Constraint:
Each worker can be assigned at most \(\text{max\_tasks} \) tasks:\(\sum_{t \in T} x[w, t] \leq \text{max\_tasks}, \quad \forall w \in W\)
Binary Decision Variables:
Ensure the variables are binary:\(x[w, t] \in \{0, 1\}, \quad \forall w \in W, \, t \in T\)
3. AMPL Model Formulation#
%%writefile Inverse_cost_model.mod
reset;
# Model Name: Worker-Task Assignment
### Optimize task assignments to workers, minimizing costs with an inverse relationship scaling.
# Version: 1.0
# Last Updated: Jan 2025
### SETS
# Define the set of workers and tasks
set WORKERS; # All workers
set TASKS; # All tasks
### PARAMETERS
# Define cost and constraints for assignments
param cost {WORKERS, TASKS} >= 0; # Cost of assigning a worker to a task
param max_tasks integer >= 1; # Maximum number of tasks per worker
### VARIABLES
# Decision variable: assignment of tasks to workers
var IsAssigned {WORKERS, TASKS} binary; # 1 if a worker is assigned to a task, 0 otherwise
### OBJECTIVE
# Minimize the total cost with an inverse relationship scaling
# The cost of assigning a worker to a task decreases with the number of tasks already assigned to that worker.
minimize TotalCost:
sum {w in WORKERS, t in TASKS}
(cost[w, t] / (1 + sum{t2 in TASKS} IsAssigned[w,t2])) * IsAssigned[w,t];
### CONSTRAINTS
subject to TaskAssignment{t in TASKS}: # Each task must be assigned to exactly one worker
sum{w in WORKERS} IsAssigned[w,t] = 1;
subject to WorkerTaskLimit{w in WORKERS}: # Each worker is assigned at most max_tasks tasks
sum{t in TASKS} IsAssigned[w,t] <= max_tasks;
Writing Inverse_cost_model.mod
4. Load data#
ampl.read("Inverse_cost_model.mod") # Load the AMPL model from the file
ampl.set["WORKERS"] = ["Alice", "Bob", "Carol", "Dave"] # Set of workers
ampl.set["TASKS"] = [
"Task1",
"Task2",
"Task3",
"Task4",
"Task5",
"Task6",
] # Set of tasks
ampl.param["max_tasks"] = 3 # Maximum number of tasks that can be assigned to a worker
ampl.param["cost"] = { # Cost matrix (cost of assigning a worker to a task)
("Alice", "Task1"): 5,
("Alice", "Task2"): 8,
("Alice", "Task3"): 6,
("Alice", "Task4"): 7,
("Alice", "Task5"): 5,
("Alice", "Task6"): 8,
("Bob", "Task1"): 7,
("Bob", "Task2"): 6,
("Bob", "Task3"): 8,
("Bob", "Task4"): 5,
("Bob", "Task5"): 7,
("Bob", "Task6"): 6,
("Carol", "Task1"): 6,
("Carol", "Task2"): 7,
("Carol", "Task3"): 5,
("Carol", "Task4"): 8,
("Carol", "Task5"): 6,
("Carol", "Task6"): 7,
("Dave", "Task1"): 8,
("Dave", "Task2"): 5,
("Dave", "Task3"): 7,
("Dave", "Task4"): 6,
("Dave", "Task5"): 8,
("Dave", "Task6"): 5,
}
5. Solve problem#
ampl.option["show_stats"] = 0 # Show problem size statistics (default: 0)
ampl.option["display_1col"] = 0 # Disable single-column data display
# ampl.option['omit_zero_rows'] = 1 # Hide rows with zero values
# ampl.option['omit_zero_cols'] = 1 # Hide columns with zero values
ampl.option["mp_options"] = (
"outlev=0 lim:time=20" # Configure CBC options (output level and time limit)
)
ampl.solve(solver="gurobi", verbose=True) # Solve the optimization problem\
assert ampl.solve_result == "solved", ampl.solve_result
Gurobi 12.0.1: tech:outlev = 0
lim:time = 20
Gurobi 12.0.1: optimal solution; objective 8
52 simplex iterations
1 branching node
6. Retrieve solution in Python#
solution = ampl.get_solution(flat=False)
for name_task, val in solution["IsAssigned"].items():
name, task = name_task
print(f"{name} assigned to {task}")
Alice assigned to Task1
Alice assigned to Task3
Alice assigned to Task5
Dave assigned to Task2
Dave assigned to Task4
Dave assigned to Task6