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.

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.

CP-SAT program
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)
# 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()
MIP progam
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)
# 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()