IDEAS home Printed from https://ideas.repec.org/a/inm/orinte/v52y2022i3p283-294.html
   My bibliography  Save this article

Developing a Maximum Inscribed Rectangle Heuristic to Satisfy Rush Orders for Heavy Plate Steel

Author

Listed:
  • M. Muntazir Mehdi

    (Microsoft Corporation, Redmond, Washington 98052)

  • Le Wang

    (Amazon.com, Seattle, Washington 98109)

  • Sean P. Willems

    (Haslam College of Business, University of Tennessee, Knoxville, Tennessee 37996)

Abstract

Steel service centers receive rush orders that must be fulfilled on very short notice. Each order only consumes a portion of one steel plate, so plate selection and job placement are the critical factors that affect the service center’s primary performance metric: plate yield. In conjunction with a steel service center, Artco Steel, we model this problem as a two-dimensional online bin-packing algorithm. Unique in the online bin-packing literature, we calculate the maximum inscribed rectangle (MIR) before and after job placement as the basis for heuristics that assign each job to a plate and position the job on the plate. Our work is the first paper to extend the online two-dimensional bin-packing problem to incorporate scrap, rectangular bin sizes, and a finite number of bins. The MIR procedure significantly outperformed Artco’s existing practice of giving priority to the most recently used plate, and the heuristic’s straightforward nature allowed easy adoption in 2010.

Suggested Citation

  • M. Muntazir Mehdi & Le Wang & Sean P. Willems, 2022. "Developing a Maximum Inscribed Rectangle Heuristic to Satisfy Rush Orders for Heavy Plate Steel," Interfaces, INFORMS, vol. 52(3), pages 283-294, May.
    • Handle: RePEc:inm:orinte:v:52:y:2022:i:3:p:283-294
    DOI: 10.1287/inte.2021.1086
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/inte.2021.1086
    Download Restriction: no
    File URL: https://libkey.io/10.1287/inte.2021.1086?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. Nicos Christofides & Charles Whitlock, 1977. "An Algorithm for Two-Dimensional Cutting Problems," Operations Research, INFORMS, vol. 25(1), pages 30-44, February.
    2. Wascher, Gerhard & Hau[ss]ner, Heike & Schumann, Holger, 2007. "An improved typology of cutting and packing problems," European Journal of Operational Research, Elsevier, vol. 183(3), pages 1109-1130, December.
    3. P. C. Gilmore & R. E. Gomory, 1961. "A Linear Programming Approach to the Cutting-Stock Problem," Operations Research, INFORMS, vol. 9(6), pages 849-859, December.
    4. Andrea Lodi & Silvano Martello & Daniele Vigo, 1999. "Heuristic and Metaheuristic Approaches for a Class of Two-Dimensional Bin Packing Problems," INFORMS Journal on Computing, INFORMS, vol. 11(4), pages 345-357, November.
    5. Silvano Martello & Daniele Vigo, 1998. "Exact Solution of the Two-Dimensional Finite Bin Packing Problem," Management Science, INFORMS, vol. 44(3), pages 388-399, March.
    6. 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.
    7. Mark A. Vonderembse & Robert W. Haessler, 1982. "A Mathematical Programming Approach to Schedule Master Slab Casters in the Steel Industry," Management Science, INFORMS, vol. 28(12), pages 1450-1461, December.
    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. Iori, Manuel & de Lima, Vinícius L. & Martello, Silvano & Miyazawa, Flávio K. & Monaci, Michele, 2021. "Exact solution techniques for two-dimensional cutting and packing," European Journal of Operational Research, Elsevier, vol. 289(2), pages 399-415.
    2. Felix Prause & Kai Hoppmann-Baum & Boris Defourny & Thorsten Koch, 2021. "The maximum diversity assortment selection problem," Mathematical Methods of Operations Research, Springer;Gesellschaft für Operations Research (GOR);Nederlands Genootschap voor Besliskunde (NGB), vol. 93(3), pages 521-554, June.
    3. Nestor M Cid-Garcia & Yasmin A Rios-Solis, 2020. "Positions and covering: A two-stage methodology to obtain optimal solutions for the 2d-bin packing problem," PLOS ONE, Public Library of Science, vol. 15(4), pages 1-22, April.
    4. Ortmann, Frank G. & Ntene, Nthabiseng & van Vuuren, Jan H., 2010. "New and improved level heuristics for the rectangular strip packing and variable-sized bin packing problems," European Journal of Operational Research, Elsevier, vol. 203(2), pages 306-315, June.
    5. Schmid, Verena & Doerner, Karl F. & Laporte, Gilbert, 2013. "Rich routing problems arising in supply chain management," European Journal of Operational Research, Elsevier, vol. 224(3), pages 435-448.
    6. Gregory S. Taylor & Yupo Chan & Ghulam Rasool, 2017. "A three-dimensional bin-packing model: exact multicriteria solution and computational complexity," Annals of Operations Research, Springer, vol. 251(1), pages 397-427, April.
    7. Bayliss, Christopher & Currie, Christine S.M. & Bennell, Julia A. & Martinez-Sykora, Antonio, 2021. "Queue-constrained packing: A vehicle ferry case study," European Journal of Operational Research, Elsevier, vol. 289(2), pages 727-741.
    8. Melega, Gislaine Mara & de Araujo, Silvio Alexandre & Jans, Raf, 2018. "Classification and literature review of integrated lot-sizing and cutting stock problems," European Journal of Operational Research, Elsevier, vol. 271(1), pages 1-19.
    9. Lodi, Andrea & Martello, Silvano & Monaci, Michele, 2002. "Two-dimensional packing problems: A survey," European Journal of Operational Research, Elsevier, vol. 141(2), pages 241-252, September.
    10. Wei, Lijun & Oon, Wee-Chong & Zhu, Wenbin & Lim, Andrew, 2011. "A skyline heuristic for the 2D rectangular packing and strip packing problems," European Journal of Operational Research, Elsevier, vol. 215(2), pages 337-346, December.
    11. Michele Monaci & Paolo Toth, 2006. "A Set-Covering-Based Heuristic Approach for Bin-Packing Problems," INFORMS Journal on Computing, INFORMS, vol. 18(1), pages 71-85, February.
    12. Krzysztof Fleszar, 2016. "An Exact Algorithm for the Two-Dimensional Stage-Unrestricted Guillotine Cutting/Packing Decision Problem," INFORMS Journal on Computing, INFORMS, vol. 28(4), pages 703-720, November.
    13. Wei, Lijun & Tian, Tian & Zhu, Wenbin & Lim, Andrew, 2014. "A block-based layer building approach for the 2D guillotine strip packing problem," European Journal of Operational Research, Elsevier, vol. 239(1), pages 58-69.
    14. Silvano Martello & Michele Monaci & Daniele Vigo, 2003. "An Exact Approach to the Strip-Packing Problem," INFORMS Journal on Computing, INFORMS, vol. 15(3), pages 310-319, August.
    15. Lei Wang & Aihua Yin, 2016. "A quasi-human algorithm for the two dimensional rectangular strip packing problem: in memory of Prof. Wenqi Huang," Journal of Combinatorial Optimization, Springer, vol. 32(2), pages 416-444, August.
    16. Puchinger, Jakob & Raidl, Gunther R., 2007. "Models and algorithms for three-stage two-dimensional bin packing," European Journal of Operational Research, Elsevier, vol. 183(3), pages 1304-1327, December.
    17. Önder Aşık & Ender Özcan, 2009. "Bidirectional best-fit heuristic for orthogonal rectangular strip packing," Annals of Operations Research, Springer, vol. 172(1), pages 405-427, November.
    18. Hadjiconstantinou, Eleni & Iori, Manuel, 2007. "A hybrid genetic algorithm for the two-dimensional single large object placement problem," European Journal of Operational Research, Elsevier, vol. 183(3), pages 1150-1166, December.
    19. Andreas Bortfeldt & Sabine Jungmann, 2012. "A tree search algorithm for solving the multi-dimensional strip packing problem with guillotine cutting constraint," Annals of Operations Research, Springer, vol. 196(1), pages 53-71, July.
    20. Gonçalves, José Fernando & Resende, Mauricio G.C., 2013. "A biased random key genetic algorithm for 2D and 3D bin packing problems," International Journal of Production Economics, Elsevier, vol. 145(2), pages 500-510.

    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:orinte:v:52:y:2022:i:3:p:283-294. 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.