IDEAS home Printed from https://ideas.repec.org/a/eee/ejores/v277y2019i2p492-506.html
   My bibliography  Save this article

Allocation under a general substitution structure

Author

Listed:
  • Tseytlin, Yulia
  • Heese, H. Sebastian

Abstract

We develop a novel solution approach for the single-period multi-product inventory allocation problem with general substitution structure. First, we construct an initial allocation sequence and present conditions for existence of a Monge sequence, implying optimality of a greedy solution. We prove that the greedy allocation along the initial sequence is optimal even if no Monge sequence exists, when in the solution all demand is satisfied and all inventory is used. For all other cases, we develop a correction algorithm and prove optimality of the resulting allocation. The worst-case computational complexity of our solution is superior to existing algorithms for the structurally related transportation problem.

Suggested Citation

  • Tseytlin, Yulia & Heese, H. Sebastian, 2019. "Allocation under a general substitution structure," European Journal of Operational Research, Elsevier, vol. 277(2), pages 492-506.
    • Handle: RePEc:eee:ejores:v:277:y:2019:i:2:p:492-506
    DOI: 10.1016/j.ejor.2019.02.049
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377221719302139
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.ejor.2019.02.049?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
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Arthur Hsu & Yehuda Bassok, 1999. "Random Yield and Random Demand in a Production System with Downward Substitution," Operations Research, INFORMS, vol. 47(2), pages 277-290, April.
    2. Burkard, Rainer E., 2007. "Monge properties, discrete convexity and applications," European Journal of Operational Research, Elsevier, vol. 176(1), pages 1-14, January.
    3. Shin, Hojung & Park, Soohoon & Lee, Euncheol & Benton, W.C., 2015. "A classification of the literature on the planning of substitutable products," European Journal of Operational Research, Elsevier, vol. 246(3), pages 686-699.
    4. Gabriel R. Bitran & Thin-Yin Leong, 1992. "Deterministic Approximations to Co-Production Problems with Service Constraints and Random Yields," Management Science, INFORMS, vol. 38(5), pages 724-742, May.
    5. Robert A. Shumsky & Fuqiang Zhang, 2009. "Dynamic Capacity Management with Substitution," Operations Research, INFORMS, vol. 57(3), pages 671-684, June.
    6. Yehuda Bassok & Ravi Anupindi & Ram Akella, 1999. "Single-Period Multiproduct Inventory Models with Substitution," Operations Research, INFORMS, vol. 47(4), pages 632-642, August.
    7. Maurice Queyranne & Frits Spieksma & Fabio Tardella, 1998. "A General Class of Greedily Solvable Linear Programs," Mathematics of Operations Research, INFORMS, vol. 23(4), pages 892-908, November.
    8. J. Christian Lang, 2010. "Production and Inventory Management with Substitutions," Lecture Notes in Economics and Mathematical Systems, Springer, number 978-3-642-04247-8, July.
    9. James B. Orlin, 1993. "A Faster Strongly Polynomial Minimum Cost Flow Algorithm," Operations Research, INFORMS, vol. 41(2), pages 338-350, April.
    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. Tseytlin, Yulia & Heese, H. Sebastian, 2023. "Inventory allocation with full downward substitution and monotone cost differences," European Journal of Operational Research, Elsevier, vol. 307(1), pages 130-139.
    2. He, Shuang & Zhang, Jian & Zhang, Juliang & Cheng, T.C.E., 2022. "Production/inventory competition between firms with fixed-proportions co-production systems," European Journal of Operational Research, Elsevier, vol. 299(2), pages 497-509.

    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. Qi Feng & Chengzhang Li & Mengshi Lu & Jeyaveerasingam George Shanthikumar, 2022. "Dynamic Substitution for Selling Multiple Products under Supply and Demand Uncertainties," Production and Operations Management, Production and Operations Management Society, vol. 31(4), pages 1645-1662, April.
    2. Tseytlin, Yulia & Heese, H. Sebastian, 2023. "Inventory allocation with full downward substitution and monotone cost differences," European Journal of Operational Research, Elsevier, vol. 307(1), pages 130-139.
    3. Hsieh, Chung-Chi & Lai, Hsing-Hua, 2020. "Pricing and ordering decisions in a supply chain with downward substitution and imperfect process yield," Omega, Elsevier, vol. 95(C).
    4. Youyi Feng & Jianjun Xu & Shaohui Zheng, 2019. "Technical Note—Dynamic Optimal Policy for an Inventory System of Two Substitutable Products with Positive Replenishment Lead Times," Operations Research, INFORMS, vol. 67(4), pages 1027-1034, July.
    5. Lu, Fen & Xu, He & Chen, Pengyu & Zhu, Stuart X., 2018. "Joint pricing and production decisions with yield uncertainty and downconversion," International Journal of Production Economics, Elsevier, vol. 197(C), pages 52-62.
    6. Zhang, Jie & Xie, Weijun & Sarin, Subhash C., 2021. "Robust multi-product newsvendor model with uncertain demand and substitution," European Journal of Operational Research, Elsevier, vol. 293(1), pages 190-202.
    7. Yao Cui & Izak Duenyas & Ozge Sahin, 2018. "Pricing of Conditional Upgrades in the Presence of Strategic Consumers," Management Science, INFORMS, vol. 64(7), pages 3208-3226, July.
    8. Freeman, Nickolas K. & Narayanan, Arunachalam & Keskin, Burcu B., 2021. "Optimal use of downward substitution in a manufacturing operation subject to uncertainty," Omega, Elsevier, vol. 103(C).
    9. Ying-Ju Chen & Brian Tomlin & Yimin Wang, 2013. "Coproduct Technologies: Product Line Design and Process Innovation," Management Science, INFORMS, vol. 59(12), pages 2772-2789, December.
    10. Saurabh Bansal & James S. Dyer, 2020. "Planning for End-User Substitution in Agribusiness," Operations Research, INFORMS, vol. 68(4), pages 1000-1019, July.
    11. Su, Ping & Tian, Zhongjun & Wang, Haiyan, 2012. "On service degrade at a discount: Capacity, demand pooling, and optimal discounting," Omega, Elsevier, vol. 40(3), pages 358-367.
    12. Jie Zhang & Weijun Xie & Subhash C. Sarin, 2021. "Multiproduct Newsvendor Problem with Customer-Driven Demand Substitution: A Stochastic Integer Program Perspective," INFORMS Journal on Computing, INFORMS, vol. 33(3), pages 1229-1244, July.
    13. Yueshan Yu & Xin Chen & Fuqiang Zhang, 2015. "Dynamic Capacity Management with General Upgrading," Operations Research, INFORMS, vol. 63(6), pages 1372-1389, December.
    14. Jan A. Van Mieghem & Nils Rudi, 2002. "Newsvendor Networks: Inventory Management and Capacity Investment with Discretionary Activities," Manufacturing & Service Operations Management, INFORMS, vol. 4(4), pages 313-335, August.
    15. Ozen, U. & Slikker, M. & Norde, H.W., 2007. "A General Framework for Cooperation under Uncertainty," Discussion Paper 2007-57, Tilburg University, Center for Economic Research.
    16. Deishin Lee, 2012. "Turning Waste into By-Product," Manufacturing & Service Operations Management, INFORMS, vol. 14(1), pages 115-127, January.
    17. 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.
    18. Transchel, Sandra, 2017. "Inventory management under price-based and stockout-based substitution," European Journal of Operational Research, Elsevier, vol. 262(3), pages 996-1008.
    19. Lu, Mengshi & Huang, Simin & Shen, Zuo-Jun Max, 2011. "Product substitution and dual sourcing under random supply failures," Transportation Research Part B: Methodological, Elsevier, vol. 45(8), pages 1251-1265, September.
    20. Han, Guanghua & Dong, Ming & Liu, Shaoxuan, 2014. "Yield and allocation management in a continuous make-to-stock system with demand upgrade substitution," International Journal of Production Economics, Elsevier, vol. 156(C), pages 124-131.

    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:eee:ejores:v:277:y:2019:i:2:p:492-506. 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: Catherine Liu (email available below). General contact details of provider: http://www.elsevier.com/locate/eor .

    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.