By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
 429,616 Members | 2,026 Online Submit an Article
Got Smarts?
Share your bits of IT knowledge by writing an article on Bytes.

# Optimally Assigning Workers to Jobs Using the Hungarian Algorithm

 Expert Mod 10K+ P: 12,359 Introduction The assignment problem is one of the basic optimization problems. In simple terms, the question being asked is something like this: There are a x number of workers and y number of jobs. Any worker can be assigned any job, but each combination of worker and job has an associated cost. All the workers should be assigned to a job in such a way that the total cost of the assignments is minimized. The terms worker, job, and cost can be generalized. They don't necessarily have to fit in that exact scenario. Anytime you need to assign one thing to another in an optimal manner is considered an assignment problem. For example, if you need to assign students to classes based on their most preferred time slots. In that scenario, the worker is the student, the job is the class, and the time slot preference is the cost. http://en.wikipedia.org/wiki/Assignment_problem The Hungarian Algorithm The Hungarian algorithm solves the assignment problem in polynomial time. It was developed and published by Harold Kuhn in 1955. In general, the algorithm works by taking a two-dimensional cost matrix and performs operations on it to create zeroes until everything can be assigned. The steps are: Take the minimum cost from a row and subtract it from all the costs in that row. Take the minimum cost from a column and subtract it from all the costs in that column. Assign lone zeroes in a column or row and cross out any other zeroes in that column and row. Continue until no lone zeroes exist. If a row or column contains multiple zeroes (ie multiple workers can do the job at the same cost or a worker can do multiple jobs at the same cost), assign any zero and cross out the others. Go back to step 3 and continue until all zeroes are assigned or crossed out. If every job / worker has been assigned, you are done. Cover all the zeroes that exist in the matrix using the fewest lines possible (there are multiple methods to do this) Take the minimum from the uncovered cells and subtract it from all uncovered cells. Add the minimum to those cells that are covered in both a row and column. Go back to step 3. http://en.wikipedia.org/wiki/Hungarian_algorithm The Code and How to Use It The code below is an example implementation of the Hungarian Algorithm in VBScript and is easily portable to VBA. It uses a cost matrix with test data of: Expand|Select|Wrap|Line Numbers 1 3 5 3 2 4 6 1 1 3 5 5 3 1 2 5 The worker is the row, the job is the column, and the cell value is the cost of assigning the worker to that job. This example can be packaged into a function where you supply a cost matrix and it outputs an assignment matrix. The implementation is also limited to the linear form of the assignment problem. Meaning that there is a one to one assignment of worker to job. It can handle if there is more of one than the other. But it not generalized to assign the same worker to multiple jobs or vice versa. If that is needed, the algorithm should be able to adapt to that by some modifications to the assignment part. I'm thinking additional variables to keep track of assignments per job and assignments per worker. Expand|Select|Wrap|Line Numbers ' costMatrix(x, y, z) ' x = worker ' y = job ' z = properties   ' properties ' 0 = cost ' 1 = is assigned ' 2 = is marked row ' 3 = is marked column ' 4 = is covered row ' 5 = is covered column   Option Explicit   Const workers = 3 ' 0 based Const jobs = 3 ' 0 based   Dim costMatrix Dim jobAssignments Dim wrkAssignments Dim n, k, i, j Dim minimum Dim output Dim assignedCount Dim loopCount Dim zeroIndex Dim didAssign   ReDim costMatrix(workers, jobs, 5) ReDim jobAssignments(jobs) ReDim wrkAssignments(workers)   ' Populate cost matrix costMatrix(0, 0, 0) = 1 costMatrix(0, 1, 0) = 3 costMatrix(0, 2, 0) = 5 costMatrix(0, 3, 0) = 3 costMatrix(1, 0, 0) = 2 costMatrix(1, 1, 0) = 4 costMatrix(1, 2, 0) = 6 costMatrix(1, 3, 0) = 1 costMatrix(2, 0, 0) = 1 costMatrix(2, 1, 0) = 3 costMatrix(2, 2, 0) = 5 costMatrix(2, 3, 0) = 5 costMatrix(3, 0, 0) = 3 costMatrix(3, 1, 0) = 1 costMatrix(3, 2, 0) = 2 costMatrix(3, 3, 0) = 5   ' Step 1, subtract row min from rows For i = 0 To workers     minimum = 999999       ' Find minimum for the row     For j = 0 To jobs         If minimum > costMatrix(i, j, 0) Then             minimum = costMatrix(i, j, 0)         End If     Next       ' Subtract minimum from each element in row     For j = 0 To jobs         costMatrix(i, j, 0) = costMatrix(i, j, 0) - minimum     Next Next   ' Step 2, subtract column min from columns For j = 0 To jobs     minimum = 999999       ' Find minimum for the column     For i = 0 To workers         If minimum > costMatrix(i, j, 0) Then             minimum = costMatrix(i, j, 0)         End If     Next       ' Subtract minimum from each element in column     For i = 0 To workers         costMatrix(i, j, 0) = costMatrix(i, j, 0) - minimum     Next Next   ' Check and Loop Steps 3 and 4 loopCount = 0 Do     loopCount = loopCount + 1       ' Reset assignments     For i = 0 To workers         wrkAssignments(i) = False     Next       For j = 0 To jobs         jobAssignments(j) = False     Next       For i = 0 To workers         For j = 0 To jobs             costMatrix(i, j, 1) = 0         Next     Next       ' Assign workers     Do         didAssign = False           ' Assign lone 0's in rows         For i = 0 To workers             If wrkAssignments(i) = False Then                 assignedCount = 0                   For j = 0 To jobs                     If jobAssignments(j) = False And costMatrix(i, j, 0) = 0 Then                         assignedCount = assignedCount + 1                         zeroIndex = j                     End If                 Next                   If assignedCount = 1 Then                     costMatrix(i, zeroIndex, 1) = 1                     wrkAssignments(i) = True                     jobAssignments(zeroIndex) = True                     didAssign = True                 End If             End If         Next           If didAssign = False Then             ' Assign lone 0's in columns             For j = 0 To jobs                 If jobAssignments(j) = False Then                     assignedCount = 0                       For i = 0 To workers                         If wrkAssignments(i) = False And costMatrix(i, j, 0) = 0 Then                             assignedCount = assignedCount + 1                             zeroIndex = i                         End If                     Next                       If assignedCount = 1 Then                         costMatrix(zeroIndex, j, 1) = 1                         wrkAssignments(zeroIndex) = True                         jobAssignments(j) = True                         didAssign = True                     End If                 End If             Next         End If           If didAssign = False Then             ' Assign first 0             For i = 0 To workers                 If wrkAssignments(i) = False Then                     For j = 0 To jobs                         If didAssign = False Then                             If jobAssignments(j) = False And costMatrix(i, j, 0) = 0 Then                                 costMatrix(i, j, 1) = 1                                 wrkAssignments(i) = True                                 jobAssignments(j) = True                                 didAssign = True                             End If                         End If                     Next                 End If             Next         End If           ' Exit loop if all 0's accounted for         assignedCount = 0           For i = 0 To workers             For j = 0 To jobs                 If wrkAssignments(i) = False And jobAssignments(j) = False And costMatrix(i, j, 0) = 0 Then                     assignedCount = assignedCount + 1                 End If             Next         Next           If assignedCount = 0 Then             Exit Do         End If     Loop       ' Check to see if all jobs have been assigned     assignedCount = 0     For j = 0 To jobs         If jobAssignments(j) = True Then             assignedCount = assignedCount + 1         End If     Next       If (assignedCount = (jobs + 1)) Or (assignedCount = (workers + 1)) Then         ' Exit if every job has an assignment or every worker has an assignment         Exit Do     ElseIf loopCount > 100 Then         ' Exit if looped too many times         WScript.Echo "Too Many Loops"         Exit Do     End If       ' Prestep 3, unmark and uncover elements     For i = 0 To workers         For j = 0 To jobs             costMatrix(i, j, 2) = 0             costMatrix(i, j, 3) = 0             costMatrix(i, j, 4) = 0             costMatrix(i, j, 5) = 0         Next     Next       ' Step 3a, mark rows and columns     For i = 0 To workers         assignedCount = 0           ' Check to see if row (worker) has an assignment         For j = 0 To jobs             If costMatrix(i, j, 1) = 1 Then                 assignedCount = 1             End If         Next           If assignedCount = 0 Then             ' No assignments so mark row             For j = 0 To jobs                 costMatrix(i, j, 2) = 1                   ' Mark column if cost is 0 in row                 If costMatrix(i, j, 0) = 0 Then                     For n = 0 To workers                         costMatrix(n, j, 3) = 1                     Next                 End If             Next         End If     Next       ' Check if column is marked     For j = 0 To jobs         If costMatrix(0, j, 3) = 1 Then             ' Check if row is assigned in column             For i = 0 To workers                 If costMatrix(i, j, 1) = 1 Then                     ' Mark row if both true                     For k = 0 To jobs                         costMatrix(i, k, 2) = 1                     Next                 End If             Next         End If     Next       ' Step 3b, cover marked columns and unmarked rows     For i = 0 To workers         For j = 0 To jobs             If costMatrix(i, j, 2) = 0 Then costMatrix(i, j, 4) = 1             If costMatrix(i, j, 3) = 1 Then costMatrix(i, j, 5) = 1         Next     Next       ' Step 4, subtract minimum from uncovered cells, add minimum to double covered cells       ' Find minimum from uncovered cells     minimum = 999999     For i = 0 To workers         For j = 0 To jobs             If costMatrix(i, j, 4) = 0 And costMatrix(i, j, 5) = 0 Then                 If minimum > costMatrix(i, j, 0) Then                     minimum = costMatrix(i, j, 0)                 End If             End If         Next     Next       ' Subtract from uncovered, add to double covered       For i = 0 To workers         For j = 0 To jobs             If costMatrix(i, j, 4) = 0 And costMatrix(i, j, 5) = 0 Then                 costMatrix(i, j, 0) = costMatrix(i, j, 0) - minimum             ElseIf costMatrix(i, j, 4) = 1 And costMatrix(i, j, 5) = 1 Then                 costMatrix(i, j, 0) = costMatrix(i, j, 0) + minimum             End If         Next     Next Loop   output = "" For i = 0 To workers     For j = 0 To jobs         output = output & costMatrix(i, j, 1) & " | "     Next     output = output & vbCrLf Next   WScript.Echo output Mar 24 '15 #1
Share this Article

### Post your comment

Sign in to post your comment or Sign up for a free account. 