×

An assignment problem with queueing time cost. (English) Zbl 0711.90024

This paper studies 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. An integer programming formulation of the problem with a nonlinear objective function is provided. A Lagrangian relaxation method is described and a heuristic solution procedure is developed which utilizes the solution generated from the relaxation problem. Experimental results for a great variety of problems indicate the efficiency and effectiveness of the method proposed. Further research areas are suggested in the end of the paper.
Reviewer: J.Sztrik

MSC:

90B22 Queues and service in operations research
60K25 Queueing theory (aspects of probability theory)
90C90 Applications of mathematical programming
65K05 Numerical mathematical programming methods
90C10 Integer programming
90C30 Nonlinear programming
90-08 Computational methods for problems pertaining to operations research and mathematical programming
PDF BibTeX XML Cite
Full Text: DOI

References:

[1] ”Classifications and Formulations of Service Facility Location Problems,” in Ed., Hazardous Materials Disposal: Siting and Management, Gower, London, 1987.
[2] Models for Public Systems Analysis, Academic Press, New York, 1977.
[3] Clark, Interfaces 6 pp 32– (1975)
[4] Erlonkotter, Operations Research 26 pp 992– (1978)
[5] Fisher, Interfaces 15 pp 10– (1985)
[6] Fisher, Management Science 27 pp 1– (1981)
[7] Fisher, Management Science 32 pp 1095– (1986)
[8] Francis, European Journal of Operational Research 12 pp 220– (1983)
[9] and , Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman and Company, San Francisco, 1979. · Zbl 0411.68039
[10] Gavish, Mathematical Programming 31 pp 78– (1985)
[11] Geoffrion, AIIE Transactions 10 pp 40– (1978)
[12] Held, Mathematical Programming 5 pp 62– (1974)
[13] and , Introductions to Operations Research, 4th ed., Holden-Day, Oakland, 1986.
[14] private correspondence, The New York City Sanitation Department, New York, NY, 1988.
[15] Queueing Systems, Volume II: Computer Applications, John Wiley and Sons, New York, 1976.
[16] and , ”An Algorithm for the Generalized Assignment Problem,” Operational Reseach 81, North-Holland, Amsterdam, 1981, pp. 589–603.
[17] Pirkul, Naval Research Logistics Quarterly 34 pp 161– (1987)
[18] Pirkul, Management Science 34 pp 896– (1988)
[19] Revelle, Management Science 16 pp 692– (1970)
[20] Riccio, Interfaces 16 pp 83– (1986)
[21] Riccio, Interfaces 14 pp 1– (1984)
[22] Ross, Mathematical Programming 8 pp 92– (1975)
[23] Ross, Management Science 24 pp 345–
[24] Sinha, Operations Research 27 pp 503– (1979)
[25] Wirasinghe, European Journal of Operational Research 12 pp 105– (1983) · Zbl 0499.90023
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.