Optimally Assigning Workers to Jobs Using the Hungarian Algorithm

**Rabbit** · Mar 24 '15, 03:58 PM

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.

Assignment problem - Wikipedia

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.

Hungarian algorithm - Wikipedia

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:

Code:

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.

Code:

' 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