## I. INTRODUCTION One of the most significant applications of optimization theory is the Assignment Problem, where various tasks need to be distributed across components to be completed, such as spreding personnel to offices and drivers to buses, among other things. There have been numerous ways of exploring the best policy for assigning jobs to components. The Hungarian approach is the most frequently used method for determining the best assignment policy. The Hungarian Method was named by Kuhn (Kuhn, 1995) and was based in significant part on earlier work by two Hungarian mathematicians, Egervary and D. Konig. When the Hungarian approach is used to address an uneven assignment problem, the technique assigns the jobs to fake components that do not perform them (if the number of jobs is greater than the number of components). It seems impossible to leave jobs unfinished in real-world situations. As a result, rather than assigning extra work to dummy components, it is recommended to do each and every job that may be done by assigning multiple jobs to a single component. To tackle assignment problems, the Hungarian algorithm (Chen., 2011) (W. B. Lee, 1997) and specific heuristic algorithms (e.g., simulated annealing method (B. Li, 2002) ant colony algorithm (Y. Liang, 2005) (R. K. Yin, 2008) particle swarm algorithm (W. F. Tan, 2007) and genetic algorithm (S. Q. Tao, 2004). Heuristic approaches are frequently employed to solve problems with assignments of high complexity. However, because the search is conducted at random, it cannot guarantee that the optimal result will be obtained. The Hungarian algorithm is an algorithm with a mathematical foundation. The Hungarian algorithm is commonly used to tackle assignment problems because of its simplicity and ability to find the best solution without requiring validation - (X. Q. Hu, 2006) (M. J. Liu, 2013) (H. Z. Zhang, 2009) (L. W. Huang, 2007) (Y. Wang, 2005). - In (J. L. Du, 2010), an enhanced Hungarian algorithm, the "add zero row approach," was presented to handle the incomplete assignment problem based on a study of the standard Hungarian algorithm. The Hungarian method was first introduced by (T. M. Chang, 2004) and, it was used to solve a common assignment problem, such as a marriage assignment. (Ma., 2014) suggested a new method, the "difference method," for solving the non-standard assignment problem: "tasks more than the number of people." This method is more straightforward than the standard algorithm because it does not require using a new matrix to replace the original coefficient matrix at the beginning and instead solves the problems directly on the old coefficient matrix. (Qiu., 2013) suggested an enhanced Hungarian algorithm for studying multiple maintenance scheduling problems in hostile environments. A quick order reduction optimization approach based on the classical Hungarian algorithm was proposed (J. X. Ren, 2014) to increase the efficiency of the distribution of cloud computing activities. The order of the matrix is quickly lowered and, the computing efficiency is increased by deleting the matrix elements that are determined. Reference (R, 2014) used the Hungarian technique to investigate the dynamic power allocation of weapon-targets by changing it into an assignment issue. Furthermore, the traditional Hungarian algorithm has been used to tackle business and technical challenges in a variety of disciplines (P. Hahn, 1998) (Kuhn., 2012) (E. M. Loiola, 2007) (T. Tassa, 2008) (S. Promparmote, 2006) (M. H. Paul, 2013). - According to many authors, the unbalanced assignment problem has many solutions, all of which assume that all jobs are finished. Kumar (Kumar, 2006) came up with a fresh approach to address the problem of uneven assignments. The decision-maker can allocate several tasks to a single component using his methodology. The Lexi Search Approach, developed by Haragopal and Yadaiah (V. Yadaiah, 2016), is a more effective technique for dealing with imbalanced assignment problems that yield the same outcomes as Kumar (Kumar, 2006). In the same year, Kumar's (Kumar, 2006), Haragopal's and Yadaiah's (V. Yadaiah, 2016) methods were surpassed by an approach provided by Betts and Vasko (Vasko, 2016). ## II. MATHEMATICAL FORMULATION Consider the processing cost of the jth job on the ith component be Cij, where $i = 1,2, \ldots, m; j = 1,2, \ldots, n$. The challenge is to create an ideal work assignment method that ensures that every task is finished while keeping the overall cost of doing so as low as possible. Mathematical model of an unbalanced assignment problem can be expressed as, Minimize: $Z = \sum_{i=1}^{m} \sum_{j=1}^{n} C_{ij} X_{ij}$ Subject to constraints $$ \sum_{j=1}^{n} X_{ij} \geq 1,\,i=1,2,\dots,n $$ $$ \sum_{j=1}^{n} X_{ij} \geq 1,\,j=1,2,\dots,n $$ $$ X_{ij}=0\,or\,1 $$ ## III. PROPOSED ALGORITHM Think about the issue of distributing a group of "n" jobs. $\mathrm{J} = \mathrm{J}_1, \mathrm{J}_2, \ldots, \mathrm{J}_n$ to an execution set with "m" components. $\mathrm{C} = (\mathrm{C}_1, \mathrm{C}_2, \ldots, \mathrm{C}_m)$. $\mathrm{X}_{\mathrm{ij}}, \mathrm{i} = 1,2, \ldots, \mathrm{m}; \mathrm{j} = 1,2, \ldots, \mathrm{n} (\mathrm{n} \mid \mathrm{m})$, indicating that there are more tasks than components. In this case, n stands for columns and m for rows. Step-01: Enter the following values: m, n Step-02: Each column's lowest cost should be subtracted from the column it belongs. This process results in each column reducing the cost column by having at least a single zero. Step-03: Determine each row's lowest cost and then deduct it from the associated row. Step-04: Analyze the feasibility of doing an ideal task so that the smallest number of lines needed to cover each zero is calculated. If the number of lines and rows equals one, proceed to Step 7; if not, proceed to Step 5. Choose the minimum uncovered cost if the number of lines exceeds the number of rows. 1. Take the least exposed cost in the table and subtract it from each exposed cost. 2. The cost at each intersection point is added by those minimum cost. Step 06: If the case (the total number of lines and rows is equal) fails, then continue steps 04 and 05. To assign the work, look for a row with only one zero. Choose that zero and block the other zeros in the relevant columns (the same component can be performed on more than one job, but the same job cannot be assigned more than one component). Step-08: Assign the value with the lowest cost in the initial problem if there is a tie, that is, if any rows have two or more zeros. Step-09: Repeat steps 7 and 8 until all positions have been filled, that is, all jobs have been assigned to one or more processing components. Step-10: End ## IV. PARALLELISM BETWEEN PROPOSED ALGORITHM AND HUNGARIAN ALGORITHM Table 1 <table><tr><td>Proposed</td><td>Hungarian</td></tr><tr><td>·This tactic is employed to address issues with unbalanced assignments. ·If the number of jobs exceeds the number of processing components, all jobs must be completed using the available components. ·There are no unfinished projects. ·Related to at least one job that can be performed by a single component. ·A single component can only be assigned to a single job.</td><td>·This tactic is employed to address issues with unbalanced assignments. ·If the number of jobs exceeds the number of components, the remaining jobs are performed by dummy components. ·Some jobs aren't being completed. ·A single component can only do one thing. ·Only one component can be allocated to a single job.</td></tr></table> ## V. MATHEMATICAL ANALYSIS Let us take a problem of 8 jobs and 5 processing components with associated execution costs as given in Table 2. Table 2 <table><tr><td></td><td>J1</td><td>J2</td><td>J3</td><td>J4</td><td>J5</td><td>J6</td><td>J7</td><td>J8</td></tr><tr><td>C1</td><td>270</td><td>260</td><td>220</td><td>190</td><td>300</td><td>320</td><td>180</td><td>250</td></tr><tr><td>C2</td><td>210</td><td>190</td><td>300</td><td>200</td><td>290</td><td>180</td><td>190</td><td>310</td></tr><tr><td>C3</td><td>190</td><td>260</td><td>230</td><td>220</td><td>280</td><td>190</td><td>300</td><td>290</td></tr><tr><td>C4</td><td>250</td><td>210</td><td>180</td><td>190</td><td>290</td><td>240</td><td>190</td><td>300</td></tr><tr><td>C5</td><td>160</td><td>180</td><td>160</td><td>140</td><td>210</td><td>170</td><td>180</td><td>200</td></tr></table> <table><tr><td></td><td>J1</td><td>J2</td><td>J3</td><td>J4</td><td>J5</td><td>J6</td><td>J7</td><td>J8</td></tr><tr><td>C1</td><td>270</td><td>260</td><td>220</td><td>190</td><td>300</td><td>320</td><td>180</td><td>250</td></tr><tr><td>C2</td><td>210</td><td>190</td><td>300</td><td>200</td><td>290</td><td>180</td><td>190</td><td>310</td></tr><tr><td>C3</td><td>190</td><td>260</td><td>230</td><td>220</td><td>280</td><td>190</td><td>300</td><td>290</td></tr><tr><td>C4</td><td>250</td><td>210</td><td>180</td><td>190</td><td>290</td><td>240</td><td>190</td><td>300</td></tr><tr><td>C5</td><td>160</td><td>180</td><td>160</td><td>140</td><td>210</td><td>170</td><td>180</td><td>200</td></tr></table> Table 3: Follows steps 1, 2 and, 3 <table><tr><td></td><td>J1</td><td>J2</td><td>J3</td><td>J4</td><td>J5</td><td>J6</td><td>J7</td><td>J8</td></tr><tr><td>C1</td><td>50</td><td>80</td><td>60</td><td>90</td><td>40</td><td>150</td><td>0</td><td>50</td></tr><tr><td>C2</td><td>50</td><td>0</td><td>130</td><td>70</td><td>40</td><td>0</td><td>0</td><td>100</td></tr><tr><td>C3</td><td>60</td><td>60</td><td>50</td><td>50</td><td>10</td><td>0</td><td>100</td><td>70</td></tr><tr><td>C4</td><td>40</td><td>20</td><td>10</td><td>70</td><td>80</td><td>60</td><td>0</td><td>90</td></tr><tr><td>C5</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td></tr></table> Table 4: Follows step 4 <table><tr><td></td><td>J1</td><td>J2</td><td>J3</td><td>J4</td><td>J5</td><td>J6</td><td>J7</td><td>J8</td></tr><tr><td>C1</td><td>40</td><td>80</td><td>60</td><td>50</td><td>90</td><td>150</td><td>0</td><td>50</td></tr><tr><td>C2</td><td>40</td><td>0</td><td>130</td><td>50</td><td>70</td><td>0</td><td>0</td><td>100</td></tr><tr><td>C3</td><td>10</td><td>60</td><td>50</td><td>60</td><td>50</td><td>0</td><td>100</td><td>70</td></tr><tr><td>C4</td><td>80</td><td>20</td><td>10</td><td>40</td><td>70</td><td>60</td><td>0</td><td>90</td></tr><tr><td>C5</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td></tr></table> By step 5; from the uncovered costs, choose the lowest cost (i.e. 10) i. Deduct 10 from each exposed cost in the matrix above. ii. To get Table 5, sum up 10 at each of the intersection points. Table 5 <table><tr><td></td><td>J1</td><td>J2</td><td>J3</td><td>J4</td><td>J5</td><td>J6</td><td>J7</td><td>J8</td></tr><tr><td>C1</td><td>30</td><td>80</td><td>50</td><td>40</td><td>80</td><td>150</td><td>0</td><td>40</td></tr><tr><td>C2</td><td>30</td><td>0</td><td>120</td><td>40</td><td>60</td><td>0</td><td>0</td><td>90</td></tr><tr><td>C3</td><td>0</td><td>60</td><td>40</td><td>50</td><td>40</td><td>0</td><td>100</td><td>60</td></tr><tr><td>C4</td><td>70</td><td>0</td><td>0</td><td>30</td><td>60</td><td>60</td><td>0</td><td>80</td></tr><tr><td>C5</td><td>0</td><td>10</td><td>0</td><td>0</td><td>0</td><td>10</td><td>0</td><td>0</td></tr></table> Following steps 6 and 7, we allocate job $\mathrm{J}_3$ to component $\mathbf{M}_1$ and cross off the remaining zeros in the row corresponding to $\mathrm{J}_3$; as a result, row four has just one zero. As stated in Table 6, allocate work $\mathrm{J}_7$ to component $\mathbf{M}_4$. <table><tr><td></td><td>J1</td><td>J2</td><td>J3</td><td>J4</td><td>J5</td><td>J6</td><td>J7</td><td>J8</td></tr><tr><td>C1</td><td>30</td><td>80</td><td>50</td><td>40</td><td>80</td><td>150</td><td>0</td><td>40</td></tr><tr><td>C2</td><td>30</td><td>0</td><td>120</td><td>40</td><td>60</td><td>0</td><td>0</td><td>90</td></tr><tr><td>C3</td><td>0</td><td>60</td><td>40</td><td>50</td><td>40</td><td>0</td><td>100</td><td>60</td></tr><tr><td>C4</td><td>70</td><td>0</td><td>0</td><td>30</td><td>60</td><td>60</td><td>0</td><td>80</td></tr><tr><td>C5</td><td>0</td><td>10</td><td>0</td><td>0</td><td>0</td><td>10</td><td>0</td><td>0</td></tr></table> <table><tr><td></td><td>J1</td><td>J2</td><td>J3</td><td>J4</td><td>J5</td><td>J6</td><td>J7</td><td>J8</td></tr><tr><td>C1</td><td>30</td><td>80</td><td>50</td><td>40</td><td>80</td><td>150</td><td>0</td><td>40</td></tr><tr><td>C2</td><td>30</td><td>0</td><td>120</td><td>40</td><td>60</td><td>0</td><td>0</td><td>90</td></tr><tr><td>C3</td><td>0</td><td>60</td><td>40</td><td>50</td><td>40</td><td>0</td><td>100</td><td>60</td></tr><tr><td>C4</td><td>70</td><td>0</td><td>0</td><td>30</td><td>60</td><td>60</td><td>0</td><td>80</td></tr><tr><td>C5</td><td>0</td><td>10</td><td>0</td><td>0</td><td>0</td><td>10</td><td>0</td><td>0</td></tr></table> According to step 8, there is a tie in the 2nd and 3rd rows (containing two zeros). We allocate $\mathrm{J}_4$ to component $\mathrm{M}_2$ (in Table-7) because the cost associated with this position is the lowest in the original cost matrix. Table 7 <table><tr><td></td><td>J1</td><td>J2</td><td>J3</td><td>J4</td><td>J5</td><td>J6</td><td>J7</td><td>J8</td></tr><tr><td>C1</td><td>30</td><td>80</td><td>50</td><td>40</td><td>80</td><td>150</td><td>0</td><td>40</td></tr><tr><td>C2</td><td>30</td><td>0</td><td>120</td><td>40</td><td>60</td><td>0</td><td>0 ×</td><td>90</td></tr><tr><td>C3</td><td>0</td><td>60</td><td>40</td><td>50</td><td>40</td><td>0</td><td>100</td><td>60</td></tr><tr><td>C4</td><td>70</td><td>20</td><td>0</td><td>30</td><td>60</td><td>60</td><td>0 ×</td><td>80</td></tr><tr><td>C5</td><td>0</td><td>10</td><td>0 ×</td><td>0</td><td>0</td><td>10</td><td>10</td><td>0</td></tr></table> Then following step 9, we get the final table-8. Table 8 <table><tr><td></td><td>J1</td><td>J2</td><td>J3</td><td>J4</td><td>J5</td><td>J6</td><td>J7</td><td>J8</td></tr><tr><td>C1</td><td>30</td><td>80</td><td>50</td><td>40</td><td>80</td><td>150</td><td>0</td><td>40</td></tr><tr><td>C2</td><td>30</td><td>0</td><td>120</td><td>40</td><td>60</td><td>0</td><td>0 ×</td><td>90</td></tr><tr><td>C3</td><td>0</td><td>60</td><td>40</td><td>50</td><td>40</td><td>0 ×</td><td>100</td><td>60</td></tr><tr><td>C4</td><td>70</td><td>20</td><td>0</td><td>30</td><td>60</td><td>60</td><td>θ</td><td>80</td></tr><tr><td>C5</td><td>0 ×</td><td>10</td><td>0 ×</td><td>0</td><td>0</td><td>10</td><td>10</td><td>0</td></tr></table> ## VI. RESULTS AND DISCUSSION Table 9 shows the work assignment policy that reduces the overall cost. <table><tr><td>Component</td><td>Job</td><td>Cost</td></tr><tr><td>C1</td><td>J7</td><td>180</td></tr><tr><td>C2</td><td>J2,J6</td><td>190,180</td></tr><tr><td>C3</td><td>J1</td><td>180</td></tr><tr><td>C4</td><td>J3</td><td>190</td></tr><tr><td>C5</td><td>J4,J5,J8</td><td>140, 210,200</td></tr><tr><td colspan="3">Total Cost1470</td></tr></table> We find the total minimum cost in comparison to the other modified Hungarian methods like Kumar [26], Haragopal and Yadaiah [27], and Betts and Vasko [28]. ## VII. CONCLUSION The study presents an improved Hungarian algorithm to solve a particular case (when the number of jobs is greater than the number of processing components) of an unbalanced assignment problem. Generally, most of the issues regarding assignments occur in the abovementioned case. The primary premise of our strategy is to allocate all tasks to be completed. If the created assignment plan is invalid, the virtual jobs will be changed, and the procedure will be continued until an actual optimal assignment strategy is discovered. We show that the assignment strategy found by the suggested approach is the best using mathematical analysis. It demonstrates that the revised algorithm is capable of determining the best assignment strategy.

Generating HTML Viewer...