IDEAS home Printed from https://ideas.repec.org/a/wly/navres/v41y1994i6p719-738.html
   My bibliography  Save this article

Minimax resource allocation problems with ordering constraints

Author

Listed:
  • Lisa M. Betts
  • J. Randall Brown
  • Hanan Luss

Abstract

Resource allocation problems consider the allocation of limited resources among numerous competing activities. We address an allocation problem with multiple knapsack resource constraints. The activities are grouped into disjoint sets. Ordering constraints are imposed on the activities within each set, so that the level of one activity cannot exceed the level of another activity in the same set. The objective function is of the minimax type and each performance function is a nonlinear, strictly decreasing and continuous function of a single variable. Applications for such resource allocation problems are found, for example, in high‐tech industries confronted with large‐scale and complex production planning problems. We present two algorithms to solve the allocation problem with ordering constraints. The first one uses characterization of the optimal decision variables to apply a search method. The second algorithm solves a sequence of problems, each in the format of the original problem without ordering constraints. Whereas the computational effort of the first algorithm depends on the desired degree of accuracy even for linear performance functions, the effort of the latter algorithm is polynomial for certain classes of performance functions. © 1994 John Wiley & Sons, Inc.

Suggested Citation

  • Lisa M. Betts & J. Randall Brown & Hanan Luss, 1994. "Minimax resource allocation problems with ordering constraints," Naval Research Logistics (NRL), John Wiley & Sons, vol. 41(6), pages 719-738, October.
  • Handle: RePEc:wly:navres:v:41:y:1994:i:6:p:719-738
    DOI: 10.1002/1520-6750(199410)41:63.0.CO;2-J
    as

    Download full text from publisher

    File URL: https://doi.org/10.1002/1520-6750(199410)41:63.0.CO;2-J
    Download Restriction: no

    File URL: https://libkey.io/10.1002/1520-6750(199410)41:63.0.CO;2-J?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
    ---><---

    References listed on IDEAS

    as
    1. Luss, Hanan, 1992. "Minimax resource allocation problems: Optimization and parametric analysis," European Journal of Operational Research, Elsevier, vol. 60(1), pages 76-86, July.
    2. Hanan Luss & Donald R. Smith, 1988. "Multiperiod allocation of limited resources: A minimax approach," Naval Research Logistics (NRL), John Wiley & Sons, vol. 35(4), pages 493-501, August.
    3. Czuchra, Waldemar, 1986. "A graphical method to solve a maximin allocation problem," European Journal of Operational Research, Elsevier, vol. 26(2), pages 259-261, August.
    4. J. Randall Brown, 1979. "The Knapsack Sharing Problem," Operations Research, INFORMS, vol. 27(2), pages 341-355, April.
    5. Vidal, ReneVictor Valqui, 1984. "A graphical method to solve a family of allocation problems," European Journal of Operational Research, Elsevier, vol. 17(1), pages 31-34, July.
    Full references (including those not matched with items on IDEAS)

    Citations

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


    Cited by:

    1. Hanan Luss, 2008. "An Equitable Bandwidth Allocation Model for Video-on-Demand Networks," Networks and Spatial Economics, Springer, vol. 8(1), pages 23-41, March.
    2. 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.
    3. Gang Liu & Weiqian Wang & Kevin W. Li, 2019. "Water Footprint Allocation under Equity and Efficiency Considerations: A Case Study of the Yangtze River Economic Belt in China," IJERPH, MDPI, vol. 16(5), pages 1-24, March.
    4. Hanan Luss, 1999. "On Equitable Resource Allocation Problems: A Lexicographic Minimax Approach," Operations Research, INFORMS, vol. 47(3), pages 361-378, June.

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Hanan Luss, 1999. "On Equitable Resource Allocation Problems: A Lexicographic Minimax Approach," Operations Research, INFORMS, vol. 47(3), pages 361-378, June.
    2. Fujimoto, Masako & Yamada, Takeo, 2006. "An exact algorithm for the knapsack sharing problem with common items," European Journal of Operational Research, Elsevier, vol. 171(2), pages 693-707, June.
    3. Yamada, Takeo & Futakawa, Mayumi & Kataoka, Seiji, 1998. "Some exact algorithms for the knapsack sharing problem," European Journal of Operational Research, Elsevier, vol. 106(1), pages 177-183, April.
    4. 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.
    5. Patriksson, Michael, 2008. "A survey on the continuous nonlinear resource allocation problem," European Journal of Operational Research, Elsevier, vol. 185(1), pages 1-46, February.
    6. Mhand Hifi & Slim Sadfi, 2002. "The Knapsack Sharing Problem: An Exact Algorithm," Journal of Combinatorial Optimization, Springer, vol. 6(1), pages 35-54, March.
    7. Mhand Hifi & Slim Sadfi & Abdelkader Sbihi, 2004. "An Exact Algorithm for the Multiple-choice Multidimensional Knapsack Problem," Post-Print halshs-03322716, HAL.
    8. B. Golany & N. Goldberg & U. Rothblum, 2015. "Allocating multiple defensive resources in a zero-sum game setting," Annals of Operations Research, Springer, vol. 225(1), pages 91-109, February.
    9. Hervé Moulin & Jay Sethuraman, 2013. "The Bipartite Rationing Problem," Operations Research, INFORMS, vol. 61(5), pages 1087-1100, October.
    10. Sbihi, Abdelkader, 2010. "A cooperative local search-based algorithm for the Multiple-Scenario Max-Min Knapsack Problem," European Journal of Operational Research, Elsevier, vol. 202(2), pages 339-346, April.
    11. Pursals, Salvador Casadesús & Garzón, Federico Garriga, 2009. "Optimal building evacuation time considering evacuation routes," European Journal of Operational Research, Elsevier, vol. 192(2), pages 692-699, January.
    12. Hanan Luss & Donald R. Smith, 1988. "Multiperiod allocation of limited resources: A minimax approach," Naval Research Logistics (NRL), John Wiley & Sons, vol. 35(4), pages 493-501, August.
    13. Mhand Hifi & Slim Sadfi & Abdelkader Sbihi, 2004. "An Exact Algorithm for the Multiple-choice Multidimensional Knapsack Problem," Université Paris1 Panthéon-Sorbonne (Post-Print and Working Papers) halshs-03322716, HAL.
    14. Hanan Luss, 2008. "An Equitable Bandwidth Allocation Model for Video-on-Demand Networks," Networks and Spatial Economics, Springer, vol. 8(1), pages 23-41, March.
    15. Muralidharan S. Kodialam & Hanan Luss, 1998. "Algorithms for Separable Nonlinear Resource Allocation Problems," Operations Research, INFORMS, vol. 46(2), pages 272-284, April.
    16. Amirgaliyeva, Zhazira & Mladenović, Nenad & Todosijević, Raca & Urošević, Dragan, 2017. "Solving the maximum min-sum dispersion by alternating formulations of two different problems," European Journal of Operational Research, Elsevier, vol. 260(2), pages 444-459.
    17. Ahuja, Ravindra K., 1997. "The balanced linear programming problem," European Journal of Operational Research, Elsevier, vol. 101(1), pages 29-38, August.
    18. Łukasz Kruk, 2020. "Continuity and monotonicity of solutions to a greedy maximization problem," Mathematical Methods of Operations Research, Springer;Gesellschaft für Operations Research (GOR);Nederlands Genootschap voor Besliskunde (NGB), vol. 92(1), pages 33-76, August.
    19. Hanan Luss & Moshe B. Rosenwein, 1995. "Multiperiod resource allocation with a smoothing objective," Naval Research Logistics (NRL), John Wiley & Sons, vol. 42(7), pages 1007-1020, October.
    20. Florian Biermann & Victor Naroditskiy & Maria Polukarov & Alex Rogers & Nicholas Jennings, 2011. "Task Assignment with Autonomous and Controlled Agents," Working Papers 004-11, International School of Economics at TSU, Tbilisi, Republic of Georgia.

    More about this item

    Statistics

    Access and download statistics

    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:wly:navres:v:41:y:1994:i:6:p:719-738. 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.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with 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: Wiley Content Delivery (email available below). General contact details of provider: https://doi.org/10.1002/(ISSN)1520-6750 .

    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.