Tools › Operations Research › Optimization › Transportation and Assignment › Example
Winston Section 7.5: the Machineco assignment problem by the Hungarian method
| Tool | Transportation and Assignment |
| Source | Winston, W. L. (2004). Operations Research: Applications and Algorithms, 4th ed. Brooks/Cole, Belmont, CA. Section 7.5. |
| Level | Undergraduate |
Problem
Machineco has four machines and four jobs; the time each machine needs for each job is tabulated. Assign one job to each machine so that the total setup time is a minimum, showing the row and column reductions, the minimum line cover and the adjustment step of the Hungarian method.
Inputs to Enter
- Problem select: Assignment, Machineco (Winston)
- Times: Machine 1 14, 5, 8, 7; Machine 2 2, 12, 6, 5; Machine 3 7, 8, 3, 9; Machine 4 2, 4, 6, 10
Answers
- Row minima 5, 2, 3, 2 (row 1 becomes 9 0 3 2); column minima 0, 0, 0, 2 (row 2 becomes 0 10 4 1)
- First cover needs 3 lines (rows 1 and 3, column 1); smallest uncovered entry 1; adjusted row 1 = 10 0 3 0, row 2 = 0 9 3 0, row 4 = 0 1 3 5; second cover needs 4 lines
- Optimal total 15: Machine 1 → Job 2, Machine 2 → Job 4, Machine 3 → Job 3, Machine 4 → Job 1 (unique; scipy linear_sum_assignment 15)
Notes
Choose the Machineco entry in the problem select. The Job Shop (H&L, total 29 with a forbidden cell) and Taha Examples 5.4-1 (27) and 5.4-2 (21) are further selector entries.