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

The Dynamic and Stochastic Knapsack Problem with Random Sized Items

Author

Listed:
  • Anton J. Kleywegt

    (School of Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta, Georgia 30332-0205)

  • Jason D. Papastavrou

    (School of Industrial Engineering, Purdue University, West Lafayette, Indiana 47907-1287)

Abstract

A resource allocation problem, called the dynamic and stochastic knapsack problem (DSKP), is studied. A known quantity of resource is available, and demands for the resource arrive randomly over time. Each demand requires an amount of resource and has an associated reward. The resource requirements and rewards are unknown before arrival and become known at the time of the demand's arrival. Demands can be either accepted or rejected. If a demand is accepted, the associated reward is received; if a demand is rejected, a penalty is incurred. The problem can be stopped at any time, at which time a terminal value is received that depends on the quantity of resource remaining. A holding cost that depends on the amount of resource allocated is incurred until the process is stopped. The objective is to determine an optimal policy for accepting demands and for stopping that maximizes the expected value (rewards minus costs) accumulated. The DSKP is analyzed for both the infinite horizon and the finite horizon cases. It is shown that the DSKP has an optimal policy that consists of an easily computed threshold acceptance rule and an optimal stopping rule. A number of monotonicity and convexity properties are studied. This problem is motivated by the issues facing a manager of an LTL transportation operation regarding the acceptance of loads and the dispatching of a vehicle. It also has applications in many other areas, such as the scheduling of batch processors, the selling of assets, the selection of investment projects, and yield management.

Suggested Citation

  • 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.
    • Handle: RePEc:inm:oropre:v:49:y:2001:i:1:p:26-41
    DOI: 10.1287/opre.49.1.26.11185
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/opre.49.1.26.11185
    Download Restriction: no
    File URL: https://libkey.io/10.1287/opre.49.1.26.11185?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. S. L. Brumelle & J. I. McGill, 1993. "Airline Seat Allocation with Multiple Nested Fare Classes," Operations Research, INFORMS, vol. 41(1), pages 127-137, February.
    2. Cyrus Derman & Gerald J. Lieberman & Sheldon M. Ross, 1972. "A Sequential Stochastic Assignment Problem," Management Science, INFORMS, vol. 18(7), pages 349-355, March.
    3. Guillermo Gallego & Garrett van Ryzin, 1994. "Optimal Dynamic Pricing of Inventories with Stochastic Demand over Finite Horizons," Management Science, INFORMS, vol. 40(8), pages 999-1020, August.
    4. S. Christian Albright, 1977. "A Bayesian Approach to a Generalized House Selling Problem," Management Science, INFORMS, vol. 24(4), pages 432-440, December.
    5. Anton J. Kleywegt & Jason D. Papastavrou, 1998. "The Dynamic and Stochastic Knapsack Problem," Operations Research, INFORMS, vol. 46(1), pages 17-35, February.
    6. Donald B. Rosenfield & Roy D. Shapiro & David A. Butler, 1983. "Optimal Strategies for Selling an Asset," Management Science, INFORMS, vol. 29(9), pages 1051-1061, September.
    7. John W. Mamer, 1986. "Successive Approximations for Finite Horizon, Semi-Markov Decision Processes with Application to Asset Liquidation," Operations Research, INFORMS, vol. 34(4), pages 638-644, August.
    8. Peter P. Belobaba, 1989. "OR Practice—Application of a Probabilistic Decision Model to Airline Seat Inventory Control," Operations Research, INFORMS, vol. 37(2), pages 183-197, April.
    9. Gregory P. Prastacos, 1983. "Optimal Sequential Investment Decisions Under Conditions of Uncertainty," Management Science, INFORMS, vol. 29(1), pages 118-134, January.
    10. 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.
    11. T. J. Stewart, 1981. "The Secretary Problem with an Unknown Number of Options," Operations Research, INFORMS, vol. 29(1), pages 130-145, February.
    12. Robert L. Carraway & Robert L. Schmidt & Lawrence R. Weatherford, 1993. "An algorithm for maximizing target achievement in the stochastic knapsack problem with normal returns," Naval Research Logistics (NRL), John Wiley & Sons, vol. 40(2), pages 161-173, March.
    13. Lawrence R. Weatherford & Samuel E. Bodily, 1992. "A Taxonomy and Research Overview of Perishable-Asset Revenue Management: Yield Management, Overbooking, and Pricing," Operations Research, INFORMS, vol. 40(5), pages 831-844, October.
    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. Anton J. Kleywegt & Jason D. Papastavrou, 1998. "The Dynamic and Stochastic Knapsack Problem," Operations Research, INFORMS, vol. 46(1), pages 17-35, February.
    2. Chatwin, Richard E., 2000. "Optimal dynamic pricing of perishable products with stochastic demand and a finite set of prices," European Journal of Operational Research, Elsevier, vol. 125(1), pages 149-174, August.
    3. Jeffrey I. McGill & Garrett J. van Ryzin, 1999. "Revenue Management: Research Overview and Prospects," Transportation Science, INFORMS, vol. 33(2), pages 233-256, May.
    4. Shelby Brumelle & Darius Walczak, 2003. "Dynamic Airline Revenue Management with Multiple Semi-Markov Demand," Operations Research, INFORMS, vol. 51(1), pages 137-148, February.
    5. Richard Van Slyke & Yi Young, 2000. "Finite Horizon Stochastic Knapsacks with Applications to Yield Management," Operations Research, INFORMS, vol. 48(1), pages 155-172, February.
    6. Kalyan Talluri & Garrett van Ryzin, 2000. "Revenue management under general discrete choice model of consumer behavior," Economics Working Papers 533, Department of Economics and Business, Universitat Pompeu Fabra, revised Oct 2001.
    7. Wang, Xiubin & Regan, Amelia, 2006. "Dynamic yield management when aircraft assignments are subject to swap," Transportation Research Part B: Methodological, Elsevier, vol. 40(7), pages 563-576, August.
    8. Yigao Liang, 1999. "Solution to the Continuous Time Dynamic Yield Management Model," Transportation Science, INFORMS, vol. 33(1), pages 117-123, February.
    9. 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.
    10. J. Neil Bearden & Ryan O. Murphy & Amnon Rapoport, 2008. "Decision Biases in Revenue Management: Some Behavioral Evidence," Manufacturing & Service Operations Management, INFORMS, vol. 10(4), pages 625-636, June.
    11. Youyi Feng & Baichun Xiao, 2001. "A Dynamic Airline Seat Inventory Control Model and Its Optimal Policy," Operations Research, INFORMS, vol. 49(6), pages 938-949, December.
    12. 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.
    13. Syed Asif Raza & Rafi Ashrafi & Ali Akgunduz, 2020. "A bibliometric analysis of revenue management in airline industry," Journal of Revenue and Pricing Management, Palgrave Macmillan, vol. 19(6), pages 436-465, December.
    14. Kalyan Talluri & Garrett van Ryzin, 2004. "Revenue Management Under a General Discrete Choice Model of Consumer Behavior," Management Science, INFORMS, vol. 50(1), pages 15-33, January.
    15. Kalyan Talluri & Garrett van Ryzin, 1998. "An Analysis of Bid-Price Controls for Network Revenue Management," Management Science, INFORMS, vol. 44(11-Part-1), pages 1577-1593, November.
    16. Feng, Youyi & Xiao, Baichun, 2006. "A continuous-time seat control model for single-leg flights with no-shows and optimal overbooking upper bound," European Journal of Operational Research, Elsevier, vol. 174(2), pages 1298-1316, October.
    17. You, Peng-Sheng, 2001. "Airline seat management with rejection-for-possible-upgrade decision," Transportation Research Part B: Methodological, Elsevier, vol. 35(5), pages 507-524, June.
    18. 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.
    19. Barut, M. & Sridharan, V, 2004. "Design and evaluation of a dynamic capacity apportionment procedure," European Journal of Operational Research, Elsevier, vol. 155(1), pages 112-133, May.
    20. Banerjee, Pradeep K. & Turner, T. Rolf, 2012. "A flexible model for the pricing of perishable assets," Omega, Elsevier, vol. 40(5), pages 533-540.

    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:49:y:2001:i:1:p:26-41. 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: 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.