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

The dynamic and stochastic knapsack Problem with homogeneous‐sized items and postponement options

Author

Listed:
  • Tianke Feng
  • Joseph C. Hartman

Abstract

This article generalizes the dynamic and stochastic knapsack problem by allowing the decision‐maker to postpone the accept/reject decision for an item and maintain a queue of waiting items to be considered later. Postponed decisions are penalized with delay costs, while idle capacity incurs a holding cost. This generalization addresses applications where requests of scarce resources can be delayed, for example, dispatching in logistics and allocation of funding to investments. We model the problem as a Markov decision process and analyze it through dynamic programming. We show that the optimal policy with homogeneous‐sized items possesses a bithreshold structure, despite the high dimensionality of the decision space. Finally, the value (or price) of postponement is illustrated through numerical examples. © 2015 Wiley Periodicals, Inc. Naval Research Logistics 62: 267–292, 2015

Suggested Citation

  • Tianke Feng & Joseph C. Hartman, 2015. "The dynamic and stochastic knapsack Problem with homogeneous‐sized items and postponement options," Naval Research Logistics (NRL), John Wiley & Sons, vol. 62(4), pages 267-292, June.
    • Handle: RePEc:wly:navres:v:62:y:2015:i:4:p:267-292
    DOI: 10.1002/nav.21627
    as

    Download full text from publisher

    File URL: https://doi.org/10.1002/nav.21627
    Download Restriction: no
    File URL: https://libkey.io/10.1002/nav.21627?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. Cyrus Derman & Gerald J. Lieberman & Sheldon M. Ross, 1972. "A Sequential Stochastic Assignment Problem," Management Science, INFORMS, vol. 18(7), pages 349-355, March.
    2. Rhonda Righter, 1989. "A Resource Allocation Problem in a Random Environment," Operations Research, INFORMS, vol. 37(2), pages 329-338, April.
    3. Katerina P. Papadaki & Warren B. Powell, 2003. "An adaptive dynamic programming algorithm for a stochastic multiproduct batch dispatch problem," Naval Research Logistics (NRL), John Wiley & Sons, vol. 50(7), pages 742-769, October.
    4. Grenadier, Steven R. & Weiss, Allen M., 1997. "Investment in technological innovations: An option pricing approach," Journal of Financial Economics, Elsevier, vol. 44(3), pages 397-416, June.
    5. S. Christian Albright, 1974. "Optimal Sequential Assignments with Random Arrival Times," Management Science, INFORMS, vol. 21(1), pages 60-67, September.
    6. Anton J. Kleywegt & Jason D. Papastavrou, 1998. "The Dynamic and Stochastic Knapsack Problem," Operations Research, INFORMS, vol. 46(1), pages 17-35, February.
    7. Alexander G. Nikolaev & Sheldon H. Jacobson, 2010. "Technical Note ---Stochastic Sequential Decision-Making with a Random Number of Jobs," Operations Research, INFORMS, vol. 58(4-part-1), pages 1023-1027, August.
    8. Toru Nakai, 1986. "A Sequential Stochastic Assignment Problem in a Partially Observable Markov Chain," Mathematics of Operations Research, INFORMS, vol. 11(2), pages 230-240, May.
    9. Jason D. Papastavrou & Srikanth Rajagopalan & Anton J. Kleywegt, 1996. "The Dynamic and Stochastic Knapsack Problem with Deadlines," Management Science, INFORMS, vol. 42(12), pages 1706-1718, December.
    10. L L Lu & S Y Chiu & L A Cox, 1999. "Optimal project selection: Stochastic knapsack with finite time horizon," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 50(6), pages 645-650, June.
    11. Michael Z. Spivey & Warren B. Powell, 2004. "The Dynamic Assignment Problem," Transportation Science, INFORMS, vol. 38(4), pages 399-419, November.
    12. Laura McLay & Sheldon Jacobson & Alexander Nikolaev, 2009. "A sequential stochastic passenger screening problem for aviation security," IISE Transactions, Taylor & Francis Journals, vol. 41(6), pages 575-591.
    13. Anton J. Kleywegt & Jason D. Papastavrou, 2001. "The Dynamic and Stochastic Knapsack Problem with Random Sized Items," Operations Research, INFORMS, vol. 49(1), pages 26-41, February.
    14. Robert McDonald & Daniel Siegel, 1986. "The Value of Waiting to Invest," The Quarterly Journal of Economics, President and Fellows of Harvard College, vol. 101(4), pages 707-727.
    15. S. Christian Albright, 1977. "A Bayesian Approach to a Generalized House Selling Problem," Management Science, INFORMS, vol. 24(4), pages 432-440, December.
    16. Jade Herbots & Willy Herroelen & Roel Leus, 2007. "Dynamic order acceptance and capacity planning on a single bottleneck resource," Naval Research Logistics (NRL), John Wiley & Sons, vol. 54(8), pages 874-889, December.
    17. Qing Ding & Lingxiu Dong & Panos Kouvelis, 2007. "On the Integration of Production and Financial Hedging Decisions in Global Markets," Operations Research, INFORMS, vol. 55(3), pages 470-489, June.
    18. Brian C. Dean & Michel X. Goemans & Jan Vondrák, 2008. "Approximating the Stochastic Knapsack Problem: The Benefit of Adaptivity," Mathematics of Operations Research, INFORMS, vol. 33(4), pages 945-964, November.
    19. Alexander J. Triantis, 2000. "Real Options And Corporate Risk Management," Journal of Applied Corporate Finance, Morgan Stanley, vol. 13(2), pages 64-73, June.
    20. D. P. Kennedy, 1986. "Optimal Sequential Assignment," Mathematics of Operations Research, INFORMS, vol. 11(4), pages 619-626, November.
    Full references (including those not matched with items on IDEAS)

    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. Alexander G. Nikolaev & Sheldon H. Jacobson, 2010. "Technical Note ---Stochastic Sequential Decision-Making with a Random Number of Jobs," Operations Research, INFORMS, vol. 58(4-part-1), pages 1023-1027, August.
    2. Arash Khatibi & Sheldon H. Jacobson, 2016. "Doubly Stochastic Sequential Assignment Problem," Naval Research Logistics (NRL), John Wiley & Sons, vol. 63(2), pages 124-137, March.
    3. Xuanming Su & Stefanos A. Zenios, 2005. "Patient Choice in Kidney Allocation: A Sequential Stochastic Assignment Model," Operations Research, INFORMS, vol. 53(3), pages 443-455, June.
    4. Meghan Shanks & Ge Yu & Sheldon H. Jacobson, 2023. "Approximation algorithms for stochastic online matching with reusable resources," Mathematical Methods of Operations Research, Springer;Gesellschaft für Operations Research (GOR);Nederlands Genootschap voor Besliskunde (NGB), vol. 98(1), pages 43-56, August.
    5. Arash Khatibi & Golshid Baharian & Banafsheh Behzad & Sheldon Jacobson, 2015. "Extensions of the sequential stochastic assignment problem," Mathematical Methods of Operations Research, Springer;Gesellschaft für Operations Research (GOR);Nederlands Genootschap voor Besliskunde (NGB), vol. 82(3), pages 317-340, December.
    6. David T. Wu & Sheldon M. Ross, 2015. "A stochastic assignment problem," Naval Research Logistics (NRL), John Wiley & Sons, vol. 62(1), pages 23-31, February.
    7. Soumia Ichoua & Michel Gendreau & Jean-Yves Potvin, 2006. "Exploiting Knowledge About Future Demands for Real-Time Vehicle Dispatching," Transportation Science, INFORMS, vol. 40(2), pages 211-225, May.
    8. , & , & ,, 2011. "Revenue maximization in the dynamic knapsack problem," Theoretical Economics, Econometric Society, vol. 6(2), May.
    9. David, Israel & Levi, Ofer, 2004. "A new algorithm for the multi-item exponentially discounted optimal selection problem," European Journal of Operational Research, Elsevier, vol. 153(3), pages 782-789, March.
    10. Anton J. Kleywegt & Jason D. Papastavrou, 1998. "The Dynamic and Stochastic Knapsack Problem," Operations Research, INFORMS, vol. 46(1), pages 17-35, February.
    11. Anton J. Kleywegt & Jason D. Papastavrou, 2001. "The Dynamic and Stochastic Knapsack Problem with Random Sized Items," Operations Research, INFORMS, vol. 49(1), pages 26-41, February.
    12. Grace Y. Lin & Yingdong Lu & David D. Yao, 2008. "The Stochastic Knapsack Revisited: Switch-Over Policies and Dynamic Pricing," Operations Research, INFORMS, vol. 56(4), pages 945-957, August.
    13. C G Lennon & J M McGowan & K Y Lin, 2008. "A game-theoretic model for repeated assignment problem between two selfish agents," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 59(12), pages 1652-1658, December.
    14. Huanan Zhang & Cong Shi & Chao Qin & Cheng Hua, 2016. "Stochastic regret minimization for revenue management problems with nonstationary demands," Naval Research Logistics (NRL), John Wiley & Sons, vol. 63(6), pages 433-448, September.
    15. Baris Ata & Yichuan Ding & Stefanos Zenios, 2021. "An Achievable-Region-Based Approach for Kidney Allocation Policy Design with Endogenous Patient Choice," Manufacturing & Service Operations Management, INFORMS, vol. 23(1), pages 36-54, 1-2.
    16. Lim, Terence & Lo, Andrew W. & Merton, Robert C. & Scholes, Myron S., 2006. "The Derivatives Sourcebook," Foundations and Trends(R) in Finance, now publishers, vol. 1(5–6), pages 365-572, April.
    17. So, Mee Chi & Thomas, Lyn C. & Huang, Bo, 2016. "Lending decisions with limits on capital available: The polygamous marriage problem," European Journal of Operational Research, Elsevier, vol. 249(2), pages 407-416.
    18. Clifford Stein & Van-Anh Truong & Xinshang Wang, 2020. "Advance Service Reservations with Heterogeneous Customers," Management Science, INFORMS, vol. 66(7), pages 2929-2950, July.
    19. Shelby Brumelle & Darius Walczak, 2003. "Dynamic Airline Revenue Management with Multiple Semi-Markov Demand," Operations Research, INFORMS, vol. 51(1), pages 137-148, February.
    20. Pak, K. & Dekker, R., 2004. "Cargo Revenue Management: Bid-Prices for a 0-1 Multi Knapsack Problem," ERIM Report Series Research in Management ERS-2004-055-LIS, Erasmus Research Institute of Management (ERIM), ERIM is the joint research institute of the Rotterdam School of Management, Erasmus University and the Erasmus School of Economics (ESE) at Erasmus University Rotterdam.

    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:62:y:2015:i:4:p:267-292. 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.