An assignment problem is a special case of:

Linear programming problem. It is a special L.P.P. (transportation type).

The method used to solve an assignment problem is the:

Hungarian method. Developed from the work of Hungarian mathematicians.

An unbalanced assignment problem is balanced by adding a dummy row or column with:

Zero costs. Dummy jobs or workers cost nothing.

A maximisation assignment problem is converted to minimisation by:

Subtracting all elements from the largest element. The opportunity loss matrix.

Adding the largest element to all

Dividing by the largest element

In a restricted assignment problem, the restricted cell is given:

A very high (infinite) cost. So it is never chosen.

Maharashtra State Board · HSC Commerce · Class 12 (Std XII)

Class 12 Maths and Statistics Part 2 Chapter 7: Assignment Problem and Sequencing

Short notes, key concepts, quick revision and practice MCQs with answers

An assignment problem allots jobs to workers or machines one-to-one at minimum cost (or maximum profit); a sequencing problem finds the order of processing jobs on machines to minimise total time. The chapter solves assignments by the Hungarian method, handles special cases, and sequences n jobs on two and three machines.

Key concepts: Assignment Problem and Sequencing

Assignment problem: A special case of linear programming in which each worker (or machine) is assigned exactly one job and each job to exactly one worker, to minimise total cost or time (or maximise profit).
Hungarian method: Step 1: subtract the smallest element of each row from that row. Step 2: subtract the smallest element of each column. Step 3: cover all zeros with the minimum number of lines. If lines = order n, make assignments on zeros (one per row and column). If not, subtract the smallest uncovered element from all uncovered elements, add it at intersections, and repeat.
Making assignments: Start with a row or column having a single zero, assign it and cross out other zeros in its row and column; continue until n assignments are made.
Special cases: Unbalanced problem: add a dummy row or column with zero costs. Maximisation: subtract every element from the largest element and minimise. Restricted assignment: put a very high (∞) cost in the restricted cell. Extra zeros may give alternative optimal solutions.
Sequencing problem: Deciding the order in which jobs are processed on machines, each machine handling one job at a time in the same order, so as to minimise the total elapsed time.
n jobs on two machines (Johnson's rule): Find the smallest processing time. If it is on machine A, place that job first; if on machine B, place it last. Remove the job and repeat. Ties may be broken arbitrarily.
Elapsed and idle time: Total elapsed time T is the time from the start of the first job to the end of the last job. Idle time of a machine = T − total processing time on that machine.
n jobs on three machines: If min Aᵢ ≥ max Bᵢ or min Cᵢ ≥ max Bᵢ, replace them by two fictitious machines G = A + B and H = B + C and apply Johnson's rule.

Quick revision: important points

An n × n assignment problem has n! possible assignments.
The Hungarian method applies to minimisation problems.
Dummy rows or columns have zero costs.
Idle time of machine B includes the wait before the first job reaches it.

Practice MCQs with answers

An assignment problem is a special case of:
1. Time series
2. Linear programming problem
3. Regression
4. Index numbers
Show answer
Answer: B. Linear programming problem
It is a special L.P.P. (transportation type).
The method used to solve an assignment problem is the:
1. Simplex method
2. Hungarian method
3. Least squares method
4. Graphical method
Show answer
Answer: B. Hungarian method
Developed from the work of Hungarian mathematicians.
An unbalanced assignment problem is balanced by adding a dummy row or column with:
1. Very high costs
2. Zero costs
3. Negative costs
4. Average costs
Show answer
Answer: B. Zero costs
Dummy jobs or workers cost nothing.
A maximisation assignment problem is converted to minimisation by:
1. Adding the largest element to all
2. Subtracting all elements from the largest element
3. Dividing by the largest element
4. Changing all signs to positive
Show answer
Answer: B. Subtracting all elements from the largest element
The opportunity loss matrix.
In a restricted assignment problem, the restricted cell is given:
1. A zero cost
2. A very high (infinite) cost
3. A negative cost
4. The average cost
Show answer
Answer: B. A very high (infinite) cost
So it is never chosen.

All Class 12 Maths and Statistics chapters

Class 12 Maths and Statistics notes: all chapters