In the One-dimensional Bin Packing problem (1-BP) items of different lengths must be assigned to a minimum number of bins of unit length. Regarding each item as a job that requires unit time and some resource amount, and each bin as the total (discrete) resource available per time unit, the 1-BP objective is the minimization of the makespan Cmax = maxj{Cj}. We here generalize the problem to the case in which each item j is due by some date dj: our objective is to minimize a convex combination of Cmax and Lmax = maxj {Cj − dj }. For this problem we propose a time-indexed Mixed Integer Linear Programming formulation. The formulation can be decom- posed and solved by column generation relegating single-bin packing to a pricing problem to be solved dynamically. We use bounds to (individual terms of) the objective function to address the oddity of activation con- straints. In this way, we get very good gaps for instances that are considered difficult for the 1-BP.

Maximum lateness minimization in one-dimensional bin packing

ARBIB, CLAUDIO;
2017-01-01

Abstract

In the One-dimensional Bin Packing problem (1-BP) items of different lengths must be assigned to a minimum number of bins of unit length. Regarding each item as a job that requires unit time and some resource amount, and each bin as the total (discrete) resource available per time unit, the 1-BP objective is the minimization of the makespan Cmax = maxj{Cj}. We here generalize the problem to the case in which each item j is due by some date dj: our objective is to minimize a convex combination of Cmax and Lmax = maxj {Cj − dj }. For this problem we propose a time-indexed Mixed Integer Linear Programming formulation. The formulation can be decom- posed and solved by column generation relegating single-bin packing to a pricing problem to be solved dynamically. We use bounds to (individual terms of) the objective function to address the oddity of activation con- straints. In this way, we get very good gaps for instances that are considered difficult for the 1-BP.
File in questo prodotto:
File Dimensione Formato  
1-s2.0-S030504831630305X-main.pdf

solo utenti autorizzati

Descrizione: Articolo principale
Tipologia: Documento in Versione Editoriale
Licenza: Dominio pubblico
Dimensione 404.3 kB
Formato Adobe PDF
404.3 kB Adobe PDF   Visualizza/Apri   Richiedi una copia
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/11697/109728
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 20
  • ???jsp.display-item.citation.isi??? 14
social impact