ZeePedia

Assignment Problems:MATHEMATICAL FORMULATION OF THE PROBLEM

<< Transportation Problems:REVIEW QUESTIONS
Assignment Problems:SOLUTION OF AN ASSIGNMENT PROBLEM >>
Operations Research (MTH601)
201
Segment VI: Assignment Problems
Lectures 36- 37
201
img
Operations Research (MTH601)
202
INTRODUCTION
A special type of problem called the assignment problem is also an allocation problem. Here we have n
jobs to perform with n persons and the problem is how to distribute the jobs to the different persons involved.
Depending on the intrinsic capacity or merit or potential of the individual, he will be able to accomplish the task
in different times. Then the objective function in assigning the different jobs to different persons is to find the
optimal assignment that will minimize the total time taken to finish all the jobs by the individuals. For example,
we have four different building activities say, construction of a hotel, a theatre, a hospital and a multistoried
building and there are four contractors competing for these jobs. Each contractor has to be assigned only one
job. The allocation should aim to minimize the total time taken to complete the construction of all four activities
after assigning only one job to one individual. In fact there are (4!) permutations possible for allocating 4 jobs to
4 contractors. We have 24 possible ways and it is tiresome to list all the possible ways and find the best one. If
we have more jobs to be allocated, it is even difficult to list out the different permutations of allocations, then
what to speak of choosing the best combinations!
The problem may be stated formally as follows. Given an nxn array of real numbers representing the
individual return associated with assigning one item to one person. We have to find the best assignment so that
the total return is optimal.
Consider the following example, given below in the table 1
Table 1
Jobs
Men
A
B
C
D
1
5
6
8
7
2
4
7
6
6
3
5
4
6
5
4
6
7
4
6
In the above example, the elements of the matrix represent the times taken by A, B, C and D in accomplishing
the jobs 1, 2, 3 and we have to find which job is to be assigned to whom so that the total time taken will be
minimum. This is the objective function. Thus, this is also an allocation problem. A solution can be found to the
above problem by the algorithem used to solve the transportation problem of degenerate transportation problem.
In this way only 4 cells will be allocated. This leads to problem of degenerate transportation problem. There
should be (4 + 4 + 1) = 7 allocations in the initial basic feasible solution, but we have only 4 allocations. Hence
it is the degeneracy.
MATHEMATICAL FORMULATION OF THE PROBLEM
Considering the above example, we have four jobs and four persons. We want to allot one job to one
person so that the total time taken will be minimum. We shall formulate a mathematical model for the problem.
Let the decision variable xij be the assignment of ith job to jth person, and cij be the time taken for ith job
by the jth person.
n
n
z=∑
cij
xij
The objective function is to minimize
i =1
j =1
202
Table of Contents:
  1. Introduction:OR APPROACH TO PROBLEM SOLVING, Observation
  2. Introduction:Model Solution, Implementation of Results
  3. Introduction:USES OF OPERATIONS RESEARCH, Marketing, Personnel
  4. PERT / CPM:CONCEPT OF NETWORK, RULES FOR CONSTRUCTION OF NETWORK
  5. PERT / CPM:DUMMY ACTIVITIES, TO FIND THE CRITICAL PATH
  6. PERT / CPM:ALGORITHM FOR CRITICAL PATH, Free Slack
  7. PERT / CPM:Expected length of a critical path, Expected time and Critical path
  8. PERT / CPM:Expected time and Critical path
  9. PERT / CPM:RESOURCE SCHEDULING IN NETWORK
  10. PERT / CPM:Exercises
  11. Inventory Control:INVENTORY COSTS, INVENTORY MODELS (E.O.Q. MODELS)
  12. Inventory Control:Purchasing model with shortages
  13. Inventory Control:Manufacturing model with no shortages
  14. Inventory Control:Manufacturing model with shortages
  15. Inventory Control:ORDER QUANTITY WITH PRICE-BREAK
  16. Inventory Control:SOME DEFINITIONS, Computation of Safety Stock
  17. Linear Programming:Formulation of the Linear Programming Problem
  18. Linear Programming:Formulation of the Linear Programming Problem, Decision Variables
  19. Linear Programming:Model Constraints, Ingredients Mixing
  20. Linear Programming:VITAMIN CONTRIBUTION, Decision Variables
  21. Linear Programming:LINEAR PROGRAMMING PROBLEM
  22. Linear Programming:LIMITATIONS OF LINEAR PROGRAMMING
  23. Linear Programming:SOLUTION TO LINEAR PROGRAMMING PROBLEMS
  24. Linear Programming:SIMPLEX METHOD, Simplex Procedure
  25. Linear Programming:PRESENTATION IN TABULAR FORM - (SIMPLEX TABLE)
  26. Linear Programming:ARTIFICIAL VARIABLE TECHNIQUE
  27. Linear Programming:The Two Phase Method, First Iteration
  28. Linear Programming:VARIANTS OF THE SIMPLEX METHOD
  29. Linear Programming:Tie for the Leaving Basic Variable (Degeneracy)
  30. Linear Programming:Multiple or Alternative optimal Solutions
  31. Transportation Problems:TRANSPORTATION MODEL, Distribution centers
  32. Transportation Problems:FINDING AN INITIAL BASIC FEASIBLE SOLUTION
  33. Transportation Problems:MOVING TOWARDS OPTIMALITY
  34. Transportation Problems:DEGENERACY, Destination
  35. Transportation Problems:REVIEW QUESTIONS
  36. Assignment Problems:MATHEMATICAL FORMULATION OF THE PROBLEM
  37. Assignment Problems:SOLUTION OF AN ASSIGNMENT PROBLEM
  38. Queuing Theory:DEFINITION OF TERMS IN QUEUEING MODEL
  39. Queuing Theory:SINGLE-CHANNEL INFINITE-POPULATION MODEL
  40. Replacement Models:REPLACEMENT OF ITEMS WITH GRADUAL DETERIORATION
  41. Replacement Models:ITEMS DETERIORATING WITH TIME VALUE OF MONEY
  42. Dynamic Programming:FEATURES CHARECTERIZING DYNAMIC PROGRAMMING PROBLEMS
  43. Dynamic Programming:Analysis of the Result, One Stage Problem
  44. Miscellaneous:SEQUENCING, PROCESSING n JOBS THROUGH TWO MACHINES
  45. Miscellaneous:METHODS OF INTEGER PROGRAMMING SOLUTION