Article ID: | iaor20052972 |
Country: | Netherlands |
Volume: | 136 |
Issue: | 1 |
Start Page Number: | 81 |
End Page Number: | 97 |
Publication Date: | Apr 2005 |
Journal: | Annals of Operations Research |
Authors: | Ward James E., Zeng Ting |
Keywords: | networks, programming: assignment |
In the assignment problem units of supply are assigned on a one-to-one basis to units of demand so as to minimize the sum of the cost associated with each supply-to-demand matched pair. Defined on a network, the supplies and demands are located at vertices and the cost a supply-to-demand matched pair is the distance between them. This paper considers a two-stage stochastic program for locating the units of supply based upon only a probabilistic characterization of demand. The objective of the first-stage location problem is to minimize the expected cost of the second-stage assignment problem. Principal results include showing that the problem is NP-hard on a general network, has a simple solution procedure on a line network, and is solvable by a low order polynomial greedy procedure on a tree network. Potential applications are discussed.