Maharashtra Board Class 12 Maths Commerce Part II Chapter 7 Assignment Problem and Sequencing PDF Download

Assignment Problem and Sequencing

Let's Study

Definition of Assignment Problem

Assignment model

Hungarian method of solving Assignment Problem

Special cases of Assignment Problem

Sequencing Problem

Types of Sequencing Problem

Finding an optimal sequence

Let's Recall

Linear Programming Problem

Let's Learn

Introduction To Assignment Problem:

We often come across situations in which we have to assign n jobs to n workers. All n workers are capable of doing all jobs, but with a varying cost. Hence our task is to find the best possible assignment that gives maximum efficiency and minimum cost. For example, assigning activities to students, subjects to teachers, different routes of pizza delivery, boys, salesmen to different regions, jobs to machines, products to factories, research problems to teams, vehicles and drivers to different routes, etc. A problem of this nature is called an assignment problem.

Definition Of Assignment Problem:

Assignment problem is a special type of problem which deals with allocation of various resources to various activities on one to one basis. It is done in such a way that the total cost or time involved in the process is minimum or the total profit is maximum.

Conditions:

i) Number of jobs is equal to number of machines or workers.

ii) Each worker or machine is assigned to only one job.

iii) Each worker or machine is independently capable of handling any job.

iv) Objective of the assignment is clearly specified (minimizing cost or maximizing profit).

Assignment Model:

Given n workers and n jobs with the cost of every worker for every job, the problem is to assign each worker to one and only one job so as to optimize the total cost.

Let C_ij be the cost of assigning i^th worker to j^th job, x_ij be the assignment of i^th worker to j^th job and x_ij = 1, if i^th worker is assigned to j^th job = 0, otherwise.

Following table represents the cost of assigning n workers to n jobs.

The objective is to make assignments that minimize the total cost.

Thus, an assignment problem can be represented by n × n matrix which covers all the n! possible ways of making assignments.

Teacher's Note

Assignment problems are very common in companies. For example, assigning delivery routes to delivery boys helps save time and money. Think of a pizza company that needs to assign routes to its delivery boys each day.

Exam Trick

Remember: In assignment problems, each worker gets exactly ONE job and each job goes to exactly ONE worker. It is like a one-to-one matching game. Think of matching socks in a laundry - one sock pairs with one other sock only.

Points To Remember

Assignment problem means giving one job to one worker.

Each worker can do all jobs but with different costs.

We want to reduce total cost or increase profit.

The cost matrix is always a square matrix (n × n).

The goal is to find the best possible matching between workers and jobs.

This is a preview of the first 3 pages. To get the complete book, click below.