Introduction

The assignment problem deals with the optimal utilisation of resources. In every organisation,
resources such as employees, machines, tasks, or projects must be matched in a way that
leads to minimum cost or maximum efficiency. The assignment problem helps in making
such decisions scientifically. It provides a systematic method of assigning a set of jobs to a
set of agents so that the overall cost is minimised or overall profit is maximised.
The concept is widely used in operations management, HR allocation, job scheduling,
production management, and even service sectors like airlines, hospitals, call centres, and
logistics. The objective is to make sure that every job is matched to one agent and every agent
is assigned one job in the most economical way.

Meaning of Assignment Problem

The assignment problem refers to a decision-making situation where a number of tasks have
to be assigned to an equal number of workers or resources, and the aim is to achieve the most
favourable result (minimum cost or maximum profit). The data for the problem is presented
in the form of a cost matrix, where each cell shows the cost of assigning a particular job to a
particular worker. The goal is to find a combination of assignments that results in the best
outcome and satisfies the condition that one worker handles only one job.

Characteristics of Assignment Problem

• Square Matrix:
The assignment problem is represented as a square matrix where the number of jobs
and number of agents are equal. If they are different, dummy rows or columns are
added to make it square.
• One-to-One Assignment:
Each job must be assigned to exactly one agent, and each agent must be given exactly
one job.
• Objective of Optimization:
The goal is either to minimise cost, time, or wastage; or to maximise profit, output, or
efficiency.
• Decision Variables are 0 or 1:
Assignments take place on a yes-or-no basis. Either a particular worker gets a job or
does not.
• Based on Opportunity Costs:
The solution depends on relative costs. The method works by reducing the matrix to
identify the lowest opportunity cost combinations.
Types of Assignment Problem

• Minimisation Assignment Problem:

This is the most common type. Costs represent money, time, or effort. The aim is to
minimise the total.
• Maximisation Assignment Problem:
Here values represent profits or returns. The matrix is converted to a minimisation
matrix by subtracting all values from the highest value before applying the method.
• Balanced Assignment Problem:
The number of jobs equals the number of agents. No dummy row or column is
required.
• Unbalanced Assignment Problem:
When jobs and agents are unequal, dummy row or column is added with zero cost
entries to make it balanced.

Applications of Assignment Problem

• Staff Scheduling:
Assigning employees to shifts, tasks, or locations.
• Production Planning:
Assigning machines to specific jobs to reduce production time.
• Transportation and Distribution:
Assigning delivery routes to drivers to minimise travel time.
• Education Sector:
Allocating teachers to classes or subjects in an efficient manner.
• Healthcare:
Assigning doctors to patients or surgeries based on expertise and minimum delay.
• Airline and Hospitality Industry:
Matching crews to flights or rooms to guests.

The Hungarian Method

The Hungarian Method is the most widely used procedure for solving assignment problems
because it is simple, systematic, and guarantees an optimal solution. The method converts the
cost matrix into a system of opportunities that helps identify the ideal assignment.
Step 1: Row Reduction

Subtract the smallest value in each row from all the elements of that row. This creates at least
one zero in each row.

Step 2: Column Reduction

Subtract the smallest value in each column from all the elements of that column. This ensures
at least one zero in each column.

Step 3: Draw Minimum Number of Lines

Draw the minimum number of horizontal and vertical lines to cover all zeroes in the matrix.
If the number of lines equals the order of the matrix, an optimal assignment exists.

Step 4: Modify the Matrix (If Needed)

If the number of lines is less than the matrix size, adjust the uncovered elements:
• Find the smallest uncovered value.
• Subtract it from all uncovered elements.
• Add it to the elements covered by both a row and a column.
Repeat the step of covering zeros again until the number of lines equals the size of the matrix.

Step 5: Make the Final Assignments

Select zeros such that only one assignment is made in each row and each column. Ensure no
two assignments appear in the same row or column. This gives the optimal solution.

Balanced vs. Unbalanced Assignment Problem

Balanced:
When the number of jobs equals the number of agents.
The matrix is square and can be solved directly.
Unbalanced:
When the numbers differ.
A dummy job or dummy worker is added with zero cost values to balance the matrix. Once
balanced, the regular method is used.

Advantages of Assignment Problem

• Simple to Understand and Apply:

The assignment problem is easy to use because it follows a structured and logical
sequence of steps. Managers do not require advanced mathematical background to
apply the method. Once the cost matrix is prepared, the Hungarian Method guides the
user through row reduction, column reduction, and selection of optimal assignments.
This simplicity makes it accessible to students, professionals, and decision-makers
who want accurate solutions without complicated techniques.
• Ensures Optimal Allocation of Resources:
The major benefit of the assignment problem is its ability to give an optimal solution.
It guarantees that the total cost will be the lowest possible or the total profit will be
the highest possible, depending on the objective. Because every worker is matched to
one specific job and every job is given to one appropriate worker, the method ensures
 that no resource is wasted. This leads to higher organisational productivity and better
utilisation of skills and time.
• Reduces Overall Cost and Time:
By scientifically matching tasks to workers or machines, the assignment method helps
organisations reduce unnecessary expenses. When each job is assigned to the person
who performs it at the lowest cost, the organisation saves money as well as time. It
eliminates inefficiency that comes from random or intuitive decision-making. The
result is a streamlined workflow where tasks are completed faster and at a lower cost.
• Eliminates Personal Bias and Subjective Judgement:
One of the strengths of the assignment method is that decisions are based on data
rather than emotions. Managers sometimes assign tasks based on personal preferences
or assumptions about workers' abilities. The assignment problem prevents this by
focusing entirely on numerical costs or profits. As a result, the system becomes fair,
transparent, and objective, which helps in maintaining trust among employees and
stakeholders.
• Applicable Across Multiple Industries and Functions:
The assignment problem is not limited to one sector. It is widely used in
manufacturing to assign machines to jobs, in HR for scheduling employees, in
transportation for route allocation, in hospitals for assigning nurses or doctors to
patients, and even in sports for pairing teams to fixtures. Because of its flexibility and
wide applicability, it is considered one of the most useful tools in operations research
and quantitative techniques.
• Saves Managerial Effort in Decision-Making:
Managers often face situations where several jobs need to be assigned to several
workers, and manual decision-making becomes difficult. The assignment problem
reduces this burden by providing a clear procedure that automatically selects the best
combination. This allows managers to focus on strategic tasks while the model
handles operational allocation.
• Can Handle Large Data Matrices Efficiently:
Even if there are many workers and many jobs, the Hungarian Method can handle
large matrices efficiently. The systematic approach reduces the complexity and
organizes the data so that an optimal assignment becomes easily visible. This is
particularly useful for large organisations with many departments, machines, or labour
units.

Disadvantages of Assignment Problem

• Assumes One-to-One Assignment Only:

A major limitation is that each job can be assigned to only one person and each person
can perform only one job. In real life, an employee may handle multiple tasks or a
machine may work on several products. The assignment problem cannot handle such
 situations because it is designed strictly for one-to-one allocation. This restriction
makes it less useful where multiple workloads or shared responsibilities are common.
• Cannot Accommodate Complex or Special Constraints:
The basic model does not allow for conditions such as skill levels, job priorities,
workers’ preferences, or time shifts. Many organisations require additional constraints
like “worker A cannot work night shift” or “job B requires special certification.” Since
the assignment problem focuses only on cost or profit, these real-world conditions
cannot be represented unless the model is extended.
• Requires Costs or Profits to Be Known in Advance:
The assignment method assumes that all costs or profits associated with each job-
worker combination are known and fixed. However, in reality, costs may change due
to delays, machine breakdowns, or changes in productivity. When costs are uncertain
or unpredictable, the assignment model becomes less effective because it cannot
adjust to changing conditions.
• Not Suitable for Non-Linear Relationships:
The method works only when the relationship between job assignment and cost is
linear. This means that each assignment has a direct and independent effect on the
total cost. If the cost depends on combinations of tasks, teamwork, or sequence of
operations, the assignment problem cannot capture these complexities. Such situations
require more advanced models like integer programming or heuristic approaches.
• Additions of Dummy Rows or Columns May Distort Interpretation:
In unbalanced problems, dummy workers or dummy jobs are added to make the
matrix square. Although mathematically correct, this sometimes confuses
interpretation, especially for beginners. It may also oversimplify real-life scenarios
because the dummy entries do not represent actual people or tasks. This reduces the
model’s ability to reflect real operational situations accurately.
• Ignores Differences in Worker Skill Levels or Job Difficulties:
The assignment problem focuses only on numerical costs and does not consider
qualitative factors such as efficiency, experience, creativity, or physical effort required
for each job. In many organisations, some workers are more skilled and can handle
difficult tasks better than others. Since the model does not include these human
factors, the solution may not always be practically ideal.
• Does Not Handle Time-Based Dependencies:
Some tasks must be completed in a particular sequence or may depend on the
completion of earlier tasks. The assignment problem cannot manage such
dependencies. It only assigns tasks without considering the timing or flow of
processes. In such cases, other tools like scheduling models or network analysis
techniques (PERT/CPM) are more suitable.