Bitte verwenden Sie diesen Link, um diese Publikation zu zitieren, oder auf sie als Internetquelle zu verweisen: https://hdl.handle.net/10419/339946 
Erscheinungsjahr: 
2026
Quellenangabe: 
[Journal:] Mathematical Methods of Operations Research [ISSN:] 1432-5217 [Volume:] 102 [Issue:] 2-3 [Publisher:] Springer [Place:] Berlin, Heidelberg [Year:] 2026 [Pages:] 395-433
Verlag: 
Springer, Berlin, Heidelberg
Zusammenfassung: 
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.
Schlagwörter: 
Cutting and packing
Bin packing
Extendable bins
Flow formulation
LP bound
Just-in-time scheduling
Persistent Identifier der Erstveröffentlichung: 
Creative-Commons-Lizenz: 
cc-by Logo
Dokumentart: 
Article
Dokumentversion: 
Published Version

Datei(en):
Datei
Größe





Publikationen in EconStor sind urheberrechtlich geschützt.