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.

### Create the data

The following code creates the data for the program.

cost = [[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]] sizes = [10, 7, 3, 12, 15, 4, 11, 5] 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 variables and constraints

The following code creates the variables and constraints for the program.

# Variables x = [] for i in range(num_workers): t = [] for j in range(num_tasks): t.append(model.NewIntVar(0, 1, "x[%i,%i]" % (i, j))) x.append(t) x_array = [x[i][j] for i in range(num_workers) for j in range(num_tasks)] # Constraints # Each task is assigned to at least one worker. [model.Add(sum(x[i][j] for i in range(num_workers)) >= 1) for j in range(num_tasks)] # Total size of tasks for each worker is at most total_size_max. [model.Add(sum(sizes[j] * x[i][j] for j in range(num_tasks)) <= total_size_max) for i in range(num_workers)]

### Create the objective

The following code creates the objective function.

model.Minimize(sum([np.dot(x_row, cost_row) for (x_row, cost_row) in zip(x, cost)]))

### Invoke the solver

The following code invokes the solver and displays the results.

solver = cp_model.CpSolver() status = solver.Solve(model) if status == cp_model.OPTIMAL: print('Minimum cost = %i' % solver.ObjectiveValue()) print() for i in range(num_workers): for j in range(num_tasks): if solver.Value(x[i][j]) == 1: print('Worker ', i, ' assigned to task ', j, ' Cost = ', cost[i][j]) print() end = time.time() print("Time = ", round(end - start, 4), "seconds")

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

## MIP solution

Next, we describe a solution to the assignment problem using the MIP solver. We omit the code that creates the data, since it is the same as in the CP-SAT solution.

### Create the variables and constraints

The following code creates the variables and constraints for the program.

# Variables x = {} for i in range(num_workers): for j in range(num_tasks): x[i, j] = solver.IntVar(0, 1, 'x[%i,%i]' % (i, j)) # Constraints # The total size of the tasks each worker takes on is at most total_size_max. for i in range(num_workers): solver.Add(solver.Sum([task_sizes[j] * x[i, j] for j in range(num_tasks)]) <= total_size_max) # Each task is assigned to at least one worker. for j in range(num_tasks): solver.Add(solver.Sum([x[i, j] for i in range(num_workers)]) >= 1)

### Create the objective

The following code creates the objective function.

solver.Minimize(solver.Sum([cost[i][j] * x[i,j] for i in range(num_workers) for j in range(num_tasks)]))

### Invoke the solver and display the results

The following code invokes the solver and displays the results.

sol = solver.Solve() print('Minimum cost = ', solver.Objective().Value()) print() for i in range(num_workers): for j in range(num_tasks): if x[i, j].solution_value() > 0: print('Worker', i,' assigned to task', j, ' Cost = ', cost[i][j]) print() end = time.time() print("Time = ", round(end - start, 4), "seconds")

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

## Complete programs

Here are the complete programs for solving the assignment problem with task sizes using CP-SAT and MIP.

from __future__ import print_function from ortools.sat.python import cp_model import time import numpy as np def main(): model = cp_model.CpModel() start = time.time() cost = [[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]] sizes = [10, 7, 3, 12, 15, 4, 11, 5] total_size_max = 15 num_workers = len(cost) num_tasks = len(cost[1]) # Variables x = [] for i in range(num_workers): t = [] for j in range(num_tasks): t.append(model.NewIntVar(0, 1, "x[%i,%i]" % (i, j))) x.append(t) x_array = [x[i][j] for i in range(num_workers) for j in range(num_tasks)] # Constraints # Each task is assigned to at least one worker. [model.Add(sum(x[i][j] for i in range(num_workers)) >= 1) for j in range(num_tasks)] # Total size of tasks for each worker is at most total_size_max. [model.Add(sum(sizes[j] * x[i][j] for j in range(num_tasks)) <= total_size_max) for i in range(num_workers)] model.Minimize(sum([np.dot(x_row, cost_row) for (x_row, cost_row) in zip(x, cost)])) solver = cp_model.CpSolver() status = solver.Solve(model) if status == cp_model.OPTIMAL: print('Minimum cost = %i' % solver.ObjectiveValue()) print() for i in range(num_workers): for j in range(num_tasks): if solver.Value(x[i][j]) == 1: print('Worker ', i, ' assigned to task ', j, ' Cost = ', cost[i][j]) print() end = time.time() print("Time = ", round(end - start, 4), "seconds") if __name__ == '__main__': main()

from __future__ import print_function import time from ortools.linear_solver import pywraplp def main(): solver = pywraplp.Solver('SolveAssignmentProblem', pywraplp.Solver.CBC_MIXED_INTEGER_PROGRAMMING) start = time.time() cost = [[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]] task_sizes = [10, 7, 3, 12, 15, 4, 11, 5] # Maximum total of task sizes for any worker total_size_max = 15 num_workers = len(cost) num_tasks = len(cost[1]) # Variables x = {} for i in range(num_workers): for j in range(num_tasks): x[i, j] = solver.IntVar(0, 1, 'x[%i,%i]' % (i, j)) # Constraints # The total size of the tasks each worker takes on is at most total_size_max. for i in range(num_workers): solver.Add(solver.Sum([task_sizes[j] * x[i, j] for j in range(num_tasks)]) <= total_size_max) # Each task is assigned to at least one worker. for j in range(num_tasks): solver.Add(solver.Sum([x[i, j] for i in range(num_workers)]) >= 1) solver.Minimize(solver.Sum([cost[i][j] * x[i,j] for i in range(num_workers) for j in range(num_tasks)])) sol = solver.Solve() print('Minimum cost = ', solver.Objective().Value()) print() for i in range(num_workers): for j in range(num_tasks): if x[i, j].solution_value() > 0: print('Worker', i,' assigned to task', j, ' Cost = ', cost[i][j]) print() end = time.time() print("Time = ", round(end - start, 4), "seconds") if __name__ == '__main__': main()