An assignment problem with queueing time cost

In this article we study the problem of assigning customers to service facilities with the objective of minimizing the total expected cost of accessing facilities and waiting for service at these facilities. We provide an integer programming formulation of the problem with a nonlinear objective function. A Lagrangian relaxation of the problem is described and a heuristic solution procedure is developed which utilizes the solution generated from the relaxed problem. Experimental results over a range of problems indicate that the solution method is both efficient and effective. A free standing heuristic developed for comparative purposes establishes the relative merit of the relaxation-based heuristic.