IDEAS home Printed from https://ideas.repec.org/a/eee/jomega/v71y2017icp85-92.html
   My bibliography  Save this article

Packing into designated and multipurpose bins: A theoretical study and application to the cold chain

Author

Listed:
  • Goldberg, Noam
  • Karhi, Shlomo

Abstract

We consider a multitype bin packing problem and focus on the particular case of an online setting with two types of items and three bin types: two designated bins and a multipurpose bin that can store both types of items. The flexibility of multipurpose bins comes at a greater cost per bin and the objective is to minimize the cost of bins used. First, we establish a competitive ratio lower bound for the unit size problem as a function of the bin cost parameters; over all bin costs the resulting worst-case competitive ratio is 1+52≈1.618. Next, we show that the first-fit algorithm׳s competitive ratio is tight (it equals the established lower bound) for the two-size standard bin packing problem (in the absence of item and bin types) with an absolute competitive ratio of 32. Then, we generalize our analysis for the problem with two item types, where each item type has a distinct size; the worst-case absolute competitive ratio is shown to be 1+52 as in the unit size case. Finally, we apply our results to analyze mixed load packing of perishable items given current spot prices of dry and refrigerated shipping containers.

Suggested Citation

  • Goldberg, Noam & Karhi, Shlomo, 2017. "Packing into designated and multipurpose bins: A theoretical study and application to the cold chain," Omega, Elsevier, vol. 71(C), pages 85-92.
  • Handle: RePEc:eee:jomega:v:71:y:2017:i:c:p:85-92
    DOI: 10.1016/j.omega.2016.09.010
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0305048316300883
    Download Restriction: Full text for ScienceDirect subscribers only

    File URL: https://libkey.io/10.1016/j.omega.2016.09.010?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. Shoshana Anily & Julien Bramel & David Simchi-Levi, 1994. "Worst-Case Analysis of Heuristics for the Bin Packing Problem with General Cost Structures," Operations Research, INFORMS, vol. 42(2), pages 287-298, April.
    2. Karhi, Shlomo & Shabtay, Dvir, 2014. "Online scheduling of two job types on a set of multipurpose machines," International Journal of Production Economics, Elsevier, vol. 150(C), pages 155-162.
    3. Bogataj, Marija & Bogataj, Ludvik & Vodopivec, Robert, 2005. "Stability of perishable goods in cold logistic chains," International Journal of Production Economics, Elsevier, vol. 93(1), pages 345-356, January.
    4. S. Thomas McCormick & Scott R. Smallwood & Frits C. R. Spieksma, 2001. "A Polynomial Algorithm for Multiprocessor Scheduling with Two Job Lengths," Mathematics of Operations Research, INFORMS, vol. 26(1), pages 31-49, February.
    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. Novas, Juan M. & Ramello, Juan Ignacio & Rodríguez, María Analía, 2020. "Generalized disjunctive programming models for the truck loading problem: A case study from the non-alcoholic beverages industry," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 140(C).
    2. Goldberg, Noam & Karhi, Shlomo, 2019. "Online packing of arbitrary sized items into designated and multipurpose bins," European Journal of Operational Research, Elsevier, vol. 279(1), pages 54-67.

    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. Thalis P. V. Zis & Harilaos N. Psaraftis, 2022. "Impacts of short-term measures to decarbonize maritime transport on perishable cargoes," Maritime Economics & Logistics, Palgrave Macmillan;International Association of Maritime Economists (IAME), vol. 24(3), pages 602-629, September.
    2. Ketzenberg, M.E. & Bloemhof-Ruwaard, J.M., 2009. "The Value of RFID Technology Enabled Information to Manage Perishables," ERIM Report Series Research in Management ERS-2009-020-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.
    3. Lin Hu & Qinghai Chen & Tingting Yang & Chuanjian Yi & Jing Chen, 2024. "Visualization and Analysis of Hotspots and Trends in Seafood Cold Chain Logistics Based on CiteSpace, VOSviewer, and RStudio Bibliometrix," Sustainability, MDPI, vol. 16(15), pages 1-22, July.
    4. N. Brauner & Y. Crama & A. Grigoriev & J. Klundert, 2005. "A Framework for the Complexity of High-Multiplicity Scheduling Problems," Journal of Combinatorial Optimization, Springer, vol. 9(3), pages 313-323, May.
    5. Nguyen Thi Nha Trang & Thanh-Thuy Nguyen & Hong V. Pham & Thi Thu Anh Cao & Thu Huong Trinh Thi & Javad Shahreki, 2022. "Impacts of Collaborative Partnership on the Performance of Cold Supply Chains of Agriculture and Foods: Literature Review," Sustainability, MDPI, vol. 14(11), pages 1-28, May.
    6. Songyi Wang & Fengming Tao & Yuhe Shi, 2018. "Optimization of Location–Routing Problem for Cold Chain Logistics Considering Carbon Footprint," IJERPH, MDPI, vol. 15(1), pages 1-17, January.
    7. Klaus Jansen & Roberto Solis-Oba, 2011. "A Polynomial Time OPT + 1 Algorithm for the Cutting Stock Problem with a Constant Number of Object Lengths," Mathematics of Operations Research, INFORMS, vol. 36(4), pages 743-753, November.
    8. Liu, D.S. & Tan, K.C. & Huang, S.Y. & Goh, C.K. & Ho, W.K., 2008. "On solving multiobjective bin packing problems using evolutionary particle swarm optimization," European Journal of Operational Research, Elsevier, vol. 190(2), pages 357-382, October.
    9. Ilyas Masudin & Anggi Ramadhani & Dian Palupi Restuputri & Ikhlasul Amallynda, 2021. "The Effect of Traceability System and Managerial Initiative on Indonesian Food Cold Chain Performance: A Covid-19 Pandemic Perspective," Global Journal of Flexible Systems Management, Springer;Global Institute of Flexible Systems Management, vol. 22(4), pages 331-356, December.
    10. Chung‐Lun Li & Zhi‐Long Chen, 2006. "Bin‐packing problem with concave costs of bin utilization," Naval Research Logistics (NRL), John Wiley & Sons, vol. 53(4), pages 298-308, June.
    11. Raut, Rakesh D. & Gardas, Bhaskar B. & Narwane, Vaibhav S. & Narkhede, Balkrishna E., 2019. "Improvement in the food losses in fruits and vegetable supply chain - a perspective of cold third-party logistics approach," Operations Research Perspectives, Elsevier, vol. 6(C).
    12. Clayton Gerber Mangini & Nilsa Duarte da Silva Lima & Irenilza de Alencar Nääs, 2024. "Risk Prediction Score for Thermal Mapping of Pharmaceutical Transport Routes in Brazil," Logistics, MDPI, vol. 8(3), pages 1-13, August.
    13. Hu, Qian & Wei, Lijun & Lim, Andrew, 2018. "The two-dimensional vector packing problem with general costs," Omega, Elsevier, vol. 74(C), pages 59-69.
    14. Filippi, Carlo, 2007. "On the bin packing problem with a fixed number of object weights," European Journal of Operational Research, Elsevier, vol. 181(1), pages 117-126, August.
    15. Leung, Joseph Y.-T. & Li, Chung-Lun, 2016. "Scheduling with processing set restrictions: A literature update," International Journal of Production Economics, Elsevier, vol. 175(C), pages 1-11.
    16. Braune, Roland, 2019. "Lower bounds for a bin packing problem with linear usage cost," European Journal of Operational Research, Elsevier, vol. 274(1), pages 49-64.
    17. Govindan, K. & Jafarian, A. & Khodaverdi, R. & Devika, K., 2014. "Two-echelon multiple-vehicle location–routing problem with time windows for optimization of sustainable supply chain network of perishable food," International Journal of Production Economics, Elsevier, vol. 152(C), pages 9-28.
    18. Rongqi Li & Zhiyi Tan & Qianyu Zhu, 2021. "Batch scheduling of nonidentical job sizes with minsum criteria," Journal of Combinatorial Optimization, Springer, vol. 42(3), pages 543-564, October.
    19. Jing Chen & Pengfei Gui & Tao Ding & Sanggyun Na & Yingtang Zhou, 2019. "Optimization of Transportation Routing Problem for Fresh Food by Improved Ant Colony Algorithm Based on Tabu Search," Sustainability, MDPI, vol. 11(23), pages 1-22, November.
    20. Esmizadeh, Yalda & Bashiri, Mahdi & Jahani, Hamed & Almada-Lobo, Bernardo, 2021. "Cold chain management in hierarchical operational hub networks," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 147(C).

    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:eee:jomega:v:71:y:2017:i:c:p:85-92. 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/wps/find/journaldescription.cws_home/375/description#description .

    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.