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
Bytes IT Community
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

Rabbit
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:
  1. Take the minimum cost from a row and subtract it from all the costs in that row.
  2. Take the minimum cost from a column and subtract it from all the costs in that column.
  3. 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.
  4. 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.
  5. Go back to step 3 and continue until all zeroes are assigned or crossed out.
  6. If every job / worker has been assigned, you are done.
  7. Cover all the zeroes that exist in the matrix using the fewest lines possible (there are multiple methods to do this)
  8. 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.
  9. 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. 1 3 5 3
  2. 2 4 6 1
  3. 1 3 5 5
  4. 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
  1. ' costMatrix(x, y, z)
  2. ' x = worker
  3. ' y = job
  4. ' z = properties
  5.  
  6. ' properties
  7. ' 0 = cost
  8. ' 1 = is assigned
  9. ' 2 = is marked row
  10. ' 3 = is marked column
  11. ' 4 = is covered row
  12. ' 5 = is covered column
  13.  
  14. Option Explicit
  15.  
  16. Const workers = 3 ' 0 based
  17. Const jobs = 3 ' 0 based
  18.  
  19. Dim costMatrix
  20. Dim jobAssignments
  21. Dim wrkAssignments
  22. Dim n, k, i, j
  23. Dim minimum
  24. Dim output
  25. Dim assignedCount
  26. Dim loopCount
  27. Dim zeroIndex
  28. Dim didAssign
  29.  
  30. ReDim costMatrix(workers, jobs, 5)
  31. ReDim jobAssignments(jobs)
  32. ReDim wrkAssignments(workers)
  33.  
  34. ' Populate cost matrix
  35. costMatrix(0, 0, 0) = 1
  36. costMatrix(0, 1, 0) = 3
  37. costMatrix(0, 2, 0) = 5
  38. costMatrix(0, 3, 0) = 3
  39. costMatrix(1, 0, 0) = 2
  40. costMatrix(1, 1, 0) = 4
  41. costMatrix(1, 2, 0) = 6
  42. costMatrix(1, 3, 0) = 1
  43. costMatrix(2, 0, 0) = 1
  44. costMatrix(2, 1, 0) = 3
  45. costMatrix(2, 2, 0) = 5
  46. costMatrix(2, 3, 0) = 5
  47. costMatrix(3, 0, 0) = 3
  48. costMatrix(3, 1, 0) = 1
  49. costMatrix(3, 2, 0) = 2
  50. costMatrix(3, 3, 0) = 5
  51.  
  52. ' Step 1, subtract row min from rows
  53. For i = 0 To workers
  54.     minimum = 999999
  55.  
  56.     ' Find minimum for the row
  57.     For j = 0 To jobs
  58.         If minimum > costMatrix(i, j, 0) Then
  59.             minimum = costMatrix(i, j, 0)
  60.         End If
  61.     Next
  62.  
  63.     ' Subtract minimum from each element in row
  64.     For j = 0 To jobs
  65.         costMatrix(i, j, 0) = costMatrix(i, j, 0) - minimum
  66.     Next
  67. Next
  68.  
  69. ' Step 2, subtract column min from columns
  70. For j = 0 To jobs
  71.     minimum = 999999
  72.  
  73.     ' Find minimum for the column
  74.     For i = 0 To workers
  75.         If minimum > costMatrix(i, j, 0) Then
  76.             minimum = costMatrix(i, j, 0)
  77.         End If
  78.     Next
  79.  
  80.     ' Subtract minimum from each element in column
  81.     For i = 0 To workers
  82.         costMatrix(i, j, 0) = costMatrix(i, j, 0) - minimum
  83.     Next
  84. Next
  85.  
  86. ' Check and Loop Steps 3 and 4
  87. loopCount = 0
  88. Do
  89.     loopCount = loopCount + 1
  90.  
  91.     ' Reset assignments
  92.     For i = 0 To workers
  93.         wrkAssignments(i) = False
  94.     Next
  95.  
  96.     For j = 0 To jobs
  97.         jobAssignments(j) = False
  98.     Next
  99.  
  100.     For i = 0 To workers
  101.         For j = 0 To jobs
  102.             costMatrix(i, j, 1) = 0
  103.         Next
  104.     Next
  105.  
  106.     ' Assign workers
  107.     Do
  108.         didAssign = False
  109.  
  110.         ' Assign lone 0's in rows
  111.         For i = 0 To workers
  112.             If wrkAssignments(i) = False Then
  113.                 assignedCount = 0
  114.  
  115.                 For j = 0 To jobs
  116.                     If jobAssignments(j) = False And costMatrix(i, j, 0) = 0 Then
  117.                         assignedCount = assignedCount + 1
  118.                         zeroIndex = j
  119.                     End If
  120.                 Next
  121.  
  122.                 If assignedCount = 1 Then
  123.                     costMatrix(i, zeroIndex, 1) = 1
  124.                     wrkAssignments(i) = True
  125.                     jobAssignments(zeroIndex) = True
  126.                     didAssign = True
  127.                 End If
  128.             End If
  129.         Next
  130.  
  131.         If didAssign = False Then
  132.             ' Assign lone 0's in columns
  133.             For j = 0 To jobs
  134.                 If jobAssignments(j) = False Then
  135.                     assignedCount = 0
  136.  
  137.                     For i = 0 To workers
  138.                         If wrkAssignments(i) = False And costMatrix(i, j, 0) = 0 Then
  139.                             assignedCount = assignedCount + 1
  140.                             zeroIndex = i
  141.                         End If
  142.                     Next
  143.  
  144.                     If assignedCount = 1 Then
  145.                         costMatrix(zeroIndex, j, 1) = 1
  146.                         wrkAssignments(zeroIndex) = True
  147.                         jobAssignments(j) = True
  148.                         didAssign = True
  149.                     End If
  150.                 End If
  151.             Next
  152.         End If
  153.  
  154.         If didAssign = False Then
  155.             ' Assign first 0
  156.             For i = 0 To workers
  157.                 If wrkAssignments(i) = False Then
  158.                     For j = 0 To jobs
  159.                         If didAssign = False Then
  160.                             If jobAssignments(j) = False And costMatrix(i, j, 0) = 0 Then
  161.                                 costMatrix(i, j, 1) = 1
  162.                                 wrkAssignments(i) = True
  163.                                 jobAssignments(j) = True
  164.                                 didAssign = True
  165.                             End If
  166.                         End If
  167.                     Next
  168.                 End If
  169.             Next
  170.         End If
  171.  
  172.         ' Exit loop if all 0's accounted for
  173.         assignedCount = 0
  174.  
  175.         For i = 0 To workers
  176.             For j = 0 To jobs
  177.                 If wrkAssignments(i) = False And jobAssignments(j) = False And costMatrix(i, j, 0) = 0 Then
  178.                     assignedCount = assignedCount + 1
  179.                 End If
  180.             Next
  181.         Next
  182.  
  183.         If assignedCount = 0 Then
  184.             Exit Do
  185.         End If
  186.     Loop
  187.  
  188.     ' Check to see if all jobs have been assigned
  189.     assignedCount = 0
  190.     For j = 0 To jobs
  191.         If jobAssignments(j) = True Then
  192.             assignedCount = assignedCount + 1
  193.         End If
  194.     Next
  195.  
  196.     If (assignedCount = (jobs + 1)) Or (assignedCount = (workers + 1)) Then
  197.         ' Exit if every job has an assignment or every worker has an assignment
  198.         Exit Do
  199.     ElseIf loopCount > 100 Then
  200.         ' Exit if looped too many times
  201.         WScript.Echo "Too Many Loops"
  202.         Exit Do
  203.     End If
  204.  
  205.     ' Prestep 3, unmark and uncover elements
  206.     For i = 0 To workers
  207.         For j = 0 To jobs
  208.             costMatrix(i, j, 2) = 0
  209.             costMatrix(i, j, 3) = 0
  210.             costMatrix(i, j, 4) = 0
  211.             costMatrix(i, j, 5) = 0
  212.         Next
  213.     Next
  214.  
  215.     ' Step 3a, mark rows and columns
  216.     For i = 0 To workers
  217.         assignedCount = 0
  218.  
  219.         ' Check to see if row (worker) has an assignment
  220.         For j = 0 To jobs
  221.             If costMatrix(i, j, 1) = 1 Then
  222.                 assignedCount = 1
  223.             End If
  224.         Next
  225.  
  226.         If assignedCount = 0 Then
  227.             ' No assignments so mark row
  228.             For j = 0 To jobs
  229.                 costMatrix(i, j, 2) = 1
  230.  
  231.                 ' Mark column if cost is 0 in row
  232.                 If costMatrix(i, j, 0) = 0 Then
  233.                     For n = 0 To workers
  234.                         costMatrix(n, j, 3) = 1
  235.                     Next
  236.                 End If
  237.             Next
  238.         End If
  239.     Next
  240.  
  241.     ' Check if column is marked
  242.     For j = 0 To jobs
  243.         If costMatrix(0, j, 3) = 1 Then
  244.             ' Check if row is assigned in column
  245.             For i = 0 To workers
  246.                 If costMatrix(i, j, 1) = 1 Then
  247.                     ' Mark row if both true
  248.                     For k = 0 To jobs
  249.                         costMatrix(i, k, 2) = 1
  250.                     Next
  251.                 End If
  252.             Next
  253.         End If
  254.     Next
  255.  
  256.     ' Step 3b, cover marked columns and unmarked rows
  257.     For i = 0 To workers
  258.         For j = 0 To jobs
  259.             If costMatrix(i, j, 2) = 0 Then costMatrix(i, j, 4) = 1
  260.             If costMatrix(i, j, 3) = 1 Then costMatrix(i, j, 5) = 1
  261.         Next
  262.     Next
  263.  
  264.     ' Step 4, subtract minimum from uncovered cells, add minimum to double covered cells
  265.  
  266.     ' Find minimum from uncovered cells
  267.     minimum = 999999
  268.     For i = 0 To workers
  269.         For j = 0 To jobs
  270.             If costMatrix(i, j, 4) = 0 And costMatrix(i, j, 5) = 0 Then
  271.                 If minimum > costMatrix(i, j, 0) Then
  272.                     minimum = costMatrix(i, j, 0)
  273.                 End If
  274.             End If
  275.         Next
  276.     Next
  277.  
  278.     ' Subtract from uncovered, add to double covered
  279.  
  280.     For i = 0 To workers
  281.         For j = 0 To jobs
  282.             If costMatrix(i, j, 4) = 0 And costMatrix(i, j, 5) = 0 Then
  283.                 costMatrix(i, j, 0) = costMatrix(i, j, 0) - minimum
  284.             ElseIf costMatrix(i, j, 4) = 1 And costMatrix(i, j, 5) = 1 Then
  285.                 costMatrix(i, j, 0) = costMatrix(i, j, 0) + minimum
  286.             End If
  287.         Next
  288.     Next
  289. Loop
  290.  
  291. output = ""
  292. For i = 0 To workers
  293.     For j = 0 To jobs
  294.         output = output & costMatrix(i, j, 1) & " | "
  295.     Next
  296.     output = output & vbCrLf
  297. Next
  298.  
  299. WScript.Echo output
Mar 24 '15 #1
Share this Article
Share on Google+