[61 INTRODUCTION In the previous chapter, we discussed about solution to the transportation 1 Know an assignment problem. Now we consider another type of special linear programming 7 bl 7 problem problem, called the assignment problem. There are many situations where the assignment of people, machines, and so on may be called for. Assignment of workers to machines, clerks to various checkout counters, salesmen to different sales areas and service crews to different districts, are typical examples of these, Assignment is a problem because people possess varying abilities for performing different jobs and, therefore, the costs of performing those jobs by different people are different. Obviously, if all persons could do a job in the same time or at the same cost then it would not matter who among them has been assigned the job. Thus, in an assignment problem, the question is how the assignments should be made in order that the total cost involved is minimised (or the total value is maximised when pay-offs are given in terms of, say, profits) Scanned with CamScanner ‘Scanned with CamScanner6.1.4 Hungarian Assignment Method (HAM) A method, designed specially to handle the assignment problems in an efficient way, called the Hungarian Assignment Method | is available, which is based on the concept of opportunity cost. It is shown schematically in Figure 6.1 and is discussed here. To begin with, it may be noted that the ‘Hungarian Assignment Method (HAM) Scanned with CamScanner ‘Scanned with CamScanneree eee convertion the rig ent Pblen «| uses the fact that if we add or rae any Se ameiel entails converting the original eost table ng 7 | not change and remains oa Rekeed Cost Tables or Opportunity Cost Tables, Consisting of only, rm | of equivalent cost tes, sail an optimal solution is obtained. The pte! scltion that i derive a, 1 positive pererca tat reduced cost table is also the optimal solution tothe original probe with the help o! s - es) Write the problem | in tabular form problem, either (i) by changing Isit Yes | the signs of the elements of ‘@ maximisation the table or by subtracting all problem? the values from the largest value. ‘Obtain reduced cost tables. (@) Subtract from all entries in each ‘tow the least value in the row. (ii) From this table, subtract from all entries in each column the ‘east value in the column. Improve the solution. For this: (Select the minimum of the uncovered (by tines) coll values. (ii) Subtract value from all Uncovered cell values, (il) Add this value to the calls lying on tho intersection of any pair of lines. (Wy) Leave the call values covered by only one tina undisturbed, Make assigninents on oni 10-0ne match 's Considering zeros in rowslcolumng. Scanned with CamScanner ‘Scanned with CamScannerical balanced assignment problem in fora pe objective function ofthe minim volving.a certain numberof persons and an equal number of jobs, ed Hon nature, the method is applied as listed in the following steps. step 1 Locate the smallest cost element in each row of the & SteP chelement in that row. AS a result, there tke Reduced Cost Table, step 2 In te reduced cost table obvained, consider each co! Syma the smallest value from every other entry in the column, fealeast one zero in each of the rows and columns of the secon i st table, Now subtract thi Hest clement shall be at least one zero in each row. of this new table, called Hunn and locate the smallest clement in it. Asa consequence of this action, there would nd reduced cost table, sep Draw the minimum number of horizontal and vertical lines sverall he "zero" elements, Ifthe number of lines drawn is equal (not the diagonal ones) that are required c to n (the number of rows/columns) the scion is optimal, and proceed to step 6, If the number of lines drawn is smaller than n, go to step 4, Siep4 Ifthe number of lines covering all zeros is smaller than n, it has the implication that the number of zeasand their locations do not permit us to obtain the optimal solution. Thus, there is a need to create more 708. Now, to create additional zero(s) we subtract a constant, equal to the minimum uncovered value in the isced cost table, from every value in the table. However, this would cause some of the covered ccll valucs to hecome negative. Now, in order not to have any negative value, we add this constant back to the cost elements ofeach of the rows and columns that are covered. Evidently, the value in any cell which is covered both by thorizontal and a vertical line (that is to say, a cell lying at the intersection of lines) would get enhanced by ‘ion due to the dual addition involved. The operative part of this step is stated now. i¢ smallest uncovered (by the lines) cost element. Subtract this element from all uncovered clements ‘cluding itself and add this element to each value located at the intersection of any two lines. The cost elements ‘trough which only one line passes remain unaltered. Step 5 Repeat steps 3 and 4 until an optimal solution is obtained. Step 6 Given the optimal solution, make the job assignments as indicated by the ‘zero’ elements. This is érne as follows: (@) Locate e row which contains only one ‘zero’ element. Assign the job corresponding to this element to its corresponding person, Cross out the zeros, if any, in the column corresponding to the element, Which is indicative of the fact that the particular job and person are no more available. (0) Repeat (a) for each of such rows which contain only one zero. Similarly, perform the in respect of each column containing only one ‘zero’ element, crossing out the zero(s), tow in which the element lies. (©) Ifthere is no row or column with only a single ‘7er0" and choose one of the jobs (or persons) and make the a the column and row in respect of which the assignme ( Repeat steps (a) through (c) until all uss (©) Determine the total cost with referen me operation any, in the Jement lef, then select a row/column a assignment, Now cross the remaining ‘he Hunganan eripmmont Method s an'elficiemt meiod of solving assigrunent pro bles. Hnvolves developing o nent Mel in every row and every 3 ‘ ’ Ives three steps of (I) obtaining zeros my i nee tons ‘covering all zeras with a minimum number of horizontal/ erica tinee ash a colements can be made; and (i) making assignments at zeros only such that feck whether as: TO aa gcneck whether as ore ceignment made Int, Modifications are needed the numberof ines Tow and each column has asi i ting all zeros is smaller than n, order of the sauare Ma\t Scanned with CamScanner ‘Scanned with CamScannerExample 6.3 Solve tho assignmont problam ivan In Examplo 6.1 for optimal solution us information Is raproduced in Tablo 6.7. £6.7 Time Taken (in minutes) by four Workers: Job jorker a agg eet PN Ose a A B c Db 1 as 40 51 o > 7 42 63 55 3 49 52 48 64 4 4 45 60 $5 The solution to this problem is given here in a step-wise manner. Step 1 Theminimum value of each row is subtracted from all elements in the row. Itis shown in the reduel cost table, also called Opportunity Cost Table, given in Table 6.8. TABLE 6.8 Reduced Cost Table 1 Worker 2 fob Step 2 Obviously, For each column of this table, the minimum the columns thi column values would char value is subtracted from all the other values. main unaffected by this operation. Here only the mt Contain a zero would rei nge. Table 6.9 shows this, TABLE6.9 Reduced Cost Table 2 Worker | ing Hay The | Scanned with CamScanner ‘Scanned with CamScannerirst cover step 8 Draw the minimum number of lines covering all zeros. As a general rule, we sould i elite those rows/columns which contain a larger number of zeros, Table 6.9 is reproduced in Table 6.. fines ae drawn. TABLE 6.10 Reduced Cost Table 3 Job Worker i Ne 4 B Cc D 1 $ i 14 2 4} 4}. ——0- 3 1 f 3 4 —0- oe Step 4 Since the number of lines drawn is equal to 4 (=), the optimal solution is obtained. The assignments are made after scanning the rows and columns for unit zeros, Assignments made are shown with squares, as shown in Table 6.11 TABLE 6.11 Assignment of Jobs a Job 4 ‘BB c D 1 5 @ i 14 2 15 K 21 ag 3 1 4 o 3 4 o 4 19 1 ‘sSienments are made in the following order. Rows 1, 3 and 4 contain only one zero each, So assign 1-B, 3-C, and 4-4. Since worker 1 has been assigned job B, we cross the zero in the second column of the second ‘ow. After making these assignments, only worker 2 and job D are left for assignment. The final pattern of cpt imetts is 1-8, 2-D, 3-C and 4-4, involving a total time of 40 + 55 + 48+ 41 = 184 minutes. This the “Spial soluion to the problem—the same as obtained earlier by enumeration and transportation, methods, ‘ample 6.4 Using the following cost matrix, determine {a) optimal job assignment and (b) the cost of @ssignments, Job ‘Machinist a a ey w Scanned with CamScanner ‘Scanned with CamScannerIteration 1 Obtain row reductions. TABLE 6.12 Reduced Cost Table 1 3 rr or ini ines to cover all zeros, Iteration 2 Obtain column reductions and draw the minimum number of lines 0s, TABLE 6.13 Reduced Cost Table 2 Machinist Since the number of lines covering all zeros is less than the hy least ofthe uncovered cell values is 2. This ven Would be subtracted from each of ore luc Jying at the intersection of lines (Corresponding to cells 4-4, D-4, A-5 a the mew table would appear as shown ty Table 6.14, Iteration 3 The optimal jsignments can be made as the least umber of lines covering all a Table 6.14 equals 5. Considering rows nts can be made in the following ify Table 6.0. | number of, columns/rows, we modify Table | Kecordingly, i | G) Sclect the second row, Assign | Gi) Consider row 4, Assign machi Cancel the zero at cell E-1 3 (iii) Since there isa single zero in ‘machinist Eto job 3 and eross out the zero at“ 4 (iv) There being only a single zo i | inst Teh i i — chins andjebsnce 0 Tefl in each of the first and third rows, we assign job 2 to mé The total cost associated wi th the optimal machinist-job assign is3+2+44+349=2], 3 4 nment pattern 4-2, B-4, C-5, D-| a ‘Scanned with CamScanner ‘Scanned with CamScannerTABLE 6.14 Reduced Cost Table 3 Machinist | s.2_SOME SPECIAL CASES 6.2.1 Unbalanced Assignment Problems ‘The Hungarian method of solving an assignment problem requires that r the number of columns should be equal to the number of rows. When LO 4 Discuss unbalanced they are equal, the problem is a balanced problem, and when not, it is 2nd constrained assignment called an unbalanced problem. Thus, when there are five workers and four Problems machines, or when there are four workers and six machines, for instance, \we have unbalanced situations in which one-to-one match is not possible. In case the machines are in excess, the excess machine(s) would remain idle and so is the case when men are in excess—the number of excess people would not get an assignment. In such situations, dummy column(s)/row(s), whichever is smaller in number, are inserted with zeros as the cost elements. For example, when the given cost matrix is of the dimension 4 x 5, a dummy row would be included. In each column in respect of this row, a ‘zero’ would be placed, After this operation of introducing dummy columns/rows, the problem is solved in the usual manner. 6.2.2 Constrained Assignment Problems Sometimes a worker cannot perform a certain job or is not to be assigned a particular job. To cope with this Situation, the cost of performing that job by such person is taken to be extremely large (which is written as M). Then the solution to the assignment problem proceeds in the manner discussed earlier. The effect of assigning Probibitive cost to such person-job combinations is that they do not figure in the final solution, eam ss You are given the information about the cost of performing different jobs by different persons. The job-person marking x indicates that the individual involved cannot perform the particular job. Using this 'nformation, state (i) the optimal assignment of jobs, and (i) the cost of such assignment. Job | eae qi h 4 te ap Pi 27 18 x 20 21 P, 34 24 2 12 7 “Py 20 17 20 x 16 P 22 28 20 16 27, Scanned with CamScanner ‘Scanned with CamScanner[Bn Rann cdg. the pertain te ondly panting M_yertse to" jee 2 Ty & Py = Types 4 have — = | 3s Ty fs 20 2) 2 DY yu \7 20° NM ir x0 6 uw | ° ° ° Sell Ss is eas Py 4. o mM. ae 3 a {9 ea a oS Pa 4 ! 4 M oO | Py 6 jo 4 Oo WW (pS Pie oO ° ° ° 9 - espa)" 5 Step Zs, a ; i a a | Pa 1 Ps 0. ») oF Scanned with CamScanner ‘Scanned with CamScanner@ rH ev lt DAT Step 4] Montane 2 hamweyt = 4. Subyhracing A Airs uiscoered 20s vote fe addline | Jat the clowhle Comered 0B nertb We hae thot =i J; Sy Sy ! RA 5S Jol ™ a3 Pa IS ib. 5 jo| 5s Py eg fp fe ah] © Py 2 ja Jol Ul © Pr fo} f - 4 0 @® © . Peabo Tbs Tine ! Z - 18 = Ty hes . | 3 Tic lé - ¥ Ty 209 Dummy) 5” x, a Scanned with CamScanner ‘Scanned with CamScanner6.2.3 Unique vs Multiple Optimal Solutions Inthe process of making assignments, it was stated earlier that we select arow/column with only a a situation ngle zero to make an assignment. However, y arise wherein the various rows and columns, where ; ‘et to be done, have all multiple zeros, In such cases, we ‘getmultiple optimal solutions to the given problem. In any of the problems LOS Compare unique and multiple optimal solutions [Link] assignment problem discussed so far. we have not experienced such a situation. Hence, each one of them has had a unique optimal solution. When a problem has a unique optimal solution, it means that no other solution to the problem exists which yields the same objective function value (cost, time, profit, etc.) as the one obtained from the optimal solution derived. On thé other hand, in a problem with multiple optimal solutions, there exist more than one solution which are all optimal and equally attractive. Consider the following example. J ple 6.6 Solve the following assignment problem and obtain the minimum cost at which all the jobs can be performed. Job (Cost in‘ 007) "| Worker 1 2 3 4 5 A 25 18 32 20 2 8 34 25 2 12 7 c 20 7 20 32 16 D 20 28 20 16 ar This problem is unbalanced since the number of jobs is 5 while the number of workers is 4. We first balance it by introducing a dummy worker £, as shown in Table 6.18. TABLE 6.18 Balancing the Assignment Problem Job Worker 1 2 3 4 5 4 25 18 32 20 a B 34 25 2 2 7 c 20 7 20 32 16 D 20 28 20 16 27 E 0 0 0 0 0 Step 1 Obtain reduced cost values by subtracting the minimum value in each row from every cell in the Tow. This is given in Table 6.19. Scanned with CamScanner ‘Scanned with CamScannerTABLE 6.19 Reduced Cost Table 1 Worker Since there is at least one zero in each row and column, we test it for optimality. Accordingly, lines are drawn | All zeros are covered by four lines, which is less than 5 (the order of the given matrix). Hence, we proceed tg improve the solution. The least uncovered value is 4. Subtracting from every uncovered value and adding to every value lying at the intersection of lines, we get the revised values as shown in Table 6.20. The solution given in Table 6.20 is optimal since the number of lines covering zeros matches with the order of the matrin. We can, therefore, proceed to make assignments. To begin with, since each of the columns as multiple zeros, we cannot start making assignments considering columns and have, therefore, to look through | rows. The first row has a single zero. Thus, we make assignment A-2 and cross out zero at £-2. Further the second and third rows have one zero each. We make assignments B-4 and C-5, and cross out zeros t D- and E-5. Now, both the rows left have two zeros each and so have both the columns. This indicates caistence of multiple optimal solutions. To obtain the solutions, we select zeros arbitrarily and proceed as discussed below. ~ | TABLE 6.20 Reduced Cost Table 2 (i) Select the zero at D- Job 1 are not availabl Evidently, J, make assignment and c1 ilable any more), Next, selecting the zero at £ (ii) Select the zero at D-3, make eflect of making same assignments: -3, make assignment and ze eae a atthe only zero lef at B-1, Obviously, ree Out zeros at D-1 and £-3, Next, make assign™ Place would lead to the same a, ng the ze zer0$ a D-3 and E-1 (as both, worker Da | | . inst uel 0 at £-1 for making assignment in the fi To conclude, the problem has two optim, © job 3, corresponding to the only ze70 al Solutions as given below, Scanned with CamScanner ‘Scanned with CamScannerSolution I (008) Solution 2 ru) Worker Job Cost Worker Job Cost 4 2 18 4 2 18 B 4 12 B 4 12 c 5 16 c 5 16 D 1 20 D 3 20 Tob left 3 Job left 1 Total 66 Total 66 Irihe course of making aseignments, if we land in a situation where each of the rows and columns lef ha multiple zeros, then the problem will have multiple optimal solutions. Otherwise the optimal solution obtaineg shall be unique. Scanned with CamScanner ‘Scanned with CamScanner| A_puticiter’s pms camabbeara typ Ute.” pieconumte haris Jor thelr ne ano S typinte 2 i jie re jp old nh. & girtan tote ty put £ “the Orne fort ta patd fer a p00 herb Crean opacities of an Scanned with CamScanner ‘Scanned with CamScannerhour - CO Nobr ro data. ——|_ Typist | Rate/ | Noo ot napon-typed or | No+ of. how per how | Popes A 5 Ia. 2 &, 144 g 6 WY — Q : ATS Z, C 3. BR > 4 10" S| Za L o_o Rs ee ous ov = — “< yy AY oven fob P, fle weodd Aol re. y on LDhews @ £5 | hows whieh Scanned with CamScanner ‘Scanned with CamScannerP GR >a a & 4 4 [ol | isl l x 1 ln 4 yA y 1 — fo} «#2. @ 2) 5 a : ® [ Seep ull Minienunn Chawrernt = |. | Subiro ceding this elnamp rat frown the | ant reno efome vith & _achoone ut | ete. tn terror dtng Podktn tse hae — | ae y ! - - ‘Scanned with CamScanner ‘Scanned with CamScanner| SepS] — Minivedan Doerner 7). _ Na hen or birnace, fring ba yk | Sep) thinivnisznn oforeent = | @ eo aD Apa. opi Wate , _ ae _potuck Ow “4 | Person Terba leat : Zoe fl T oe =| 8 =F, 64 € Q 66 . Des PR. 20 F E S 2 A F319 ~~ Scanned with CamScanner — ‘Scanned with CamScannerSecmad ‘Sctutlon, Typist Tabb. Coat: A T Is 8 R a 4 c S WM D P Bo + & 8 64 F344 CA Wie20 dme Ce hos token te triad for | i Attra torial popl. The Aetras oro vga Ai enon izes 2 hoor. Each FH = oypods were asbod to five Astle thelt ron, _| persis Oto trent, ldid mot List aff tho pve leeo aoe erg net hodoyed usta Ames a ‘Scanned with CamScanner ‘Scanned with CamScannerlout fo which Acoma At thet tho, tolod -prcforemee_ Aaenting, a trent The. ae notarwast tn a “boble. on a MorrK pone aP\y MN 303 Bol” 304 30) 305, | 302 Fern ullote ha. — adage ant Prabhat vps Step | My, my, MyM - Popp tM - 30x 9 o 4 ° | = Igo df MBM 304 0} A 1 - 305M 4 2 o MM es Scanned with CamScanner ‘Scanned with CamScanner—301 M 1 302 M, I 303 M ! __ 304 Me . 2 205 My 2 ! Moni mi rotén Cones at meme atta tt ong Fer. che pbdng }f3 pai valle wi mbt ‘ +p sits osnrovedl C j—partle rn , we a fannt_ the. anata t we. | ton Shfec bie. uth oy booxivnts ob Ov Catange ib teste ain by. Batre ting: HH Cech of the. 20eretat® the watt ye prem tre picts Aer, Wak tem the value. Barney. the, usrat bramediune 2s ‘Scanned with CamScanner ‘Scanned with CamScanner/ Example 6.7}. company plans to assign five salesmen to five districts in which it operates. Estimates of ‘wee, teuerise in thousends of rupees for each salesman in different districts are given in the following table. \s your opinion, whet should be the placement of the salesmen if the objective is to maximise the expected sa reverse} Expected Sales Data District Salesman Scanned with CamScanner ‘Scanned with CamScannertries in the ti Since it is a maximisation problem, we would fi be Tom the fone, which equals 19 here, The restltant My TABLE 6,21 Opportunity Loss Matrix Salesman F Dy, Ds D ; 1 13 sy 9 3 1 Sy 1 "7 13 20 5 Sy 0 4 8 ul : Se 0 5 i iS 1 6 2 Now we shall proceed as usual. Step 1 Subtract minimum value in each row from every value in the row. The resulting values are he in Table 6.22. TABLE 6.22 Reduced Cost Table 1 District Salesman De 7 7 a r 5 8 2 0 12 0 5S 0 16 12 19 4 Ss 0 14 8 i 4 Ss 19 3 0 5 5 Ss n 7 0 5 1 Step 2,3 Subtract minimum value in each column in Reduced Cost Table 1 from each value inthe ol Test for optimality by drawing lines to cover zeros. These are shown in Table 6.23. TABLE 6.23 Reduced Cost Table 2 District Salesman a a meat a Ss —— ; Sy Ss Sy Ss " wae ce the number of lines covering all zeros is fewer than n, we select the least uncovered cell equals 4. With this, we can modify the table as given in Table 6.24, Step 4, 5,6 Find improved solution. Test for optimality and make assignments. Scanned with CamScanner ‘Scanned with CamScannerTABLE 6.24 Reduced Cost Table 3 District Salesman: Dr Dd Dy Ds Ds s $30 $9 —t : 5; 9 10 10 x S t 8 4 2 fo S 2 + Se 5s L 3 ‘There are more than one optimal assignments possible in this case because of the existence of multiple zeros in different rows and columns. The assignments possible are S| — Da, S.— Dy, S3— Ds, Sy — Ds, Ss — Dg; oF S\ — D2, Sp— Ds, 83 — D, Sy— Ds, Ss — Dy; or $1 — Da, 8, — Ds, 83 - Di, St Da, Ss — Dy; or S — Dz, Sp — Dy, 83 — Ds, Sy — Dy, Ss - Dy. Each of these assignment patterns would lead to an expected aggregated sales equal to % 2,31, 000, Scanned with CamScanner ‘Scanned with CamScannerJone to-_be__asniganed te alta sales ltearLtiorfes . The roorntaly, poles TS eptimnasted Jer_eacin seller ne prcdentative fer_Aierorct Jaater tarridrrios [tn Lakhs of SF), are Brows — Sobes Ternitrrios Sales boro x x mw A 200 150 1710 220 g 160 120 150 14O c (10 195 (Yo 200 D [go 175 l6o 120 5 ge total peat bolos T ex” row tlh - 54 for contain Atabmns, babes Aoprvrtytat0re e. Crrnnt be. astrtened +o © robes seratiny Th ten tre etic) a digas poet Behodanle be i r te dute Hie _etect ma tote Bole: 6a food, ConaverKing the SpiSton rnartiwi & OK om Lote orSeimalbebon “Hbpe by pubiyache ently a snot vt “of the Givin wating frown 220° xz I TL av A 20 To 50 oO 6 60 Loo. To 8d Cc 30 25 230 20 D YO 4s 60 30 Scanned with CamScanner ‘Scanned with CamScannerPAGE pare BY HOTE BOOKS fi 8 c +s——_%——fo L's. © Db ~@——~fo} ——e—-8- © OR (ALkierwote Sot) x x me I. A B10 55 6 c L — 1 ‘Scanned with CamScanner ‘Scanned with CamScanner— Opten | | ___H Satesinan Ternidny __ A aoa 6 x | & fm D a Total A ae 220 g ac 150 - c ac 195 | > x - 180 Tetod wis Dy pateamen 6 dannot be. anstgrec te 4 teaAliow, TL (eptn2) tren ebtims | abme Ywroly. be: tochkepted= rtweut atserre, 1 eyYect en Zales + -- Bs ffttre penoterd dh art Capable of parting Gry of there Jowr produrtn. pA ELLIO Dag sti mee _fows OD bese 20 tiny ted fer _tunch » The ~ pl tnimactes f-the pif» Ve each af te pnkicth ada pdt tebaed + Scanned with CamScanner ‘Scanned with CamScanner—_—|+ 240 350 __aa_sop Bho SD 25D Bg (80 }50 200 240 300 226 1ES9) al Pe 3 IMM y Operate | Ca prods YSIS = ZO Be wate ef 1. prodiact A @ FB) ust tyogzh) Scanned with CamScanner ‘Scanned with CamScannerimpeen a ctodal 9 F2U0~ = To dotue tris problem, we mend to Commer 4 Ae. Preble Crt opportunity Leds wath |_ Ons. ou btre chins. it fac 450 - the ie Nigrent peg id get the. foiling . [acca = : as 8 és D : | ba + gto 15D RDS 150 i | a 40 ° 200 ‘15D L 3306 210 300 250 i “4 210 Iso 2s. 20 te i Steal A. & cj D . | ‘Ls 60 o aes oO ! | 2 40 “0 200 150 _ { 3 56 20 so ° = 4 60 3° 1s 120 i Step A 8 qc. Dp (Step3) I 4 25. 3 - 2 3M [ 150 Ve - i 2 0 RK 3) . Y 4 257 20 bh | ® © - i |] PrSn tnt 2fe wre wt = Ret nti - the ywotyix unt try deoant unt mened. - i wile we tans — ‘ ‘Scanned with CamScanner ‘Scanned with CamScanner‘Scanned with CamScanner