Balanced Task Assignment with Inverse Cost Scaling#

Inverse_cost.ipynb Open In Colab Kaggle Gradient Open In SageMaker Studio Lab Hits

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.

Partner with the AMPL team to transform complex problems into optimized solutions. AMPL consulting services combine deep technical knowledge with industry-leading insights, helping you unlock the full potential of optimization within your organization.

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#

  1. 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\)

  2. 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\)

  3. 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