Optimally Assigning Workers to Jobs Using the Hungarian Algorithm

[Rabbit]

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:

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.

' 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