Hungarian method

Also called Kühn algorithm, the Hungarian algorithm, or Hungarian method solves cost allocation table. Consider a number of machines and as many tasks. Each machine performs a task at a certain cost. The goal is to determine the machine on which each task will run, in parallel.

Since this problem is similar to a coupling problem in a graph, it meets König’s criterion for nodal minimum weight coverage. The goal is to find one element per row and column in the table so that the sum of the costs is minimal. If we start from a problem of maximization, it will be necessary to reverse the costs in order to fall back on a problem of minimization.

Let’s take a simple example to show the process of the algorithm. There are 5 machines (line) and 5 tasks (column) giving the following cost table:

17
15
9
5
12
16
16
10
5
10
12
15
14
11
5
4
8
14
17
13
13
9
8
12
17

Step 1: Reduction of the initial table

One subtract each line the smallest element of the line. Then we subtract from each column the smallest element of the column.
12
9
4
0
7
11
10
5
0
5
7
9
9
6
0
0
3
10
13
9
5
0
0
4
9

This standardization of machine costs and tasks makes it possible to have at least one zero per line and per column.

Step 2: Find a feasible solution

We are looking for the line with the fewest zeros. In case of equality we will take the highest line.

  1. We frame one of the zeros of this line (arbitrarily the one on the left).
  2. We mark all zeros on the same row and column as the one selected.
  3. We start again until all the zeros are framed or crossed out.

If we have a zero per line and column, we have an optimal solution. Otherwise we go to step 3.

12
9
4
0
7
11
10
5
-0-
5
7
9
9
6
0
0
3
10
13
9
5
0
-0-
4
9

Step 3: Creating pivots

The sub-table allows by retrench to have a configuration to find an optimal solution. The construction of the pivots is as follows:

  1. Mark all rows having no assignments.
  2. Mark all (unmarked) columns having zeros in newly marked row(s).
  3. Mark all rows having assignments in newly marked columns.
  4. Repeat for all non-assigned rows.

A line is then drawn on any unmarked line and any marked column. In our example, the lines 1 and 2 are marked, as well as the column 4. The elements twice marked are accompanied by a star.

12
9
4
-0-
7
11
10
5
-0-
5
-7-
-9-
-9-
*-6-*
-0-
-0-
-3-
-10-
*-13-*
-9-
-5-
-0-
-0-
*-4-*
-9-

Step 4: Edit the table

Non crossings elements with a line are a partial table.

  1. From the elements that are left, find the lowest value. Subtract this from every unmarked element and add it to every element covered by two lines.
  2. Repeat steps 2–4 until an assignment is possible

 

8
5
0
0
3
7
6
1
0
1
7
9
9
10
0
0
3
10
17
9
5
0
0
8
9

The minimum allocation is calculated from the initial table: 9+5+5+4+9 = 32.

Publicités