We present a worst case analysis for the Generalized Bin Packing Problem, a novel packing problem arising in many Transportation and Logistics settings and characterized by multiple item and bin attributes and by the joint presence of both compulsory and non-compulsory items. As a preliminary worst case analysis has recently been proposed in the literature, we extend this study by proposing semi-online and offline algorithms, extending the well known First Fit Decreasing and Best Fit Decreasing heuristics for the Bin Packing Problem. In particular, we show that knowing part of the instance or the whole instance is not enough for computing worst case ratio bounds.
Asymptotic results for the Generalized Bin Packing Problem / Baldi, MAURO MARIA; Crainic, T. G.; Perboli, Guido; Tadei, Roberto. - In: PROCEDIA: SOCIAL & BEHAVIORAL SCIENCES. - ISSN 1877-0428. - ELETTRONICO. - 111(2014), pp. 663-671.
Titolo: | Asymptotic results for the Generalized Bin Packing Problem | |
Autori: | ||
Data di pubblicazione: | 2014 | |
Rivista: | ||
Digital Object Identifier (DOI): | http://dx.doi.org/10.1016/j.sbspro.2014.01.100 | |
Appare nelle tipologie: | 1.1 Articolo in rivista |
File in questo prodotto:
File | Descrizione | Tipologia | Licenza | |
---|---|---|---|---|
2014-procedia-Asymptotic results for the Generalized Bin Packing Problem.pdf | 2a Post-print versione editoriale / Version of Record | ![]() | Visibile a tuttiVisualizza/Apri | |
EWGT2013_Baldi_final.pdf | 2. Post-print / Author's Accepted Manuscript | ![]() | Visibile a tuttiVisualizza/Apri |
http://hdl.handle.net/11583/2508940