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

The Surplus Inventory Matching Problem in the Process Industry

Author

Listed:
  • Jayant R. Kalagnanam

    (International Business Machines, T. J. Watson Research Center, Yorktown Heights, NY 10598)

  • Milind W. Dawande

    (International Business Machines, T. J. Watson Research Center, Yorktown Heights, NY 10598)

  • Mark Trumbo

    (International Business Machines, T. J. Watson Research Center, Yorktown Heights, NY 10598)

  • Ho Soo Lee

    (International Business Machines, T. J. Watson Research Center, Yorktown Heights, NY 10598)

Abstract

We introduce a new problem that arises from operations planning in the process industry. This problem involves matching an order book against surplus inventory before production planning. It can be formulated by generalizing the multiple knapsack problem along three dimensions: (i) adding assignment restrictions on items that can be assigned to a knapsack, (ii) adding a new attribute (called “color” in this paper) to an item and then adding the associated “color” constraints that restrict the number of distinct colors that can be assigned to a knapsack, and (iii) considering multiple objectives for optimization. We formulate the problem, provide a result regarding its complexity, and report on our computational experience with solving a set of real instances based on data from the operations of a large steel plant. We then propose a network-flow---based heuristic that yields solutions within 3% of optimal (or the best known feasible solution). This system has been successfully deployed and is now used daily in the mill operations.

Suggested Citation

  • Jayant R. Kalagnanam & Milind W. Dawande & Mark Trumbo & Ho Soo Lee, 2000. "The Surplus Inventory Matching Problem in the Process Industry," Operations Research, INFORMS, vol. 48(4), pages 505-516, August.
    • Handle: RePEc:inm:oropre:v:48:y:2000:i:4:p:505-516
    DOI: 10.1287/opre.48.4.505.12425
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/opre.48.4.505.12425
    Download Restriction: no
    File URL: https://libkey.io/10.1287/opre.48.4.505.12425?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. Martello, Silvano & Toth, Paolo, 1980. "Solution of the zero-one multiple knapsack problem," European Journal of Operational Research, Elsevier, vol. 4(4), pages 276-283, April.
    2. Michael A. Trick, 1992. "A linear relaxation heuristic for the generalized assignment problem," Naval Research Logistics (NRL), John Wiley & Sons, vol. 39(2), pages 137-151, March.
    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. P A Huegler & J C Hartman, 2007. "Fulfilling orders for steel plates from existing inventory," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 58(9), pages 1156-1166, September.
    2. Milind Dawande & Jayant Kalagnanam & Ho Soo Lee & Chandra Reddy & Stuart Siegel & Mark Trumbo, 2004. "The Slab-Design Problem in the Steel Industry," Interfaces, INFORMS, vol. 34(3), pages 215-225, June.
    3. Anantaram Balakrishnan & Joseph Geunes, 2003. "Production Planning with Flexible Product Specifications: An Application to Specialty Steel Manufacturing," Operations Research, INFORMS, vol. 51(1), pages 94-112, February.
    4. Morikawa, Katsumi & Takahashi, Katsuhiko & Hirotani, Daisuke, 2014. "Make-to-stock policies for a multistage serial system under a make-to-order production environment," International Journal of Production Economics, Elsevier, vol. 147(PA), pages 30-37.
    5. 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.
    6. Fernandes, Nuno O. & Silva, Cristóvão & Carmo-Silva, S., 2015. "Order release in the hybrid MTO–FTO production," International Journal of Production Economics, Elsevier, vol. 170(PB), pages 513-520.
    7. Lixin Tang & Ying Meng & Zhi-Long Chen & Jiyin Liu, 2016. "Coil Batching to Improve Productivity and Energy Utilization in Steel Production," Manufacturing & Service Operations Management, INFORMS, vol. 18(2), pages 262-279, May.
    8. Brian Denton & Diwakar Gupta & Keith Jawahir, 2003. "Managing Increasing Product Variety at Integrated Steel Mills," Interfaces, INFORMS, vol. 33(2), pages 41-53, April.
    9. Lixin Tang & Gongshu Wang & Zhi-Long Chen, 2014. "Integrated Charge Batching and Casting Width Selection at Baosteel," Operations Research, INFORMS, vol. 62(4), pages 772-787, August.
    10. John J. H. Forrest & Jayant Kalagnanam & Laszlo Ladanyi, 2006. "A Column-Generation Approach to the Multiple Knapsack Problem with Color Constraints," INFORMS Journal on Computing, INFORMS, vol. 18(1), pages 129-134, February.
    11. Lixin Tang & Ying Meng & Gongshu Wang & Zhi-Long Chen & Jiyin Liu & Guofen Hu & Lijun Chen & Bo Zhang, 2014. "Operations Research Transforms Baosteel’s Operations," Interfaces, INFORMS, vol. 44(1), pages 22-38, February.
    12. Chris Clifton & Ananth Iyer & Richard Cho & Wei Jiang & Murat Kantarc{i}ou{g}lu & Jaideep Vaidya, 2008. "An Approach to Securely Identifying Beneficial Collaboration in Decentralized Logistics Systems," Manufacturing & Service Operations Management, INFORMS, vol. 10(1), pages 108-125, January.
    13. F J Vasko & D D Newhart & K L Stott & F E Wolf, 2003. "A large-scale application of the partial coverage uncapacitated facility location problem," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 54(1), pages 11-20, January.
    14. Zanoni, Simone & Zavanella, Lucio, 2005. "Model and analysis of integrated production-inventory system: The case of steel production," International Journal of Production Economics, Elsevier, vol. 93(1), pages 197-205, January.
    15. Laszlo Ladanyi & Jon Lee & Robin Lougee-Heimer, 2005. "Rapid Prototyping of Optimization Algorithms Using COIN-OR: A Case Study Involving the Cutting-Stock Problem," Annals of Operations Research, Springer, vol. 139(1), pages 243-265, October.

    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. Mutsunori Yagiura & Toshihide Ibaraki & Fred Glover, 2004. "An Ejection Chain Approach for the Generalized Assignment Problem," INFORMS Journal on Computing, INFORMS, vol. 16(2), pages 133-151, May.
    2. Dell’Amico, Mauro & Delorme, Maxence & Iori, Manuel & Martello, Silvano, 2019. "Mathematical models and decomposition methods for the multiple knapsack problem," European Journal of Operational Research, Elsevier, vol. 274(3), pages 886-899.
    3. H. Edwin Romeijn & Dolores Romero Morales, 2003. "An asymptotically optimal greedy heuristic for the multiperiod single‐sourcing problem: The cyclic case," Naval Research Logistics (NRL), John Wiley & Sons, vol. 50(5), pages 412-437, August.
    4. Johnston, Robert E. & Khan, Lutfar R., 1995. "Bounds for nested knapsack problems," European Journal of Operational Research, Elsevier, vol. 81(1), pages 154-165, February.
    5. Christopher Hojny & Tristan Gally & Oliver Habeck & Hendrik Lüthen & Frederic Matter & Marc E. Pfetsch & Andreas Schmitt, 2020. "Knapsack polytopes: a survey," Annals of Operations Research, Springer, vol. 292(1), pages 469-517, September.
    6. M. Dawande & J. Kalagnanam & P. Keskinocak & F.S. Salman & R. Ravi, 2000. "Approximation Algorithms for the Multiple Knapsack Problem with Assignment Restrictions," Journal of Combinatorial Optimization, Springer, vol. 4(2), pages 171-186, June.
    7. Olivier Lalonde & Jean-François Côté & Bernard Gendron, 2022. "A Branch-and-Price Algorithm for the Multiple Knapsack Problem," INFORMS Journal on Computing, INFORMS, vol. 34(6), pages 3134-3150, November.
    8. Hellsten, Erik Orm & Sacramento, David & Pisinger, David, 2020. "An adaptive large neighbourhood search heuristic for routing and scheduling feeder vessels in multi-terminal ports," European Journal of Operational Research, Elsevier, vol. 287(2), pages 682-698.
    9. Charles H. Reilly, 2009. "Synthetic Optimization Problem Generation: Show Us the Correlations!," INFORMS Journal on Computing, INFORMS, vol. 21(3), pages 458-467, August.
    10. H. Edwin Romeijn & Dolores Romero Morales, 2001. "Generating Experimental Data for the Generalized Assignment Problem," Operations Research, INFORMS, vol. 49(6), pages 866-878, December.
    11. Zhou, Qing & Hao, Jin-Kao & Wu, Qinghua, 2022. "A hybrid evolutionary search for the generalized quadratic multiple knapsack problem," European Journal of Operational Research, Elsevier, vol. 296(3), pages 788-803.
    12. Joseph B. Mazzola & Steven P. Wilcox, 2001. "Heuristics for the multi‐resource generalized assignment problem," Naval Research Logistics (NRL), John Wiley & Sons, vol. 48(6), pages 468-483, September.

    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:48:y:2000:i:4:p:505-516. 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.