0% found this document useful (0 votes)
10 views16 pagesAssignment Method
discussed about how to solve the assignment problems
Uploaded by
alrafi2535Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF or read online on Scribd
0% found this document useful (0 votes)
10 views16 pagesAssignment Method
discussed about how to solve the assignment problems
Uploaded by
alrafi2535Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF or read online on Scribd
/ 16
i
Pours 131
Thirty wits assigned
to square YB.
stone squares from the previous solution, but in order to satisfy the rule that
the number of stone squares equals the number of rim requirements minus
1, we will keep XB as a stone square and only eliminate square YC. We have
placed the zero stone in square XB, as shown in Figure 11-32.
In some cases more than two stone squares may be reduced to zero.-In
such cases we eliminate only one of those squares, so that the number of
stone squares in the solution still satisfies the rule of rim requirements minus
1. The Bass Gravel Company problem can now be solved using the standard 7,
procedure, which was discussed before. =
Wie assignment problem
TSPECAL CASE OF HE
“TRANSPORTATION
PROSLEN: THE
computationally more efficient than the simplex method for a-special class — ASSIGIMENT PAOALEM
of problems. We shall also show that the assignment problem is a special case 518
‘CHAPTER 11
NUMBERS OF 3
EQUALS NUMBER OF
COLUMNS IN THE
ASSIGNMENT PROBLEM
b
USE THE NORTHWEST
CORNER RULE TO GET
THE INITIAL SOLUTION
WHY THE
TRANSPORTATION
‘METHOD IS INEFFICIENT
FOR THE ASSIGNMENT
PROBLEM
111
Cost for each job-
machine assignment
for Kellum Machine
Shop problem
of the transportation problem. In other words, we can solve an assignment
problem using the transportation method.
‘The Kellum Machine Shop does custom metalworking for a number of
local plants. Kellum currently has three jobs to be done (let us symbolize
them A, B, and C). Kellum algo-has three machines on which to do the work
(X, Y, and Z). Any one of the jobs can be processed completely on any one
of the machines, Furthermore, the cost of processing any job on any machine
is known. The assignment of jobs to machines must be on. a one-to-one basis;
that is, each job must be assigned exclusively to one and only one machine.
The objective is to assign the jobs to the machines so as to minimize total
cost.
‘The cost data are given in Table 11-11. The number of rows (jobs) equals
the number of columns (machines). This is one characteristic of all assignment
problems. Another characteristic is that in the optimal solution there will be
one and only one assignment irta given row or column of the given assignment
table. These characteristics are-peculiar-to the assignment problem. In the
general transportation problem, for example, it is niot necessary to have an
equal number of sources and destinations; nor does the transportation method
require-that there be one assignment only in a given row or column of the
optimal solution.
USING THE TRANSPORTATION METHOD.
TO-SOLVE THE ASSIGNMENT PROBLEM
Since each job must be assigned to one and only one machiine, we caftsay
that the job regurenent Tor each jobs and ther the macKine capacity Tor
Zach_machine-is also J. This might be the caserTor example, when the
{ditional setup expenses are such as to prohibit the partial assignment of
machines to more than one job. Given the cost data of Table 11-11, the job
requirements, and machine capacities, we _can-set-up-the transportation
tableau given in Figure 11-33, showing the initial solution using the northwest
corner rule.
There are three stone squares in this initial solution. However, according
to the rule of rim requirements minus 1, we should have five stone squares.
Hence we must add two zero stone squares to resolve the degeneracy. This
has been done in Figure 11-34.
The Kellum problem can now be solved in the usual manner. Because all
the stone squares have a value of 1 or 0, a degenerate solution will result
ivith each subsequent solution: The: reason far this can be attributed to the two special characteristics of the assignment problem mentioned in the
previous section. Having to cope with the problem of degeneracy at each
solution makes the transportation method computationally inefficient for
solving an assignment problem.
— USING THE ASSIGNMENT METHOD.
The assignment method, also known as Flood’s technique of the Hungarian
na ride Tent_method_of solving
assignment problems. There are basically three steps in the assignment
method. We preenUie reasoning underlying each of these steps.
Foie 1132
‘The Kellan
assignment protlem
set up in the
ASSIGNMENT METHOD,
1S MORE EFFICIENT
#6
Cegenurary resoived
ie 113" 520 .
CHAPTER 11
CONCEPT OF
‘OPPORTUNITY cosT:
‘AND OPPORTUNITY
COST TABLE
4J0B-0PPORTUNITY
costs
MACHINE-OPPORTUNITY
costs
uaa 1142
Cost of each job-
machine assignment
for the Kelium
‘Machine Shop
problem
Step 1: Determine the opportunity-cost table Since the assignment method
applies the concept of opportunity costs, a brief explanation of this concept
may be helpful. The cost of any kind of action or decision consists of the
opportunities that are sacrificed in taking that action, Many of us go through
an opportimity-cost analysis without realizing it. For example, a friend who
had been thinking of buying a new house drives by in a brand-new car. He
promptly starts explaining how nice it is living in an apartment. This is an
example of opportunity-cost analysis. If we do one thing, we cannot do
another.
Let us now sce how this concept plays an important part in the computational
mechanics of the assignment method. For convenience, the cost data for the
Kellum Machine Shop problem are repeated in Table 11-12.
Suppose we decide to assign job A to machine X. The table shows that the
cost of this assignment is $25. Because machine X could just as well process
job B for $15, it is clear that our assignment of job A to machine X is not
the best decision. ‘Therefore, when we arbitrarily assign job A to machine X,
we are in effect sacrificing the opportunity to save $10 ($25 — $15). This
sacrifice is more generally referred to as an opportunity cost. In other words,
the decision to assign Nob A te HACHNE-X-preciudes THe aBignment of job B
to machine X, given the restriction that one and only one job can be assigned
to-a machine. Thus we say that the opportunity cost of the assignment of job
A to machine X is $10 with respect to the lowest-cost assignment for machine
X (or column X). Similarly, a Kellum decision to assign job C to machine X
would involve an opportunity cost-of $7 ($22.— $15). Finally, since the
assignment of job B.to machine X is the best assignment, we can say that the
opportunity cost of this assignment is zero ($15 — $15). More specifically
these costs can_be called the job-opportunity costs with regard to machine X. If
We were to subtract the lowest cost-of-column-Y (machine Y) from all the
costs in this column, we would-have the job-opportunity costs with regard to
machine Y. The same procedure in column Z would give the job-opportunity
costs for machine Z.
In addition to: these job-opportunity costs, there are machine-opportunily
costs. We could, for example, assign job A to machine X, Y, or Z. If we
assigned job A to machine Y, there would be an opportunity cost attached
to this decision. The assignment of job A to machine Y costs $31, while the
assignment of job A to machine X costs only $25. Therefore the opportunity
cost of assigning job A to machine’ Y is $6 ($31 — $25). Similarly the
assignment of job A to machine Z involves an opportunity cost of $10 ($35
Machine. = $25). A zero opportunity cos is involved in. the assignment of job At
machine X, since this is the best assignment for job.A.(row A), Hence we —
+ could compute the machine opportunity costs for each row (each job) by
subtracting the lowest costenury in each row from all cost entries in its row.
This discussion on opportunity costs should provide an understanding of
the mechanics of the first step in the assignment method, which is to develop
the toal-opportunity-cost table. There are two parts to this first step. Part a
is to subtract the lowest entry in each column‘of the original cost table from
all entries in that column. The resulting new table with computations is given
in Table 11-13.
Table 11-13, should be recognized as the Jb oppercanty table. Now the
objective of this first step is to develop a total-opportunity-cost table. In other
words, we want to consider the machine-opportunity costs also.-Part b of step
1 accomplishes this, but not in exactly the same way as Our intuitive analysis.
The effect, however, is the same. Part b is to subtract the lowest entry in each
row of the lable obtained in part from all numbers in that row. The new table
and computations are shown in Table 11-14.
Step 2: Determine whether an optimal assignment can be made The
objective is to assign the jobs to the machines so as to minimize total costs.
With the total-opportunity-cost table, this objective will be achieved if we can
assign the jobs to the machines in such a way as to obtain a total opportunity _
cost of zero. In other words, we want to make the three hest possible
assignments, ments, The best possible assignment of a job to a machine would involve an
tunity cost of
Looking at the total opportunity cost in Table 11-14, we find four squares
with zeros, each indicating a zero opportunity cost for that square (assignment).
Hence, we could assign job A to machine X and job C to machine Y or Z, all
assignments having an opportunity cost of zero. If this were done, however,
‘TWO PARTS IN
[DETERMINING THE
OPPORTUNITY-COST
TABLE
PARTA
PART B
CAN AN OPTIMAL
ASSIGNMENT BE MADE?
THE BEST POSSIBLE
ASSIGNMENT
TABLE 11-46
‘Step 1, part b: total
ity-cost table 522,
CHAPTER 11
F
OPTIMAL
ASSIGHMENT CANNOT
‘UNITY-COST
PARTS A AND @ IN
MODIFYING THE
OPPORTUNITY-COST
TABLE
TALE 115,
Test for optimal
assignment for
Kellum Machine,
‘Shop problem
‘MODIFY THE
we
we could not assign job’ B to any machine with a zero opportunity cost. The
reason here is that the assignment of job A to machine X precludes the
assignment of job B to machine X. If we had a zero in’ square BY, we could
make an optimal assignment, In other words, to make an optimal assignment
of the three jobs to the three machines, we must locate three zero squares in
the table such that a complete assignment to these squares can be made with
a total opportunity cost of zero.
re is a conven ini ther an optimal assign.
mentcan be made. This method consists of drawing straight lines (vertically
ment can be mad -
and horizontally) through the total-opportunity-cost table in such a manner
as_to_ minimize the numbers of lines necessary _to cover all zero squares. If
the number of ines cquals the number of rows in the table, an optimal
assignment can be Grade andihe problem is solved. On the other hand, an
optimal assignment cannot be made if the number of lines is less than the
number of rows. In this case we must develop a new total-opportunity-cost
table.
The test for optimal assignment has been applied to our present table and
is shown in Table 11-15. It requires only two lines (row C and column X) to
cover all the zero squares. Therefore, as there are three rows, an optimal
assignment is not possible.
Step 3: Revise the total opportunity-cost table If an optimal assignment is
not feasible, we must. modify the tota-opportunity-cost table by including
some assignment not in the rows and columns coyered by the lines. Of course,
that assignment with’ the least opportunity cost is chosen; in our problem,
this would be the assignment of job B to machine Y with an opportunity cost.
of 1. In other words we would like to change the opportunity cost for this
assignment from I to zero.
‘The proceduse-tor-accomplishing this ask is as follows: (a) select the
smallest number in the table not covered by a straight Tine and subtract this
Sree from al mummbers not covered Br-avanaight Tine, and (6) ade this
jumbers [ying at the intersection of any two lines.
The revised total-opportunity-cost table and computations of parts @ and b
‘of step 3 are shown in Table 11-16. :
‘The test for optimal assignment described in step 2 is applied again to the
revised table. This is shown in Table 11-17.
Machine TABLE 11-16
Rewsed epportaiycost table for Kelum Madina Sha problem
As the minimum number of lines necessary to cover all zeros is three, and
as this number is equal to the number of rows, an optimal assignment can
be made. In this case the optimal assignments are ‘A to X, B to Y, and C to
Z. In larger problems, however, the assignments may not be readily apparent
and we must resort to a more systematic procedure. The first step isto select,
row or colusmn in which there is only one zero square. The first assignment
is made to that zero square. Lines are then drawn through the column and
row in which the zero square is located: From the remaining rows and
columns we again select a row or column in which there is only one zero cell.
Another assignment is made, and lines are drawn through the respective row
and column. The procedure is repeated until a complete assignment has
been made. The assignment sequence using this procedure in our problem
is shown in Figure 11-35.
To calculate the total cost of these assignments for Kellum, we must go
back to the original cost table. The computation of total cost is as follows:
BLE
Test for optimal 524 in
CHAPTER 11
Ficure 11.35
Assignment
sequence.
SUMMARIZING THE
ASSIGNMENT METHOD .
OTHER APPLICATIONS
‘OF THE ASSIGNMENT
‘METHOD
ice cle Basa § — yuPncd Muay
XY? KEY 2 xyz
eer he A A
B 0 0 6 8 o%6 8
2820. -0 c 8 0 0 c
)
‘SUMMARY OF THE ASSIGNMENT METHOD
1 Determine the opportunity-cost table,
a, Subtract the lowest entry in each column of the given cost table from
“Yall entries in that column,»
b, Subtract the lowest entry in each row of the table obtained in part a
from all numbers in that row.
2 Determine whether an optimal assignment can be made. The procedure is to
draw straight lines (vertically and horizontally) through the total-opportunity-
cost table in such a manner as to minimize the number of lines necessary to
cover all zero squares. An optimal assignment can be made when'the number
of lines equals the number of rows. If the number of lines drawn is fewer
than the number of rows, ari optimal assignment cannot be made and the
problem is not solved.
3. Revise the total opportunity-cost table.
a. Select the smallest number in the table not covered by a straight line
and subtract this number from-all-numbers not covered by a straight
line. :
b, Add this same number to the numbers lying at the intersection of
any two lines. Go back to step 2.
The assignment method has been applied successfully to a number of
situations other than the Kellum job-machine problem we have used as an
illustration here. This approach has produced optimal assignments of per-
sonnel to job situations requiring specialized talents. Included in successful
applications of the assignment method are the assignments of selling personnél
to territories, instructois to specialized learning situations, and auditors to
client accounts. In order to apply this method successfully, management must
be able to determine cost data or other effectiveness measues like the costs
in Table 11-12. B Solving maximization problems
the transportation 3
and assignment methods en Hee
Both the transportation and assignment methods are used to solve problems
which exhibit certain characteristics. The term transportation, for example,
implies a generic class of problems in which total supply equals total demand.
However, this does not mean that a particular problem must literally be
described as a transportation system having supplies and demands, nor does
it imply that the objective must be to minimize total costs. In many cases, we
> might consider using either the transportation method or the assignment
method to solve problems whose objective is to maximize some function such
as total profit. The procedure used to solve a maximization problem is almost
identical to that used for a minimization problem. You may recall that with
the simplex method, the only difference between solving the two types of
problems was the rule for deciding which variable should enter the solution
at each iteration. If our objective is to maximize profit, we select the variable
having the largest positive C, — Z; value and continue to iterate in this
fashion until all C; — Z, values are either zero or negative. For minimization
problems, we select the variable having the largest negative Cj — Z; value
and continue iterating until all C, = Z; vahes are either. zeto or positive. We
will now describe the procedure for solving transportation and assignment
type problems when our objective is maximization.
| TRANSPORTATION METHOD FOR
MAXIMIZATION PROBLEM:
Dave Danesh is Vice President for marketing with the Monarch Company.
Monarch is planning to expand its sales of computer software into three new
territories—Arizona, New Mexico, and Texas. It has been determined that
20, 15, and 30 salespersons will be required to service each of the three areas,
respectively. The company recently hired 65 new salespersons to cover these
areas, and based on their experience and prior sales performance, the new
hires have been classified as Type A, B, or C salespersons. Depending upon
the regions to which each of the three types are assigned, Monarch estimates
the following annual revenues per salesperson:
Dave wishes to determine how many salespersons of each type to assign to
the three regions so that total annual revenues will be maximized. ® FIGURE 11-35,
Northwest corner
initial solution and R,
and K, values.
TABLE 11-18
Evaluation of unused
‘squares in the
initial solution
To ‘ sons
Aizona New Mexico’ Texas’ SUORTEE
100 120 =)
Ay=0 A © 3 24
%
bi Ky = 100 Ky = 120 Ky = 140
|
Salespersons
required
Let us begin by developing the northwest corner solution. This is shown
in Figure 11-36. The first step of the MODI method, where all R, and K,
values are computed, is identical for our maximization problem as it is for
minimization problems. These computed R, and X, valuesare shown in Figure
11-36. Now we proceed to step 2 of the MODI method, where we compute
improvement indices for all unused squares. This step is also identical to that
for a minimization problem. Table 11-18 summarizes the step 2 calculations.
Now we go to step 3 of the MODI procedure.
You may recall that when solving a minimization problem, we decided at
step 8 to select the unused square having the largest negative improvement
index. For our maximization problem, we do just the opposite and select the
unused square having the largest positive improvemeint index. Since we are
seeking the largest total revenue, by selecting either unused square 21 or 31
where improvement indices are both +4, revenues can increase by $4000 for
Improvement
index each type B salesperson we assign to Arizona or for each type C salesperson
we assign to Arizona. Let us arbitrarily select one of these unused squares,
21, and find the closest path into square 21 just as we did in solving 2
minimization problem. This path is square 21(+) to 11(—) to 12(+) to 22(—)
and back to square 21,-resulting in a shift of 11 salespersons into square 21,
leaving 9 in square 11, 15 in square 12, and none in our new unused square
22. Our new solution is shown in igure 11-37, The revised R; and K; values
computed in step 1 of the MODI procedure are also shown in Figure 11-37.
The improvement indices for the unused squares in our new solution are
summarized in Table 11-19. Upon inspection of Table 11-19, you should
note that our new solution is optimal, because all the improvement indices
are either zero or negative. The presence of a.zero improvement index for
unused square 31 indicates alternative optimal solutions. Two of these optimal
solutions are summarized in Table 11-20.
TARE 1119
Evaluation of unused
squares for the
optimal solution 828
CHAPTER 11
TARE 1-20
‘Two optimal. solutions
for the Monarch
Company problem
When Dave Danesh discovered there were alternative optimal solutions to
his allocation problem, he was extremely pleased. Being an astute manager,
he recognizes the benefits of locating his salespersons into territories where
they have personal preferences, These benefits manifest themselves in the
form of higher employee morale, higher retention of the sales staff, and
improved job performance. Alternative solutions allow Dave much more
flexibility in satisfying the preferences of his sales personnel while still meeting
the sales objectives of the Monarch Company.
Salesperson Number Annual
pe Tertitory assigned revenue
‘Arizona 9 $ 900,000
A New Mexico 15 1,800,000
B ‘Arizona 11 ‘990,000
B Texas 16 2,016,000
c Texas 14 41,680,000 a
f : Total $7,386,000 og
Number Annual TS
typ Tertitory signed revenue
A : ‘Arizona 9 $ 900,000
A New Mexico 15” 1,800,000
8 Texas 2 3,402,000
c ‘Arizona ees 924,000
c Texas 3 360,000
Total $7,386,000"
ASSIGNMENT METHOD FOR
MAXIMIZATION PROBLEMS:
Heidi Kurtz manages the Jamesville Car Rental Agency. This year, she plans
to purchase five new automobiles to replace five older vehicles. The older
vehicles are to be sold at auction. Heidi has solicited bids from five individuals,
each of whom wishes to purchase only one vehicle but has agreed to make a
sealed bid on each of the five. The bids are as follows:
. t <2. ~ Automobile i
Buyer Ford Dodge Buick ~. Volkswagen _Toyota
Amy $3,000. - $2600 $3,300 $2,600, $3,100
Bert 3,500- “9,000 2800 2,800 3,300
Carl 2,800 2,900 3,900 2,300 3,600
j 3,900 3,100 3,400. 2,900
{ 200. 500, 2900
3,600
so that each of them can purchase one-vehicle while the total of the five
accepted bids is amaximiem : Heidi's maximization problem is solved with the assignment method exactly
the same way as a minimization problem, except for one important difference.
We first need to convert each of the bids into a regret value, This is done in
the same manner as we did in Chaper .4 with decision-making under
uncertainty. Looking down the column for Ford, we see that the highest bid
is $3,500 from Bert. We develop the regret values for the Ford column‘by-
subtracting each of the five bids in turn from $3,500. Following this same
procedure for the other four vehicles, we develop the full set of regret values
shown in Table 11-21. Our objective in m: ing the total of the accepted
bids will now be met il ret. Consequently, we can
problem shown in Table 11-21°as a minimization
problem using the assignment method. All the steps to the procedure are
identical from this point on.
‘The optimal solution to the problem is shown in Figure 11-38. The
calculations for the total bid returns to the Jamesville Car Rental Agency are
summarized in Table 11-22.
6 Using the computer to solve
assignment and transportation problems
‘Lhe transportation and assignment problems are particularly easy to solve
by hand since they don't require anything more complicated than addition
and subtraction. However, even these methods become tedious if’ you have
to solve a large problem by hand. Let's look at the output from some -
microcomputer implementations of these methods. The: programs we used
Tee 1.21
Regret values for
automabite bids CHAPTER 11
TABLE 22
Optimal solution to
the Jamesville Car
Rental Agency
problem
Buyer Bid accepted Bid price
Amy Volkswagen $ 2,600
Bert Ford 3,500
Carl Buick _ 3,900 é
Dolly Toyota 3,500"
Edgar Dodge 3,500
Total $17,000
were written by Warren J. Erikson and Owen P. Hall, Jr.! The programs
prompt the user for all the input data and are quite simple to use.
In Figure 11-39 we have the computer solution to the Kellum Machine
Shop assignment problem. Of course, it’s the same as the solution we got by
hand on pages 520-523,
Figure 11-40 shows the solution to the Bass Gravel Company problem
which we solved by hand on pages 487 to 510. Compare Figure 11-40 with
the optimal solution we got in Figure 11-21.
* Warren J. Erikson and Owen P. Hall, J., Computer Models for Management Science (Reading,
‘MA: Addison-Wesley Publishing Company, 1983).
JX HEEB E
*
* ASSIGNMENT MODEL *
*
*
FEE III I
ANALYSIS «
*
* RESULTS #«
#* INFORMATION ENTERED **
NUMBER OF ROW!
NUMBER OF COLS:
ROW 1
KOW 2
ROW 3.
URE 11-39
22 19 17
ROW ASSIGNMENTS
3
3
PAYOFFS Qe A
2822 Stes, 30 Z Zo-- -- A
1s 20 24 MINIMUM TOTAL PAYOFF = 62
** END OF ANALYSIS #* -
‘omputer solution to Kellum Machine Shop assignment problem. PCP REAR ERED EDR E RRR ERE RRR 331
> * eee
* TRANSPORTATION ANALYSIS * ASSOBET PORES
* : * 4 5
JUHI HE EEC OBO RER EEA Oe
»* INFORMATION ENTERED ** #* RESULTS #*
NUMBER OF SOURCE ROWS: OPTIMAL SHIPPING SCHEDULE
NUMBER OF DESTINOTION COLUMNS: 3
PROBLEM TYPE: MINIMIZATION
a o 56 0
PAYOFF PER UNTT : UNITS
AVAILABLE.
at ° Al
4 8 8 Sé -
3 Ab 9
16 16 82
TOTAL PAYOFF: 2744
38 16 24 77 «4 END OF ANALYSISn¢
UMS NEEDED
72 fon Tian
FIGURE 11-40
Computer solution to Bass Gravel Company transportation problem.
7 Glossary a
‘Assignment problem A special case of the transportation problem in which the
number of columns equals the number of rows and in which in the optimal solution
there will be one and only one assignment in a given row or column of the assignment
table.
Balanced condition The condition when total demand is equal to total supply.
Degeneracy A condition in the transportation problem when the number of stone
squares does not equal the number of rim requirements — 1.
Destination A point of demand in a transportation problem.
Flood’s technique Another name given to the assignment method.
‘Hungarian method of assignment Another name given to the assignment method.
Improvement index The net cliange in cost occasioned by a one-unit change in the
quantity shipped. e . 4
Job-opportunity costs Differences in cost between the best possible assignments of
Job to machine and the ones chosen (column differences). ox Machine-opportuaity costs Differences in cost between the best possible assignment
SRE of machines to jobs and the ones chosen (row differences).
OUPTER 11
5
