{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,21]],"date-time":"2026-01-21T12:14:09Z","timestamp":1768997649702,"version":"3.49.0"},"reference-count":16,"publisher":"MDPI AG","issue":"7","license":[{"start":{"date-parts":[[2022,6,23]],"date-time":"2022-06-23T00:00:00Z","timestamp":1655942400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100001809","name":"NSFC","doi-asserted-by":"publisher","award":["72071116"],"award-info":[{"award-number":["72071116"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001809","name":"NSFC","doi-asserted-by":"publisher","award":["2019B10026"],"award-info":[{"award-number":["2019B10026"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001809","name":"NSFC","doi-asserted-by":"publisher","award":["E01220200006"],"award-info":[{"award-number":["E01220200006"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Ningbo 2025 key technology projects","award":["72071116"],"award-info":[{"award-number":["72071116"]}]},{"name":"Ningbo 2025 key technology projects","award":["2019B10026"],"award-info":[{"award-number":["2019B10026"]}]},{"name":"Ningbo 2025 key technology projects","award":["E01220200006"],"award-info":[{"award-number":["E01220200006"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Symmetry"],"abstract":"<jats:p>Bin packing is a typical optimization problem with many real-world application scenarios. In the online bin packing problem, a sequence of items is revealed one at a time, and each item must be packed into a bin immediately after its arrival. Inspired by duality in optimization, we proposed pattern-based adaptive heuristics for the online bin packing problem. The idea is to predict the distribution of items based on packed items, and to apply this information in packing future arrival items in order to handle uncertainty in online bin packing. A pattern in bin packing is a combination of items that can be packed into a single bin. Patterns selected according to past items are adopted and periodically updated in scheduling future items in the algorithm. Symmetry in patterns and the stability of patterns in the online bin packing problem are discussed. We have implemented the algorithm and compared it with the Best-Fit in a series of experiments with various distribution of items to show its effectiveness.<\/jats:p>","DOI":"10.3390\/sym14071301","type":"journal-article","created":{"date-parts":[[2022,6,23]],"date-time":"2022-06-23T22:43:00Z","timestamp":1656024180000},"page":"1301","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":9,"title":["Identify Patterns in Online Bin Packing Problem: An Adaptive Pattern-Based Algorithm"],"prefix":"10.3390","volume":"14","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-7046-7189","authenticated-orcid":false,"given":"Bingchen","family":"Lin","sequence":"first","affiliation":[{"name":"School of Computer Science, University of Nottingham Ningbo China, Ningbo 315000, China"}]},{"given":"Jiawei","family":"Li","sequence":"additional","affiliation":[{"name":"School of Computer Science, University of Nottingham Ningbo China, Ningbo 315000, China"}]},{"given":"Ruibin","family":"Bai","sequence":"additional","affiliation":[{"name":"School of Computer Science, University of Nottingham Ningbo China, Ningbo 315000, China"}]},{"given":"Rong","family":"Qu","sequence":"additional","affiliation":[{"name":"School of Computer Science, University of Nottingham, Nottingham NG8 1BB, UK"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0102-2581","authenticated-orcid":false,"given":"Tianxiang","family":"Cui","sequence":"additional","affiliation":[{"name":"School of Computer Science, University of Nottingham Ningbo China, Ningbo 315000, China"}]},{"given":"Huan","family":"Jin","sequence":"additional","affiliation":[{"name":"School of Computer Science, University of Nottingham Ningbo China, Ningbo 315000, China"}]}],"member":"1968","published-online":{"date-parts":[[2022,6,23]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"299","DOI":"10.1137\/0203025","article-title":"Worst-Case Performance Bounds for Simple One-Dimensional Packing Algorithms","volume":"3","author":"Johnson","year":"1974","journal-title":"SIAM J. Comput."},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"272","DOI":"10.1016\/S0022-0000(74)80026-7","article-title":"Fast algorithms for bin packing","volume":"8","author":"Johnson","year":"1974","journal-title":"J. Comput. Syst. Sci."},{"key":"ref_3","unstructured":"Johnson, D.S. (1973). Near-Optimal Bin Packing Algorithms. [Ph.D. Thesis, Massachusetts Institute of Technology]."},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"207","DOI":"10.1145\/322186.322187","article-title":"New Algorithms for Bin Packing","volume":"27","author":"Yao","year":"1980","journal-title":"J. ACM"},{"key":"ref_5","doi-asserted-by":"crossref","unstructured":"Coffman, E.G., Csirik, J., Galambos, G., Martello, S., and Vigo, D. (2013). Bin Packing Approximation Algorithms: Survey and Classification. Handbook of Combinatorial Optimization, Springer.","DOI":"10.1007\/978-1-4419-7997-1_35"},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"562","DOI":"10.1145\/3828.3833","article-title":"A simple on-line bin-packing algorithm","volume":"32","author":"Lee","year":"1985","journal-title":"J. ACM"},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"305","DOI":"10.1016\/0196-6774(89)90031-X","article-title":"On-line bin packing in linear time","volume":"10","author":"Ramanan","year":"1989","journal-title":"J. Algorithms"},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"203","DOI":"10.1016\/0166-218X(91)90087-D","article-title":"Improved bounds for harmonic-based bin packing algorithms","volume":"34","author":"Richey","year":"1991","journal-title":"Discret. Appl. Math."},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"640","DOI":"10.1145\/585265.585269","article-title":"On the online bin packing problem","volume":"49","author":"Seiden","year":"2002","journal-title":"J. ACM"},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/j.tcs.2012.04.017","article-title":"New lower bounds for certain classes of bin packing algorithms","volume":"440\u2013441","author":"Balogh","year":"2012","journal-title":"Theor. Comput. Sci."},{"key":"ref_11","unstructured":"Heydrich, S., and van Stee, R. (2016, January 12\u201315). Beating the Harmonic Lower Bound for Online Bin Packing. Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016), Rome, Italy. Available online: http:\/\/drops.dagstuhl.de\/opus\/volltexte\/2016\/6321."},{"key":"ref_12","doi-asserted-by":"crossref","unstructured":"Silva-G\u00e1lvez, A., Lara-C\u00e1rdenas, E., Amaya, I., Cruz-Duarte, J.M., and Ortiz-Bayliss, J.C. (2020). A Preliminary Study on Score-Based Hyper-heuristics for Solving the Bin Packing Problem. Pattern Recognition, Springer Science+Business Media. Chapter 30.","DOI":"10.1007\/978-3-030-49076-8_30"},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"113343","DOI":"10.1016\/j.dss.2020.113343","article-title":"A data-driven methodology for the automated configuration of online algorithms","volume":"137","author":"Dunke","year":"2020","journal-title":"Decis. Support Syst."},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"1474","DOI":"10.1287\/opre.2019.1914","article-title":"Interior-Point-Based Online Stochastic Bin Packing","volume":"68","author":"Gupta","year":"2020","journal-title":"Oper. Res."},{"key":"ref_15","doi-asserted-by":"crossref","unstructured":"Ross, N., Keedwell, E., and Savic, D. (2020). Human-Derived Heuristic Enhancement of an Evolutionary Algorithm for the 2D Bin-Packing Problem. Parallel Problem Solving from Nature\u2014PPSN XVI, Springer.","DOI":"10.1007\/978-3-030-58115-2_29"},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"741","DOI":"10.1609\/aaai.v35i1.16155","article-title":"Online 3D bin packing with constrained deep reinforcement learning","volume":"Volume 35","author":"Zhao","year":"2021","journal-title":"Proceedings of the AAAI Conference on Artificial Intelligence"}],"container-title":["Symmetry"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/2073-8994\/14\/7\/1301\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,10]],"date-time":"2025-10-10T23:38:07Z","timestamp":1760139487000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/2073-8994\/14\/7\/1301"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,6,23]]},"references-count":16,"journal-issue":{"issue":"7","published-online":{"date-parts":[[2022,7]]}},"alternative-id":["sym14071301"],"URL":"https:\/\/doi.org\/10.3390\/sym14071301","relation":{},"ISSN":["2073-8994"],"issn-type":[{"value":"2073-8994","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,6,23]]}}}