ASSIGNMENT PROBLEM (OPERATIONS RESEARCH) USING PYTHON

BACKGROUND

The Assignment Problem is a special type of Linear Programming Problem based on the following assumptions:

1. It aims at minimizing the cost or time associated with completing a certain number of tasks by certain resources (man or machinery).
2. Only one job is assigned to one resource.

Mathematically, this problem is solved using the Hungarian Method as explained below:

However, solving this task for increasing number of jobs and/or resources calls for computational techniques.

This article aims at solving an Assignment Problem using the Gurobi package of Python.

PROBLEM STATEMENT

Machineco has four machines and four jobs to be completed. Each machine must be assigned to complete one job. The time required to set up each machine for completing each job is shown in the Table. Machineco wants to minimize the total setup time needed to complete the four jobs.

IMPORTING THE GUROBI PACKAGE

from gurobipy import *

SETS

The 4 Machines and 4 Jobs are the identified sets from the proposed problem.

# Defining Sets
machines = ["M0","M1","M2", "M3"]
jobs= ["J0", "J1", "J2", "J3"]

I = range(len(machines))
J = range(len(jobs))

DATA

The problem matrix gives us values of the setup times for each machine required to do the job.

#Data
Set_up_time = [
    [14,5,8,7],
    [2,12,6,5],
    [7,8,3,9],
    [2,4,6,10]
]

DEFINING THE MODEL

#Model
m= Model("Assignment Model")

DEFINING THE VARIABLE

xij defines which machine should be assigned to each job such that:

#Defining the Variable
X = {}
for i in I:
    for j in J:
       X[i,j] = m.addVar(vtype= GRB.BINARY)

OBJECTIVE FUNCTION

The objective is to minimize the total setup time needed to complete the four jobs.

#Objective Function
m.setObjective(quicksum(Set_up_time[i][j]*X[i,j] for i in I for j in J), GRB.MINIMIZE)

CONSTRAINTS

There are 2 constraints that need to be satisfied:

1. Each machine performs at most one job by forcing (for each machine) the sum of X(i,j) over all jobs to be at most 1.
2. Each job is to be completed by forcing (for each job) the sum of X(i,j) over all machines to be at least 1.

These can be written as:

Computing these constraints as below:

#Constraint-1
for i in I:
     m.addConstr(quicksum(X[i,j] for j in J) <= 1)
#Constraint-2
for j in J:
    m.addConstr(quicksum(X[i,j] for i in I) >= 1)

OPTIMIZIED SET UP TIME

m.optimize()
print("Optimized Set up Time",m.objVal, "hours")
Gurobi Optimizer version 9.0.1 build v9.0.1rc0 (win64)
Optimize a model with 8 rows, 16 columns and 32 nonzeros
Model fingerprint: 0xee439cf7
Variable types: 0 continuous, 16 integer (0 binary)
Coefficient statistics:
  Matrix range     [1e+00, 1e+00]
  Objective range  [2e+00, 1e+01]
  Bounds range     [0e+00, 0e+00]
  RHS range        [1e+00, 1e+00]
Presolved: 8 rows, 16 columns, 32 nonzeros

Continuing optimization...


Explored 0 nodes (6 simplex iterations) in 0.01 seconds
Thread count was 8 (of 8 available processors)

Solution count 2: 15 28 

Optimal solution found (tolerance 1.00e-04)
Best objective 1.500000000000e+01, best bound 1.500000000000e+01, gap 0.0000%
Optimized Set up Time 15.0 hours

SENSITIVITY ANALYSIS

Based on the initial assumptions and the output below, the optimal assignment of 15 hours can be attained by assigning:

1. Machine 0 to Job 1
2. Machine 1 to Job 3
3. Machine 2 to Job 2
4. Machine 3 to Job 0

for i in I:
    print("-"*30)
    print("Machine:",i)
    print("-"*30)   
    for j in J:
        print("   Jobs",j,X[i,j].x)
------------------------------
Machine: 0
------------------------------
   Jobs 0 -0.0
   Jobs 1 1.0
   Jobs 2 -0.0
   Jobs 3 -0.0
------------------------------
Machine: 1
------------------------------
   Jobs 0 0.0
   Jobs 1 -0.0
   Jobs 2 -0.0
   Jobs 3 1.0
------------------------------
Machine: 2
------------------------------
   Jobs 0 -0.0
   Jobs 1 -0.0
   Jobs 2 1.0
   Jobs 3 -0.0
------------------------------
Machine: 3
------------------------------
   Jobs 0 1.0
   Jobs 1 0.0
   Jobs 2 -0.0
   Jobs 3 -0.0

VERIFYING RESULTS

Based on the assignment proposed above, the set up times for the machines have been highlighted in the Table below.

From the Table results,

Optimal Set Up Time = 5 + 5 + 3 + 2 = 15 which is the computed optimum set up time value, hence confirming optimal results