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

Online packing of arbitrary sized items into designated and multipurpose bins

Author

Listed:
  • Goldberg, Noam
  • Karhi, Shlomo

Abstract

We consider an online multitype bin-packing problem with two item types. This setting can be motivated by transport applications in which some items may be shipped either in dry shipping containers or more costly refrigerated ones, while other items can only be transported in refrigerated containers. The problem was introduced by Goldberg and Karhi [Omega 71:85-92, 2017] who focused on the case of up to two item types, three bin types and only two item sizes. For this special case a tight (also known as optimal) absolute competitive ratio was shown of approximately 1.618. Here we consider the general problem of arbitrary item sizes and show a lower bound on the absolute competitive ratio of any online algorithm that is a function of the bin costs. This bound in the worst-case is approximately 1.781. We then extend the first-fit method to our problem setting and prove an absolute competitive ratio bound that is a function of the bin costs. In the worst case this upper bound is approximately 1.930. In addition an upper bound of 1.750 is established on the worst-case asymptotic (as the number of items grows large) competitive ratio.

Suggested Citation

  • 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.
    • Handle: RePEc:eee:ejores:v:279:y:2019:i:1:p:54-67
    DOI: 10.1016/j.ejor.2019.05.029
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377221719304461
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.ejor.2019.05.029?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. Hans Kellerer & Joseph Y.‐T. Leung & Chung‐Lun Li, 2011. "Multiple subset sum with inclusive assignment set restrictions," Naval Research Logistics (NRL), John Wiley & Sons, vol. 58(6), pages 546-563, September.
    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. Kang, Jangha & Park, Sungsoo, 2003. "Algorithms for the variable sized bin packing problem," European Journal of Operational Research, Elsevier, vol. 147(2), pages 365-372, June.
    4. Gerard M. Campbell, 1999. "Cross-Utilization of Workers Whose Capabilities Differ," Management Science, INFORMS, vol. 45(5), pages 722-732, May.
    5. Shlomo Karhi & Dvir Shabtay, 2013. "On the optimality of the TLS algorithm for solving the online-list scheduling problem with two job types on a set of multipurpose machines," Journal of Combinatorial Optimization, Springer, vol. 26(1), pages 198-222, July.
    6. 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.
    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. Lin, Qi & Zhao, Qiuhong & Lev, Benjamin, 2020. "Cold chain transportation decision in the vaccine supply chain," European Journal of Operational Research, Elsevier, vol. 283(1), pages 182-195.

    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. Xueqi Wu & Zhi‐Long Chen, 2022. "Fulfillment scheduling for buy‐online‐pickup‐in‐store orders," Production and Operations Management, Production and Operations Management Society, vol. 31(7), pages 2982-3003, July.
    2. 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.
    3. 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.
    4. 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).
    5. Peters, Emmanuel & de Matta, Renato & Boe, Warren, 2007. "Short-term work scheduling with job assignment flexibility for a multi-fleet transport system," European Journal of Operational Research, Elsevier, vol. 180(1), pages 82-98, July.
    6. Wallace J. Hopp & Eylem Tekin & Mark P. Van Oyen, 2004. "Benefits of Skill Chaining in Serial Production Lines with Cross-Trained Workers," Management Science, INFORMS, vol. 50(1), pages 83-98, January.
    7. Sayin, Serpil & Karabati, Selcuk, 2007. "Assigning cross-trained workers to departments: A two-stage optimization model to maximize utility and skill improvement," European Journal of Operational Research, Elsevier, vol. 176(3), pages 1643-1658, February.
    8. Federica Costa & Matthias Thürer & Alberto Portioli-Staudacher, 2023. "Heterogeneous worker multi-functionality and efficiency in dual resource constrained manufacturing lines: an assessment by simulation," Operations Management Research, Springer, vol. 16(3), pages 1476-1489, September.
    9. Wright, P. Daniel & Mahar, Stephen, 2013. "Centralized nurse scheduling to simultaneously improve schedule cost and nurse satisfaction," Omega, Elsevier, vol. 41(6), pages 1042-1052.
    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. Fowler, John W. & Wirojanagud, Pornsarun & Gel, Esma S., 2008. "Heuristics for workforce planning with worker differences," European Journal of Operational Research, Elsevier, vol. 190(3), pages 724-740, November.
    12. Hu, Qian & Wei, Lijun & Lim, Andrew, 2018. "The two-dimensional vector packing problem with general costs," Omega, Elsevier, vol. 74(C), pages 59-69.
    13. G M Campbell, 2011. "A two-stage stochastic program for scheduling and allocating cross-trained workers," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 62(6), pages 1038-1047, June.
    14. Omri Dover & Dvir Shabtay, 2016. "Single machine scheduling with two competing agents, arbitrary release dates and unit processing times," Annals of Operations Research, Springer, vol. 238(1), pages 145-178, March.
    15. Hong, Shaohui & Zhang, Defu & Lau, Hoong Chuin & Zeng, XiangXiang & Si, Yain-Whar, 2014. "A hybrid heuristic algorithm for the 2D variable-sized bin packing problem," European Journal of Operational Research, Elsevier, vol. 238(1), pages 95-103.
    16. de Souza, Mauricio C. & de Carvalho, Carlos R.V. & Brizon, Wellington B., 2008. "Packing items to feed assembly lines," European Journal of Operational Research, Elsevier, vol. 184(2), pages 480-489, January.
    17. David D. Cho & Kurt M. Bretthauer & Jan Schoenfelder, 2023. "Patient-to-nurse ratios: Balancing quality, nurse turnover, and cost," Health Care Management Science, Springer, vol. 26(4), pages 807-826, December.
    18. Borja Ena & Alberto Gomez & Borja Ponte & Paolo Priore & Diego Diaz, 2022. "Homogeneous grouping of non-prime steel products for online auctions: a case study," Annals of Operations Research, Springer, vol. 315(1), pages 591-621, August.
    19. Paquay, Célia & Limbourg, Sabine & Schyns, Michaël, 2018. "A tailored two-phase constructive heuristic for the three-dimensional Multiple Bin Size Bin Packing Problem with transportation constraints," European Journal of Operational Research, Elsevier, vol. 267(1), pages 52-64.
    20. Lewis, R. & Song, X. & Dowsland, K. & Thompson, J., 2011. "An investigation into two bin packing problems with ordering and orientation implications," European Journal of Operational Research, Elsevier, vol. 213(1), pages 52-65, August.

    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:279:y:2019:i:1:p:54-67. 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.