Glossary · approach
Assignment Problem
Matching a set of resources (people, vehicles, machines) to a set of tasks at minimum cost or maximum benefit.
Hungarian AlgorithmBipartite Matching
The assignment problem is the problem of one-to-one matching n resources (e.g. workers, technicians, vehicles) to n tasks while minimizing total cost or maximizing total benefit. Its classical form was solved in polynomial time by Kuhn in 1955 with the 'Hungarian algorithm' — one of OR's oldest and most elegant solutions. The generalized assignment problem (GAP) allows multiple tasks per resource and is NP-hard. The mathematical skeleton of many problems sits on top of the assignment problem: field-service technician dispatch, shift scheduling, school timetabling, bid allocation, robot-task assignment.
Örnek
Matching 5 technicians to 5 customers, where each technician's travel time to each customer is different. The Hungarian algorithm finds the matching that minimizes total travel time in seconds.