Skip to content
← Mathematics and Statistics

Mathematics and Statistics · Class 12 Commerce

Ch 15Assignment Problem and Sequencing — Class 12 Mathematics and Statistics, concept-first.

Suppose a workshop has four machines and four jobs waiting to be processed. Each machine can do any of the jobs, but the cost (or time) of doing a particular job differs from machine to machine — one machine is fast at drilling but slow at grinding, another is the reverse.

32

Q&A

4

Concepts

Not available

Exam weightage

Start learning — read this chapter →

Key concepts

Hover a concept to preview it and jump to its most relevant Q&A.

The Assignment Problem

The assignment problem is a one-to-one allocation problem: match agents to tasks, one each, to minimise total cost, given a square cost matrix .

Most relevant Q&A

Start with this concept →

Chapter contents

The NCERT structure, section by section. Open a section to see its questions, then read the concept-first solution.

1

What is an Assignment Problem?

Suppose a workshop has four machines and four jobs waiting to be processed. Each machine can do any of the jobs, but the cost (or time) of doing a particular job differs from machine to machine — one…

2

The Hungarian Method (Balanced Minimisation)

The Hungarian method solves a balanced () minimisation assignment problem exactly. It rests on one key idea: adding or subtracting a constant to every entry of a whole row (or a whole column) does not…

3

Maximisation Assignment Problems

The Hungarian method is built to minimise. Many real problems instead ask us to maximise — assign salesmen to territories to make total profit (or sales, output, efficiency) as large as possible.

4

Unbalanced and Restricted Assignments

Two common departures from the neat minimisation problem are easily handled without changing the method.

5

Sequencing Problems: Basic Concepts

A sequencing problem asks a different question from the assignment problem. Here we have several jobs, each of which must pass through the same set of machines in the same technological order, and we…

6

Processing n Jobs Through Two Machines

Consider jobs, each of which must be processed first on Machine 1 () and then on Machine 2 (), in that order. Let be the time of job on and its time on .

7

Processing n Jobs Through Three Machines

When each of jobs must pass through three machines in the fixed order , there is no simple rule in general.

Exercises

+Show 6 questions6 questions
  1. Q1What is an assignment problem? State any three assumptions on which the standard assignment model is based, and explain why enumerating all…Free
  2. Q2In the Hungarian method, after row and column reduction the minimum number of lines needed to cover all the zeros of a $5 \times 5$ matrix i…Free
  3. Q8Define a sequencing problem. State Johnson's rule for sequencing $n$ jobs on two machines, and explain how the total elapsed time and a mach…Preview
  4. Q10Four jobs are processed on two machines $M_1$ (first) then $M_2$, with times (in minutes): | Job | A | B | C | D | |---|---|---|---|---| | $…Preview
  5. Q12A three-machine ($M_1 \to M_2 \to M_3$) sequencing problem can be converted to a two-machine problem using Johnson's rule if: (a) $\min A_i…Preview
  6. Q13Assign four workers $A, B, C, D$ to four jobs $J_1, J_2, J_3, J_4$ (one each) to minimise total cost (in $₹$): | Worker | $J_1$ | $J_2$ | $J…Preview

Sample & Board Papers

Sample papers and previous-year board questions for this subject.

+Show 19 questions19 questions
  1. Q1Choose the correct alternative : The assignment problem is said to be balanced if it is a ______. (a) Square matrix (b) Rectangular matrix (…Preview
  2. Q2State whether the following statement is true or false: To convert a maximization-type assignment problem into a minimization problem, the s…Preview
  3. Q3A job production unit has four jobs P, Q, R, and S which can be manufactured on each of the four machines I, II, III, and IV. The processing…Preview
  4. Q4Five jobs are performed first on machine $M_1$ and then on machine $M_2$. Time taken in hours by each job on each machine is given below: |…Preview
  5. Q5In an assignment problem, if number of column is greater than number of rows, then a dummy column is added. (a) True (b) FalsePreview
  6. Q6A marketing manager has list of salesmen and territories. Considering the travelling cost of the salesmen and the nature of territory, the m…Preview
  7. Q7Six jobs are performed on Machines $M_1$ and $M_2$ respectively. Time in hours taken by each job on each machine is given below: | Jobs $\ri…Preview
  8. Q8To use the Hungarian method, a profit maximization assignment problem requires ______. (a) Converting all profits to opportunity losses (b)…Preview
  9. Q9The time interval between starting the first job and completing the last job including the idle time (if any) in a particular order by the g…Preview
  10. Q10A toy manufacturing company produces five types of toys. Each toy has to go through three machines A, B, C in the order ABC. The time requir…Preview
  11. Q11Three new machines $M_1$, $M_2$, $M_3$ are to be installed in a machine shop. There are four vacant places A, B, C, D. Due to limited space,…Preview
  12. Q12The objective of an assignment problem is to assign ______. (a) Number of jobs to equal number of persons at maximum cost. (b) Number of job…Preview
  13. Q13Find the sequence that minimizes the total elapsed time to complete the following jobs in the order AB. Find the total elapsed time and idle…Preview
  14. Q14Solve the following assignment problem to maximization: | | I | II | III | IV | V | | --- | --- | --- | --- | --- | --- | | 1 | 18 | 24 | 19…Preview
  15. Q15To convert an assignment problem into a minimization problem, the smallest element in the matrix is deducted from all other elements.Preview
  16. Q16Solve the following assignment problem for minimization: | Men | Tasks (in hours) | | | | | --- | --- | --- | --- | --- | | I | II | III | I…Preview
  17. Q17Determine the optimal sequence of jobs that minimizes the total elapsed time for the data given below (processing time on machines is given…Preview
  18. Q18Five jobs are performed first on machine $M_1$ and then on machine $M_2$. Time taken in hours by each job on each machine is given below: |…Preview
  19. Q19A computer centre has 4 expert programmers. The centre needs four application programmes to be developed. The head of the computer centre af…Preview

More questions

+Show 7 questions7 questions
  1. Example 3Three operators $O_1, O_2, O_3$ are to be assigned to three tasks $T_1, T_2, T_3$, one operator per task. The time (in minutes) each operato…Free
  2. Example 4Four workers $W_1, W_2, W_3, W_4$ are to be assigned to four jobs $J_1, J_2, J_3, J_4$, one job each. The cost (in $₹$ hundreds) is: | Worke…Free
  3. Example 5A firm has three salesmen $S_1, S_2, S_3$ and three territories $T_1, T_2, T_3$. The expected monthly profit (in $₹$ thousands) from each sa…Free
  4. Example 6A shop must complete four jobs $J_1, J_2, J_3, J_4$ but has only three machines $M_1, M_2, M_3$ (each machine can take one job). The cost (i…Preview
  5. Example 7Three machines $A, B, C$ are to be assigned to three jobs $J_1, J_2, J_3$. Machine $B$ **cannot** process job $J_3$ (it lacks the required a…Preview
  6. Example 9Five jobs must each be processed first on Machine $M_1$ and then on Machine $M_2$. The processing times (in hours) are: | Job | 1 | 2 | 3 |…Preview
  7. Example 11Five jobs must be processed through three machines in the order $M_1 \to M_2 \to M_3$. The times (in hours) are: | Job | 1 | 2 | 3 | 4 | 5 |…Preview