IDEAS home Printed from https://ideas.repec.org/a/inm/oropre/v41y1993i5p959-971.html
   My bibliography  Save this article

Minimax Resource Allocation Problems with Resource-Substitutions Represented by Graphs

Author

Listed:
  • Rachelle S. Klein

    (AT&T Bell Laboratories, Holmdel, New Jersey)

  • Hanan Luss

    (AT&T Bell Laboratories, Holmdel, New Jersey)

  • Uriel G. Rothblum

    (Technion-Israel Institute of Technology, Haifa, Israel)

Abstract

Resource allocation problems focus on the allocation of limited resources among competing activities. We examine such problems when certain substitutions among resources are possible. The substitutional relations can be represented by a graph comprised of multiple components. In each component, the nodes correspond to resources and the arcs correspond to feasible substitutions. The objective is of the minimax form, where each term is a continuous, strictly decreasing function of a single activity level. The objective is to minimize the largest term, subject to a limited supply of multiple resources. Potential applications to such problems are found, for example, in the manufacture of high tech products. We develop an efficient algorithm to solve such problems. At each iteration, a relaxed minimax problem is solved. A max-flow algorithm is then applied to determine whether the solution of the relaxed problem is feasible for the original problem. If the solution is infeasible, a tighter relaxed problem is formulated and resolved. The algorithm is also extended to find the lexicographic minimax solution. Computational results are presented.

Suggested Citation

  • Rachelle S. Klein & Hanan Luss & Uriel G. Rothblum, 1993. "Minimax Resource Allocation Problems with Resource-Substitutions Represented by Graphs," Operations Research, INFORMS, vol. 41(5), pages 959-971, October.
    • Handle: RePEc:inm:oropre:v:41:y:1993:i:5:p:959-971
    DOI: 10.1287/opre.41.5.959
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/opre.41.5.959
    Download Restriction: no
    File URL: https://libkey.io/10.1287/opre.41.5.959?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. G. Yu, 1998. "Min-Max Optimization of Several Classical Discrete Optimization Problems," Journal of Optimization Theory and Applications, Springer, vol. 98(1), pages 221-242, July.
    2. Narendra Agrawal & Stephen A. Smith, 2003. "Optimal retail assortments for substitutable items purchased in sets," Naval Research Logistics (NRL), John Wiley & Sons, vol. 50(7), pages 793-822, October.
    3. Hanan Luss, 1999. "On Equitable Resource Allocation Problems: A Lexicographic Minimax Approach," Operations Research, INFORMS, vol. 47(3), pages 361-378, June.
    4. Stephen A. Smith & Narendra Agrawal, 2000. "Management of Multi-Item Retail Inventory Systems with Demand Substitution," Operations Research, INFORMS, vol. 48(1), pages 50-64, February.
    5. Ogryczak, Wlodzimierz & Wierzbicki, Adam & Milewski, Marcin, 2008. "A multi-criteria approach to fair and efficient bandwidth allocation," Omega, Elsevier, vol. 36(3), pages 451-463, June.
    6. Klein, Rachelle S. & Luss, Hanan & Rothblum, Uriel G., 1995. "Multiperiod allocation of substitutable resources," European Journal of Operational Research, Elsevier, vol. 85(3), pages 488-503, September.
    7. Jinfa Chen & David D. Yao & Shaohui Zheng, 2001. "Optimal Replenishment and Rework with Multiple Unreliable Supply Sources," Operations Research, INFORMS, vol. 49(3), pages 430-443, June.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:inm:oropre:v:41:y:1993:i:5:p:959-971. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    We have no bibliographic references for this item. You can help adding them by using this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Chris Asher (email available below). General contact details of provider: https://edirc.repec.org/data/inforea.html .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.