Please use this identifier to cite or link to this item: https://hdl.handle.net/10419/339946 
Year of Publication: 
2026
Citation: 
[Journal:] Mathematical Methods of Operations Research [ISSN:] 1432-5217 [Volume:] 102 [Issue:] 2-3 [Publisher:] Springer [Place:] Berlin, Heidelberg [Year:] 2026 [Pages:] 395-433
Publisher: 
Springer, Berlin, Heidelberg
Abstract: 
We study the overflowing bin packing problem (OBPP), a recently proposed one-dimensional packing problem with notable conceptual ties to the field of (just-in-time) scheduling. In this scenario, we are required to pack items of known sizes into bins of known capacities so that, in broad terms, each bin’s total load comes as close as possible to its capacity. To establish its status as an independent research branch, the OBPP is first distinguished from related optimization problems. We then review an assignment model from the literature and analyze its theoretical properties, providing a closed-form expression for the associated LP bound and characterizing its worst-case performance ratio. In the second part, we introduce a new flow-based approach for the OBPP and examine both its theoretical and numerical advantages, the latter based on extensive computational experiments with diverse benchmark sets. Overall, the new flow formulation consistently produces high-quality—mostly optimal—solutions in short computation times, significantly outperforming previous state-of-the-art methods.
Subjects: 
Cutting and packing
Bin packing
Extendable bins
Flow formulation
LP bound
Just-in-time scheduling
Persistent Identifier of the first edition: 
Creative Commons License: 
cc-by Logo
Document Type: 
Article
Document Version: 
Published Version

Files in This Item:
File
Size





Items in EconStor are protected by copyright, with all rights reserved, unless otherwise indicated.