The assignment problem is one of the fundamental combinatorial optimization problems in the branch of optimization or operations research in mathematics. It consists of finding a maximum weight matching (or minimum weight perfect matching) in a weightedbipartite graph.
In its most general form, the problem is as follows:
- The problem instance has a number of agents and a number of tasks. Any agent can be assigned to perform any task, incurring some cost that may vary depending on the agent-task assignment. It is required to perform all tasks by assigning exactly one agent to each task and exactly one task to each agent in such a way that the total cost of the assignment is minimized.
If the numbers of agents and tasks are equal and the total cost of the assignment for all tasks is equal to the sum of the costs for each agent (or the sum of the costs for each task, which is the same thing in this case), then the problem is called the linear assignment problem. Commonly, when speaking of the assignment problem without any additional qualification, then the linear assignment problem is meant.
Algorithms and generalizations
The Hungarian algorithm is one of many algorithms that have been devised that solve the linear assignment problem within time bounded by a polynomial expression of the number of agents. Other algorithms include adaptations of the primal simplex algorithm, and the auction algorithm.
The assignment problem is a special case of the transportation problem, which is a special case of the minimum cost flow problem, which in turn is a special case of a linear program. While it is possible to solve any of these problems using the simplex algorithm, each specialization has more efficient algorithms designed to take advantage of its special structure.
When a number of agents and tasks is very large, a parallel algorithm with randomization can be applied. The problem of finding minimum weight maximum matching can be converted to finding a minimum weight perfect matching. A bipartite graph can be extended to a complete bipartite graph by adding artificial edges with large weights. These weights should exceed the weights of all existing matchings to prevent appearance of artificial edges in the possible solution. As shown by Mulmuley, Vazirani & Vazirani (1987), the problem of minimum weight perfect matching is converted to finding minors in the adjacency matrix of a graph. Using the isolation lemma, a minimum weight perfect matching in a graph can be found with probability at least ½. For a graph with n vertices, it requires time.
Suppose that a taxi firm has three taxis (the agents) available, and three customers (the tasks) wishing to be picked up as soon as possible. The firm prides itself on speedy pickups, so for each taxi the "cost" of picking up a particular customer will depend on the time taken for the taxi to reach the pickup point. The solution to the assignment problem will be whichever combination of taxis and customers results in the least total cost.
However, the assignment problem can be made rather more flexible than it first appears. In the above example, suppose that there are four taxis available, but still only three customers. Then a fourth dummy task can be invented, perhaps called "sitting still doing nothing", with a cost of 0 for the taxi assigned to it. The assignment problem can then be solved in the usual way and still give the best solution to the problem.
Similar adjustments can be done in order to allow more tasks than agents, tasks to which multiple agents must be assigned (for instance, a group of more customers than will fit in one taxi), or maximizing profit rather than minimizing cost.
Formal mathematical definition
The formal definition of the assignment problem (or linear assignment problem) is
- Given two sets, A and T, of equal size, together with a weight functionC : A × T → R. Find a bijectionf : A → T such that the cost function:
Usually the weight function is viewed as a square real-valued matrixC, so that the cost function is written down as:
The problem is "linear" because the cost function to be optimized as well as all the constraints contain only linear terms.
The problem can be expressed as a standard linear program with the objective function
subject to the constraints
The variable represents the assignment of agent to task , taking value 1 if the assignment is done and 0 otherwise. This formulation allows also fractional variable values, but there is always an optimal solution where the variables take integer values. This is because the constraint matrix is totally unimodular. The first constraint requires that every agent is assigned to exactly one task, and the second constraint requires that every task is assigned exactly one agent.
K.R. Baker, Introduction to Sequencing and Scheduling, Wiley, New York, 1974.Google Scholar
A.P. Barbosa-Póvoa, Detailed design and retrofit of multipurpose batch plants, Ph.D. Thesis, University of London, London, 1994.Google Scholar
D.B. Birewar and I.E. Grossmann, Incorporating scheduling in the optimal design of multiproduct batch plants, Computers Chem. Eng. 13(1989)141–161.CrossRefGoogle Scholar
D.B. Birewar and I.E. Grossmann, Efficient optimization algorithms for zero-wait scheduling of multiproduct plants, I&EC Research 28(1989)1333–1345.Google Scholar
J. Cerdá, G. Henning and I.E. Grossmann, A mixed-integer linear programming model for short term batch scheduling in parallel lines, presented at the ORSA/TIMS Meeting–Global Manufacturing in the 21st Century, Detroit, MI, 1994.Google Scholar
C.A. Crooks, Synthesis of operating procedures for chemical plants, Ph.D. thesis, University of London, London, 1992.Google Scholar
S. French, Sequencing and Scheduling: An Introduction to the Mathematics of the Job-Shop, Ellis Horwood, England, 1982.Google Scholar
W.B. Gooding, J.F. Pekny and P.S. McCroskey, Enumerative approaches to parallel flowshop scheduling via problem transformation, Computers Chem. Eng. 18(1994)909–927.CrossRefGoogle Scholar
I.E. Grossmann, J. Quesada, R. Raman and V. Voudouris, Mixed integer optimization techniques for the design and scheduling of batch processes, in: Batch Processing Systems Engineering, eds. G.V. Reklaitis, A.K. Sunol, D.W.T. Rippin and O. Hortacsu, Springer, Berlin, 1996, pp. 451–494.Google Scholar
J.N.D. Gupta, Optimal flowshop schedules with no intermediate storage space, Nav. Res. Logist. Quart. 23(1976)235–243.Google Scholar
E. Kondili, C.C. Pantelides and R.W.H. Sargent, A general algorithm for short-term scheduling of batch operations. I. MILP formulation, Computers Chem. Eng. 17(1993)211–227.CrossRefGoogle Scholar
H. Ku, D. Rajagopalan and I.A. Karimi, Scheduling in batch processes, Chem. Eng. Prog. 83 (1987)35–45.Google Scholar
C.C. Pantelides, Unified frameworks for optimal process planning and scheduling, in: Foundations of Computer Aided Process Operations, eds. D.W.T. Rippin, J.C. Hale and J.F. Davis, CACHE, Austin, TX, 1994, pp. 253–274.Google Scholar
J.F. Pekny and D.L. Miller, Exact solution of the no-wait flowshop scheduling problem with a comparison to heuristic methods, Computers Chem. Eng. 15(1991)741–748.CrossRefGoogle Scholar
J.F. Pekny and M.G. Zentner, Learning to solve process scheduling problems: The role of rigorous knowledge acquisition frameworks, in: Foundations of Computer Aided Process Operations, eds. D.W.T. Rippin, J.C. Hale and J.F. Davis, CACHE, Austin, TX, 1994, pp. 275–309.Google Scholar
J.M. Pinto and I.E. Grossmann, Optimal cyclic scheduling of multistage continuous multiproduct plants, Computers Chem. Eng. 18(1994)797–816.CrossRefGoogle Scholar
J.M. Pinto and I.E. Grossmann, A continuous time mixed-integer linear programming model for short term scheduling of multistage batch plants, I&EC Research 34(1995)3037–3051.Google Scholar
J. Pinto and I.E. Grossmann, An alternate MILP model for short term batch scheduling with preordering constraints, Ind. Eng. Chem. Research 35(1996)338–342.CrossRefGoogle Scholar
G.V. Reklaitis, Perspectives on scheduling and planning of process operations, presented at the 4th International Symposium on Process Systems Engineering, Montebello, Canada, 1991.Google Scholar
G.V. Reklaitis, Overview of scheduling and planning of batch process operations, NATO Advanced Study Institute–Batch Process Systems Engineering, Antalya, Turkey, 1992.Google Scholar
S.H. Rich and G.J. Prokopakis, Scheduling and sequencing of batch operations in a multipurpose plant, Ind. Eng. Chem. Process Des. Dev. 25(1986)979–988.CrossRefGoogle Scholar
D.W.T. Rippin, Batch process systems engineering: a retrospective and prospective review, Computers Chem. Eng. 17 (suppl. issue)1993, S1–S13.CrossRefGoogle Scholar
N.V. Sahinidis and I.E. Grossmann, MINLP model for cyclic multiproduct scheduling on continuous parallel lines, Computers Chem. Eng. 15(1991)85–103.CrossRefGoogle Scholar
N.V. Sahinidis and I.E. Grossmann, Reformulation of multiperiod MILP models for planning and scheduling of chemical processes, Computers Chem. Eng. 15(1991)255–272.CrossRefGoogle Scholar
G. Schilling, Y.-E. Pineau, C.C. Pantelides and N. Shah, Optimal scheduling of multipurpose continuous plants, presented at the AIChE National Meeting, San Francisco, CA, 1994.Google Scholar
N. Shah, Efficient scheduling, planning and design of multipurpose batch plants, Ph.D. Thesis, University of London, London, 1992.Google Scholar
N. Shah, C.C. Pantelides and R.W.H. Sargent, A general algorithm for short-term scheduling of batch operations. II. Computational issues, Computers Chem. Eng. 17(1993)229–244.CrossRefGoogle Scholar
N. Shah, C.C. Pantelides and R.W.H. Sargent, Optimal periodic scheduling of multipurpose batch plants, Ann. Oper. Res. 42(1993)193–228.CrossRefGoogle Scholar
V.T. Voudouris and I.E. Grossmann, Optimal synthesis of multiproduct batch plants with cyclic scheduling and inventory considerations, Ind. Eng. Chem. Res. 32(1993)1962 –1980.CrossRefGoogle Scholar
V.T. Voudouris and I.E. Grossmann, An MILP model for the optimal design and scheduling of a special class of multipurpose plants, Computers Chem. Eng. 20(1996)1335–1360.CrossRefGoogle Scholar
S.J. Wilkinson, N. Shah and C.C. Pantelides, Scheduling of multisite flexible production systems, paper presented at the AIChE Annual Meeting, San Francisco, CA, 1994.Google Scholar
P. Williams, Model Building in Mathematical Programming, 2nd ed., Wiley, Chichester, Northern Ireland, 1985.Google Scholar
Z. Xueya and R.W.H. Sargent, The optimal operation of mixed production facilities–a general formulation and some approaches to the solution, Proceedings of the 5th Symposium on Process Systems Engineering, Kyongju, Korea, 1994.Google Scholar
Z. Xueya, Algorithms for optimal process scheduling using nonlinear models, Ph.D. Thesis, University of London, London, 1995.Google Scholar