Hence, the transportation cost of the optimum schedule is ce ADO = 360+ 50x3+20%9 43% 80-45 x A= 750 +54 = 750 since A 2.2. ASSIGNMENT PROBLEMS 2.2.1. Introduction A problem in which n different facilities are assigned to n different tasks, such a problem is known as an assignment problem. For example, if there is availability of three men and there are three jobs to be done where each man have capability of doing any job but because of individual quality variation, it takes different time amount for each of them to cary out each job. Here the problem is how to bring about the assignment of men to the jobs such that total time spent on jobs can be minimised. Assignment ‘model is basically a special type of linear programming in ‘which the main objective is to bring about assignment of a number of origins to an equal destination number s0 as to ‘maximise profit or minimise cost. A one-to-one basis needs is o be followed while assigning values. “Assignment Problem is the technique of selecting the best possible assignment of tasks from a number of alternatives.” Assignment problems are associated with matching of objects in two distinct set or bringing out optimal pairing. For example, in 2 children’s garment sales depot, there ‘ae four sales counter and four salesmen. Now the problem is how assignment of salesmen should be done to the ‘counters in such a manner that the total service time is minimised altogether. 2.2.2. Formulation of Assignment itectiveness (in terms of time, Profit, cost te.) of ea factity (resource) for each job (activity), the problem is say snment of each resource to one and only one job (Gecivity) such that there is optimisation of given effectiveness measure, For this probiem, the data matrix is shown in table 23, Table 217 c Resources | Supply workers) | Je [ Jaen Je Wifey} eee [1 We [en | eee | 1 We | eur [ea em [ Demand {1 [1.1 | It is observed from the table that the data matrix looks exactly like the transportation cost matrix. Only exception being availability (or supply) of each resource and tte demand is taken to be one at each destinations. The fat that lies behind this is assignment on a one-to-one basis. * Let xy denote the assignment of facility i to job j such tht 1 if facilityisassigned to job j 4° 0 otherwisepoten ben Mad Mole 3) pu the mathematical mode of he aa maint ienment problem vine Z= 3. Sy anette constants $j «1 forall source avait) $i = borat cy eiremen) ot tO fra and ee eset Ne is oT aig of CURE a si fiscear amie ove it tht te assignment problem 1g sf tron poten pening seo carci as is aoe sgue mai, nd ‘Toecetcimal problem solution would be. always 2) Moree 9 ati given cost mates column oe wayly one asignment wil be here 223. Applications of Assignment Model ‘Rgament model possess several applications, Some of Senae slows: sigan oF opaion tc. 2 ts alocston fr pia pcan. 2 Acre gna! dierent sales aes, 3) Eagle's igen machines. 2. Fptaenes oftacer and jects. 224. Methods of Solution of ‘Assignment Problems ‘aang fur meiods ae widely wed for solving an ‘imme prblen: Eitan Metiot: Anog he gen sous tare mot ce) an acs kel ee ae a a ere samen Se it ting Bie mol Now at ota weed bang sun ont and cee pet ne f Stn) ce, sane ‘Sun coternnmam psi pose! eo ‘Tame gate, tc te at lie opin Sina he pin: Gem te #1 {ta roe tipaments «poem wi 8 fa Toe tape as poem oth [roa so oel newl f 312) Sgnee onerous a Genie na ee mana ean aif Hace Enmcrce med app sional 2 Simpler Metal Sinpex mao can be el fr ‘gt spin pen hee Eeeted ar ermine wt Oct Se nivel any ty pt Schad ln he gene nahonatla of ‘Senet pen, tient ew moro fe se: 2n equates and n x n decision. For example, to solves prob with wskersobs, there wil be 10 ules and 25 decision varbles which are Bar 10 solve manually ‘Transportation Method: Asigament problem is [known 1 bea apecileateof transportation problem and ths it can be solved by the ws of transportation methods, However, fora general asigent probe ‘very basi fen soltion having a uae pay It of erdern mast hive assignments m+ 8 n= Tn dn 1 But any sltion cannot possess ‘more than nasigment de wo special structure of the problem. Thus tere inherent degeneration of theaspnent problem So, for removing the degeneracy, dummy allocation (of (a= 1) number is required 30 a8 0 proced with ‘sch tanspration method. Tus, it can be eval that depenrcy problem teach slation makes the ‘mabod of transport iefcest computationally for assignment problem solaion. 4) Hongarian Assignment Method (HAM: obserable tht none of the above mentioned tee ‘working meiods to solve an asignent problem is ffcen. A metod specially designed to handle ‘signmentpoblems an efficient way thats based ‘onthe opportnity co concept, known as Hangarian ‘Asignment Method. “This HAM method motes successively the columns and rows of the effetiveness max uni the is hscrvance of at east ne zero component in each cnn and yw sot complete assignment can be nade coespondng to these 2205. When applied The orginal ellectveness mats, he complete ssigment comes ou (0 bean optinal assignment in ‘wich the esting total efletveness comes ou to be ‘minimal Thee wl always be convergence of this eho io optimal asignment ante ps which te tecoially eed ak assignment algorithm. 8 225, Hungarian Method / Flood Techniques to Solve Assignment Problems 'A Hungarian Assignment Method (HAM) method Specialy designed to handle asigament problems is an ‘Fiient vay tas based onthe oppatnity cost concep ‘This HAM method mais sesesivey the columns and rows ofthe efectivenes matrix wl there is observance ‘tea ve tee componen in each column apd 1OW 50 that complet esignment canbe mae coresponding (0 those zen. When applied tothe orginal effectiveness Imai he compete assignment comes out 10 be an primal asigameat nv which the resulting tt Heciveoess comes cut to be minimal. There will be Shays convergence of this method to. optimal ‘signee infinite steps Which are tecmiallytemmed 3s ‘ssignment algorithmFollowing re the varius tps which re involved it 2 SEIS met ich ti aa sco SREB I 2 (gure sigan got a Ria Ta cna i THEO vod in beacon fie shmgente vcs Dea lon ‘ae x 3p gue 23: ow Gh rh Hogan Mat ‘Step 1: Row Reduction: Lowest cos in the row ie subtracted fom each om ‘Step 2: Column Reduction: Lowes ostin the soln ‘beac rom each columa of tis new cot mt ‘Step 3: Minimum number of vertical and herizeatal lines) ‘ae drawn so aso necessarily cover ll eros atleast once IWinan a xn matin, aisimum numberof ines is then forthe given assigament problem, one hss an optimal solution coresponding to aS of independent 2 set of zeros whee no two 208 inthe set OC the ‘Same ror clu, ‘Step 4: Inthe case when minimum aumter of lines inn 1 matrix i es than, ten smallest nmber ie selected hich doesnot ave aline trough i ‘Slep 5: Tis number is then subircted from all elements that are covered by lines and added to the elements which ‘are located at the intersection of wo lines. Step @) is applied again to find a solution among the new set of ‘eros Incase, no esl ound, his step i repeated and of step (3) and (4) is continued uni ve fs ofthe assignment problem. Step & Optimality Criterion: The jb assignness = made withthe help of given optimal ston sn by the "zero clement. The procedure fr ts fellows 3. i) Arow ie semen, sich is consnng el tes Compt at Sas ‘assigned to its comresponding person. All Zcne 2 colt ing te men ac ‘if any. This indicates the fact that there is 00 % salty of parila pron Sip amped rae sch os sve seo in tht The sume oe Peto iat i ret no ening nly one “rar cent ta ‘hich re ilemon, ay. ‘n-case when there is no coluran or row with él ‘zero’ clement left in them, then arbitrarily ‘of row/columa is made and one of the job wAllocation Problems Models (Module 2) is chosen to make assignment. Now the emai eros ae crossed in the row and coleman with res to which we have done the stsignment iv) Repeat steps (10 Gi) until we have dove all assignments. ¥), Total cost is determined with reference tthe origi cost abe. Example 29: Solve the following asigament prob using Hungarian Method. Th Men [ATR] CTD 1 fasta [soto 2 [arf fess 3 feos [aster far fas toss] Solution: Applying Hungarian Method, we have th following steps: Step 1) Row Reduction: Select the lowest element © tach row and subtract tom the oer clement wae = oi et is eee Cerel ‘Column Reduction: Sle Step?) toh column and sb ‘SFacotr ofthat column as follows the lowest clement of rom the other ttt Sow we have 1 de ini yaw Lines No that cover all Step 3) De sin such umber of Hes eas 10 fiat cover those eros, Por this of fms that conta Exim 2S, _ oval mai ce pe “aw pe otal umber of tine div is which are ‘Ato eowedcolumns (0 = 4), 30 the solution i “The asignment canbe made by ‘ioe syntol() 8 shown in table 2.18 ‘Toble21 Asigoment of Tasks Tink sen {ATT a 0 srs perp itt