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. [10.1016/j.sbspro.2014.01.100]

Asymptotic results for the Generalized Bin Packing Problem

BALDI, MAURO MARIA;PERBOLI, Guido;TADEI, Roberto
2014

Abstract

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.
File in questo prodotto:
File Dimensione Formato  
2014-procedia-Asymptotic results for the Generalized Bin Packing Problem.pdf

accesso aperto

Tipologia: 2a Post-print versione editoriale / Version of Record
Licenza: Creative commons
Dimensione 166.92 kB
Formato Adobe PDF
166.92 kB Adobe PDF Visualizza/Apri
EWGT2013_Baldi_final.pdf

accesso aperto

Tipologia: 2. Post-print / Author's Accepted Manuscript
Licenza: Creative commons
Dimensione 224.21 kB
Formato Adobe PDF
224.21 kB Adobe PDF Visualizza/Apri
Pubblicazioni consigliate

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11583/2508940