Lecture 7 min.
When solving certain management problems, it is necessary to assign performers (people, machines, and so on) to carry out tasks of the same type. Mack's method is used to distribute functions among the elements of a system when each of these elements is able to perform any of the functions with different efficiency [1, p. 240]. It is assumed that one element performs one function, and the system must achieve maximum efficiency at its output. For example, an organization has n workers among whom n tasks must be distributed so that all the tasks are completed in the minimum total time. The time needed to complete the tasks depends directly on the personality traits and qualifications of the performers. Consequently, for these and other reasons, the labor efficiency of the performers will differ.
This problem is called the assignment problem and is a special case of the more general transportation problem. There is a definite algorithm for solving the assignment problem by Mack's method. First, a matrix is constructed: suppose that the worker numbers (W) of the organization are listed vertically and the task numbers (T), which correspond to different positions, are listed horizontally. We fill the table with the task completion times. The goal is to find the minimum total time needed to complete all n tasks. An example of the table of initial data is given below.
Next, it is necessary to set up a system of constraints for the rows and columns. Since every worker must be employed and perform one task, and that task in turn must be performed, the sum of the elements in each row (and likewise in each column) must equal 1 [2, p. 97].
The total task completion time will be the objective function to be minimized, in which the corresponding time values serve as the coefficients of X_y.
The solution method of Mack's approach to this problem is based on the principle that the optimal choices do not change if the same number is added to, or subtracted from, every element of any row or column [3, p. 148].
The assignment problem is one of the best-known discrete optimization problems. The goal of the problem is to find the optimal (minimum-cost) assignment of workers to given jobs. The assignment problem has wide application, for example, in assigning vehicles to routes, allocating tools for processing various grades of steel, and so on.
Problem statement.
The obvious way to solve the problem is to enumerate all n! permutations. However, in practice such an inefficient approach becomes unusable even for matrices of small size.
The assignment problem is a special case of general classes of optimization problems, and therefore there are many different methods for solving it.
Divide the set of columns into A and A', where
A is the selected set,
A' is the unselected set.
At the beginning of the calculations, and when returning from cycles to the start, there are no selected columns; all columns belong to A'.
Choose from the set A' a column containing more than one underlined element, and move this column from A' to A.
An underlined element is the minimum element in a row.
Note: before the first step of the algorithm the set A is always empty.
If an underlined element is in the set A, find in each row the difference between the minimum underlined element and the minimum non-underlined element. From all the differences found, choose the minimum one.
Increase all elements of the matrix A by the minimum difference chosen at step 2.
In the row with the minimum difference, mark the minimum non-underlined element with a dashed line 
Move the column containing the element marked with a dashed line 
to the set C.
If C contains more than 2 non-underlined elements, move C from A' to A and go to step 2. Otherwise, go to step 6.
Underline the element marked with a dashed line 
(
changes to 
).
Find the original underlined element in the row with the minimum difference (the row where 
) and remove the underlining (
changes to
). Denote the column with the element
as D.
If D does not contain other underlined elements, it must contain elements marked with a dashed line. Denote this element
and go to step 6.
If D contains one more underlined element, then the fully underlined elements form a new basis. In this case, go to step 1.
Example 4.The initial table:
Let us underline the minimum elements in each row and add the first column to the set A, since it contains two underlined elements. The minimum of the differences found corresponds to the second row. Since this difference is 0, the elements of the set A remain unchanged. We move on to the next table.
Let us mark the element 
with a dashed line. We add the fifth column to the set C. C has only one underlined element. We underline it with a solid line, remove the underlining from the element
and designate the first column by the letter D. D has one more underlined element
, so we go to the first step.
We add the third column to the set A, find the minimum difference, and move on to the next table.
Let us mark the element 
with a dashed line. We add the fourth column to the set C. C has only one underlined element. We underline it with a solid line, remove the underlining from the element
and designate the third column by the letter D. D has more underlined elements, so we go to the first step.
We add the third column to the set A, find the minimum difference, and move on to the next table.
Let us mark the element 
with a dashed line. We add the fifth column to the set C. C still has other underlined elements, so we move the fifth column to A. The minimum difference corresponds to the second row.
Let us mark the element 
with a dashed line. We add the first column to the set C. C still has other underlined elements, so we move the fifth column to A. The minimum difference corresponds to the second row. We add the value of the minimum difference, i.e. 1, to all elements of the set A.
Let us mark the element 
with a dashed line. We add the second column to the set C. C has only one underlined element. We underline it with a solid line, remove the underlining from the element
and designate the fifth column by the letter D. D has one element underlined with a dashed line
. We underline it with a solid line and remove the underlining from the element
. The assignment is complete.
The corresponding value of the objective function:
f= 6 + 16 + 6 + 14 + 8 = 50
Comments