Assignment with Task Sizes

This section describes an assignment problem in which each task has a size, which represents how much time or effort the task requires. The total size of the tasks performed by each worker has a fixed bound.

We'll present Python programs that solve this problem using the CP-SAT solver and the MIP solver.

CP-SAT solution

First, let's take a look at the CP-SAT solution to the problem.

Import the libraries

The following code imports the required library.

from ortools.sat.python import cp_model

Define the data

The following code creates the data for the program.

costs = [
    [90, 76, 75, 70, 50, 74, 12, 68],
    [35, 85, 55, 65, 48, 101, 70, 83],
    [125, 95, 90, 105, 59, 120, 36, 73],
    [45, 110, 95, 115, 104, 83, 37, 71],
    [60, 105, 80, 75, 59, 62, 93, 88],
    [45, 65, 110, 95, 47, 31, 81, 34],
    [38, 51, 107, 41, 69, 99, 115, 48],
    [47, 85, 57, 71, 92, 77, 109, 36],
    [39, 63, 97, 49, 118, 56, 92, 61],
    [47, 101, 71, 60, 88, 109, 52, 90],
]
num_workers = len(costs)
num_tasks = len(costs[0])

task_sizes = [10, 7, 3, 12, 15, 4, 11, 5]
# Maximum total of task sizes for any worker
total_size_max = 15

As in previous examples, the cost matrix gives the cost for worker i to perform task j. The sizes vector gives the size of each task. total_size_max is the upper bound on the total size of the tasks performed by any single worker.

Create the model

The following code creates the model.

model = cp_model.CpModel()

Create the variables

The following code creates an array of variables for the problem.

x = {}
for worker in range(num_workers):
    for task in range(num_tasks):
        x[worker, task] = model.NewBoolVar(f'x[{worker},{task}]')

Add the constraints

The following code creates the constraints for the program.

# Each worker is assigned to at most one task.
for worker in range(num_workers):
    model.Add(
        sum(task_sizes[task] * x[worker, task]
            for task in range(num_tasks)) <= total_size_max)

# Each task is assigned to exactly one worker.
for task in range(num_tasks):
    model.Add(sum(x[worker, task] for worker in range(num_workers)) == 1)

Create the objective

The following code creates the objective function.

objective_terms = []
for worker in range(num_workers):
    for task in range(num_tasks):
        objective_terms.append(costs[worker][task] * x[worker, task])
model.Minimize(sum(objective_terms))

Invoke the solver

The following code invokes the solver.

solver = cp_model.CpSolver()
status = solver.Solve(model)

Display the results

Now, we can print the solution.

if status == cp_model.OPTIMAL or status == cp_model.FEASIBLE:
    print(f'Total cost = {solver.ObjectiveValue()}\n')
    for worker in range(num_workers):
        for task in range(num_tasks):
            if solver.BooleanValue(x[worker, task]):
                print(f'Worker {worker} assigned to task {task}.' +
                      f' Cost = {costs[worker][task]}')
else:
    print('No solution found.')

Here's the output of the program.

Minimum cost: 326
Worker  0  assigned to task  6   Cost =  12
Worker  1  assigned to task  0   Cost =  35
Worker  1  assigned to task  2   Cost =  55
Worker  2  assigned to task  4   Cost =  59
Worker  5  assigned to task  5   Cost =  31
Worker  5  assigned to task  7   Cost =  34
Worker  6  assigned to task  1   Cost =  51
Worker  8  assigned to task  3   Cost =  49

Time =  2.2198 seconds

The entire program

Here is the entire program.

"""Solve a simple assignment problem."""
from ortools.sat.python import cp_model


def main():
    # Data
    costs = [
        [90, 76, 75, 70, 50, 74, 12, 68],
        [35, 85, 55, 65, 48, 101, 70, 83],
        [125, 95, 90, 105, 59, 120, 36, 73],
        [45, 110, 95, 115, 104, 83, 37, 71],
        [60, 105, 80, 75, 59, 62, 93, 88],
        [45, 65, 110, 95, 47, 31, 81, 34],
        [38, 51, 107, 41, 69, 99, 115, 48],
        [47, 85, 57, 71, 92, 77, 109, 36],
        [39, 63, 97, 49, 118, 56, 92, 61],
        [47, 101, 71, 60, 88, 109, 52, 90],
    ]
    num_workers = len(costs)
    num_tasks = len(costs[0])

    task_sizes = [10, 7, 3, 12, 15, 4, 11, 5]
    # Maximum total of task sizes for any worker
    total_size_max = 15

    # Model
    model = cp_model.CpModel()

    # Variables
    x = {}
    for worker in range(num_workers):
        for task in range(num_tasks):
            x[worker, task] = model.NewBoolVar(f'x[{worker},{task}]')

    # Constraints
    # Each worker is assigned to at most one task.
    for worker in range(num_workers):
        model.Add(
            sum(task_sizes[task] * x[worker, task]
                for task in range(num_tasks)) <= total_size_max)

    # Each task is assigned to exactly one worker.
    for task in range(num_tasks):
        model.Add(sum(x[worker, task] for worker in range(num_workers)) == 1)

    # Objective
    objective_terms = []
    for worker in range(num_workers):
        for task in range(num_tasks):
            objective_terms.append(costs[worker][task] * x[worker, task])
    model.Minimize(sum(objective_terms))

    # Solve
    solver = cp_model.CpSolver()
    status = solver.Solve(model)

    # Print solution.
    if status == cp_model.OPTIMAL or status == cp_model.FEASIBLE:
        print(f'Total cost = {solver.ObjectiveValue()}\n')
        for worker in range(num_workers):
            for task in range(num_tasks):
                if solver.BooleanValue(x[worker, task]):
                    print(f'Worker {worker} assigned to task {task}.' +
                          f' Cost = {costs[worker][task]}')
    else:
        print('No solution found.')


if __name__ == '__main__':
    main()

MIP solution

Next, we describe a solution to the assignment problem using the MIP solver.

Import the libraries

The following code imports the required library.

from ortools.linear_solver import pywraplp

Define the data

The following code creates the data for the program.

costs = [
    [90, 76, 75, 70, 50, 74, 12, 68],
    [35, 85, 55, 65, 48, 101, 70, 83],
    [125, 95, 90, 105, 59, 120, 36, 73],
    [45, 110, 95, 115, 104, 83, 37, 71],
    [60, 105, 80, 75, 59, 62, 93, 88],
    [45, 65, 110, 95, 47, 31, 81, 34],
    [38, 51, 107, 41, 69, 99, 115, 48],
    [47, 85, 57, 71, 92, 77, 109, 36],
    [39, 63, 97, 49, 118, 56, 92, 61],
    [47, 101, 71, 60, 88, 109, 52, 90],
]
num_workers = len(costs)
num_tasks = len(costs[0])

task_sizes = [10, 7, 3, 12, 15, 4, 11, 5]
# Maximum total of task sizes for any worker
total_size_max = 15

Declare the solver

The following code creates the solver.

# Create the mip solver with the SCIP backend.
solver = pywraplp.Solver.CreateSolver('SCIP')

Create the variables

The following code creates an array of variables for the problem.

# x[i, j] is an array of 0-1 variables, which will be 1
# if worker i is assigned to task j.
x = {}
for worker in range(num_workers):
    for task in range(num_tasks):
        x[worker, task] = solver.IntVar(0, 1, f'x[{worker},{task}]')

Add the constraints

The following code creates the constraints for the program.

# The total size of the tasks each worker takes on is at most total_size_max.
for worker in range(num_workers):
    solver.Add(
        solver.Sum([
            task_sizes[task] * x[worker, task] for task in range(num_tasks)
        ]) <= total_size_max)

# Each task is assigned to exactly one worker.
for task in range(num_tasks):
    solver.Add(
        solver.Sum([x[worker, task] for worker in range(num_workers)]) == 1)

Create the objective

The following code creates the objective function.

objective_terms = []
for worker in range(num_workers):
    for task in range(num_tasks):
        objective_terms.append(costs[worker][task] * x[worker, task])
solver.Minimize(solver.Sum(objective_terms))

Invoke the solver

The following code invokes the solver and displays the results.

status = solver.Solve()

Display the results

Now, we can print the solution.

if status == pywraplp.Solver.OPTIMAL or status == pywraplp.Solver.FEASIBLE:
    print(f'Total cost = {solver.Objective().Value()}\n')
    for worker in range(num_workers):
        for task in range(num_tasks):
            if x[worker, task].solution_value() > 0.5:
                print(f'Worker {worker} assigned to task {task}.' +
                      f' Cost = {costs[worker][task]}')
else:
    print('No solution found.')

Here is the output of the program.

Minimum cost =  326.0

Worker 0  assigned to task 6   Cost =  12
Worker 1  assigned to task 0   Cost =  35
Worker 1  assigned to task 2   Cost =  55
Worker 4  assigned to task 4   Cost =  59
Worker 5  assigned to task 5   Cost =  31
Worker 5  assigned to task 7   Cost =  34
Worker 6  assigned to task 1   Cost =  51
Worker 8  assigned to task 3   Cost =  49

Time =  0.0167 seconds

The entire program

Here is the entire program.

"""MIP example that solves an assignment problem."""
from ortools.linear_solver import pywraplp


def main():
    # Data
    costs = [
        [90, 76, 75, 70, 50, 74, 12, 68],
        [35, 85, 55, 65, 48, 101, 70, 83],
        [125, 95, 90, 105, 59, 120, 36, 73],
        [45, 110, 95, 115, 104, 83, 37, 71],
        [60, 105, 80, 75, 59, 62, 93, 88],
        [45, 65, 110, 95, 47, 31, 81, 34],
        [38, 51, 107, 41, 69, 99, 115, 48],
        [47, 85, 57, 71, 92, 77, 109, 36],
        [39, 63, 97, 49, 118, 56, 92, 61],
        [47, 101, 71, 60, 88, 109, 52, 90],
    ]
    num_workers = len(costs)
    num_tasks = len(costs[0])

    task_sizes = [10, 7, 3, 12, 15, 4, 11, 5]
    # Maximum total of task sizes for any worker
    total_size_max = 15

    # Solver
    # Create the mip solver with the SCIP backend.
    solver = pywraplp.Solver.CreateSolver('SCIP')


    # Variables
    # x[i, j] is an array of 0-1 variables, which will be 1
    # if worker i is assigned to task j.
    x = {}
    for worker in range(num_workers):
        for task in range(num_tasks):
            x[worker, task] = solver.IntVar(0, 1, f'x[{worker},{task}]')

    # Constraints
    # The total size of the tasks each worker takes on is at most total_size_max.
    for worker in range(num_workers):
        solver.Add(
            solver.Sum([
                task_sizes[task] * x[worker, task] for task in range(num_tasks)
            ]) <= total_size_max)

    # Each task is assigned to exactly one worker.
    for task in range(num_tasks):
        solver.Add(
            solver.Sum([x[worker, task] for worker in range(num_workers)]) == 1)

    # Objective
    objective_terms = []
    for worker in range(num_workers):
        for task in range(num_tasks):
            objective_terms.append(costs[worker][task] * x[worker, task])
    solver.Minimize(solver.Sum(objective_terms))

    # Solve
    status = solver.Solve()

    # Print solution.
    if status == pywraplp.Solver.OPTIMAL or status == pywraplp.Solver.FEASIBLE:
        print(f'Total cost = {solver.Objective().Value()}\n')
        for worker in range(num_workers):
            for task in range(num_tasks):
                if x[worker, task].solution_value() > 0.5:
                    print(f'Worker {worker} assigned to task {task}.' +
                          f' Cost = {costs[worker][task]}')
    else:
        print('No solution found.')


if __name__ == '__main__':
    main()