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
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;
Overwriting 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#
# Set the solver type for use in solving the problems
solver = 'gurobi'
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=solver, verbose=True) # Solve the optimization problem using CBC solver
Gurobi 12.0.0: tech:outlev = 0
lim:time = 20
Gurobi 12.0.0: optimal solution; objective 8
66 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