Skip to content

Operations Management and Strategic Management · Job Evaluation, Job Allocation - Assignment

Job Allocation and Assignment Problem Basics for CMA Inter

Updated 10 October 2026 · Fact-checked

The assignment problem allocates n jobs to n workers, one job per worker and one worker per job, so that total cost is minimised (or total profit maximised). It is a special case of linear programming with 0-1 variables. To solve it, build the cost matrix, check it is square, then apply the Hungarian method.

Understand Job Allocation and Assignment Problem Basics

Suppose a firm has four machine operators and four jobs. Each operator can do each job, but the cost differs by operator. You must give one job to each operator so that the total cost is lowest. This is the assignment problem.

It is a special case of a linear programming problem. The decision variable xij is 1 if worker i gets job j, and 0 otherwise. Every worker gets exactly one job and every job goes to exactly one worker. The objective is to minimise the sum of cost × xij over all pairs.

It is also a special case of the transportation problem. Think of workers as sources and jobs as destinations. Each supply is 1 and each demand is 1. Because of this, the number of workers must equal the number of jobs. The matrix is square. If it is not, you add a dummy row or column with zero costs.

The usual assumptions are: the number of workers equals the number of jobs; each worker does only one job; each job is done by only one worker; the cost (or time or profit) of every worker-job pair is known and fixed; and the objective is a single measure, either minimise cost or maximise profit.

The key idea behind the solution is simple. If you subtract a constant from every cost in a row or column, the best assignment does not change. Only the total changes by that constant. The Hungarian method uses this to create zeros and then picks an assignment on the zeros.

Key rules to remember

Objective function (minimisation)
Minimise Z = Σi Σj cij xij, for i, j = 1 to n
cij is the cost of giving job j to worker i. Use maximise if cij is profit.
Worker constraint
Σj xij = 1 for every worker i
Each worker gets exactly one job.
Job constraint
Σi xij = 1 for every job j
Each job is done by exactly one worker.
Binary condition
xij = 0 or 1
xij = 1 means worker i is assigned job j.
Balanced condition
Number of workers = Number of jobs
If not equal, add dummy rows or columns with zero cost to make the matrix square.
Number of variables and constraints
n × n variables; 2n constraints
A 4 × 4 problem has 16 variables and 8 constraints.

How to solve Job Allocation and Assignment Problem Basics questions

Use this method to formulate and set up any basic assignment question. Solving then follows the Hungarian method.

  1. 1Read the problem and list the workers (or machines) as rows and the jobs as columns.
  2. 2Write the cost, time or profit matrix from the data given.
  3. 3Count rows and columns. If they differ, add a dummy row or column with zero entries to make it square.
  4. 4Define the variable: xij = 1 if worker i is assigned job j, otherwise 0.
  5. 5Write the objective function: minimise Σ cij xij for cost or time, or maximise for profit.
  6. 6Write the constraints: each row sums to 1 and each column sums to 1, with xij = 0 or 1.
  7. 7Solve with the Hungarian method: subtract row minimum, then column minimum, cover zeros with the least lines, and assign on zeros.
  8. 8Write the final assignment pairs and compute total cost from the original matrix, not the reduced one.

Quickest way: Row-column reduction check for small matrices

When to use it: Use for 3 × 3 or 4 × 4 matrices when the question asks only for the optimal assignment or minimum cost.

  1. Subtract the smallest number in each row from every number in that row.
  2. Subtract the smallest number in each column of the new matrix from that column.
  3. Look for a row or column with exactly one zero. Assign that zero and strike out its row and column.
  4. Repeat until all workers have jobs. If you get stuck, use the line-covering step of the Hungarian method.
  5. Add the original costs of the chosen pairs to get the total.

Common mistakes in Job Allocation and Assignment Problem Basics

  • Solving an unbalanced matrix without adding a dummy

    Students rush into row reduction without counting rows and columns.

    Fix: Count rows and columns first. Add a dummy row or column with zero costs to make it square.

  • Adding the reduced costs to find the total cost

    The final matrix with zeros looks like the answer.

    Fix: Always return to the original matrix. Add the original cost of each assigned pair.

  • Confusing assignment with transportation

    Both use a cost matrix and look similar.

    Fix: Remember that assignment has all supplies and demands equal to 1, needs a square matrix, and gives 0-1 values. Transportation has varying supplies, demands and quantities.

  • Writing constraints as 'less than or equal to'

    Students copy the pattern from general LPP.

    Fix: Assignment constraints are equalities: each row and column sums to exactly 1.

  • Forgetting to state the variable definition

    Students jump straight to the equations.

    Fix: Always write 'xij = 1 if worker i is assigned job j, otherwise 0' first. Examiners give marks for it.

Worked examples

Example 1

Four workers A, B, C, D are to be given four jobs 1, 2, 3, 4, one each. The cost in ₹ is: A: 1: 20, 2: 25, 3: 22, 4: 28; B: 15, 18, 23, 17; C: 19, 17, 21, 24; D: 25, 23, 24, 24. Formulate the problem as an LPP.

Show the solution
  1. Define xij = 1 if worker i is assigned job j, otherwise 0, for i = A, B, C, D and j = 1, 2, 3, 4.
  2. Objective: Minimise Z = 20xA1 + 25xA2 + 22xA3 + 28xA4 + 15xB1 + 18xB2 + 23xB3 + 17xB4 + 19xC1 + 17xC2 + 21xC3 + 24xC4 + 25xD1 + 23xD2 + 24xD3 + 24xD4.
  3. Worker constraints: xA1 + xA2 + xA3 + xA4 = 1, and similarly for B, C and D.
  4. Job constraints: xA1 + xB1 + xC1 + xD1 = 1, and similarly for jobs 2, 3 and 4.
  5. Binary condition: every xij = 0 or 1.

Answer: The LPP has 16 variables and 8 equality constraints, with the objective and constraints as written above.

Example 2

Three workers P, Q, R are to do three jobs. The cost in ₹ is: P: Job 1: 8, Job 2: 6, Job 3: 10; Q: 9, 7, 12; R: 7, 8, 9. Find the assignment with minimum total cost.

Show the solution
  1. The matrix is 3 × 3, so it is balanced.
  2. Row reduction: subtract 6 from P, 7 from Q, 7 from R. P: 2, 0, 4; Q: 2, 0, 5; R: 0, 1, 2.
  3. Column reduction: column minima are 0, 0, 2. Subtract 2 from column 3. Matrix: P: 2, 0, 2; Q: 2, 0, 3; R: 0, 1, 0.
  4. Zeros are at P2, Q2, R1, R3. Cover them with lines: column 2 and row R. That is 2 lines, which is less than 3, so improve.
  5. Smallest uncovered number is 2 (P1, P3, Q1, Q3 are uncovered; the smallest is 2). Subtract 2 from uncovered, add 2 at the intersection of the lines (R2). New matrix: P: 0, 0, 0; Q: 0, 0, 1; R: 0, 3, 0.
  6. Now assign. Q has zeros at 1 and 2. R has zeros at 1 and 3. P has zeros at 1, 2, 3. Choose Q-2, R-1, P-3. Check: all zeros, one per row and column.
  7. Total cost from the original matrix: P3 = 10, Q2 = 7, R1 = 7. Sum = 24.
  8. Check another option: P-1 (8), Q-2 (7), R-3 (9) = 24. Also 24, so there are multiple optimal solutions.

Answer: Minimum total cost is ₹24. One optimal assignment is P to Job 3, Q to Job 2, R to Job 1. P-1, Q-2, R-3 is another optimal assignment with the same cost.

Exam tips

  • For a formulation question, write the variable definition, objective function, both sets of constraints and the binary condition. Each earns marks.
  • In MCQs, remember that the assignment problem needs a square matrix and that its constraints are equalities with right-hand side 1.
  • The difference between assignment and transportation is a favourite short-answer question. Prepare a four-point comparison on supply and demand, matrix shape, variable values and method.
  • Always compute the final cost from the original matrix and show the pairs clearly.

Practice questions from Job Evaluation, Job Allocation - Assignment

Job Allocation and Assignment Problem Basics in other exams

The same ground in other exams, if you are preparing for more than one or want another angle on it.

Job Allocation and Assignment Problem Basics: frequently asked questions

What is the difference between the assignment problem and the transportation problem?

In the assignment problem, each source supplies exactly one unit and each destination needs exactly one unit, so the matrix is square and variables are 0 or 1. In the transportation problem, supplies and demands can be any quantities and the shipments can take any non-negative value. The assignment problem is a special case of the transportation problem.

Why must the number of workers equal the number of jobs?

Each worker gets exactly one job and each job goes to exactly one worker. This is only possible with a square matrix. If the numbers differ, you add a dummy row or column with zero costs.

Is the assignment problem a linear programming problem?

Yes. It has a linear objective and linear constraints. The variables are 0 or 1, but the structure of the problem guarantees that the Hungarian method gives a valid optimal solution.

How do I allocate jobs to workers to minimise cost?

Write the cost matrix, make it square, and apply the Hungarian method. Reduce rows and columns to create zeros, then assign on the zeros. Add the original costs of the chosen pairs to get the minimum total.