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

#### 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.
##### Scheda breve Scheda completa Scheda completa (DC)
2017
File in questo prodotto:
File
1-s2.0-S030504831630305X-main.pdf

solo utenti autorizzati

Descrizione: Articolo principale
Tipologia: Documento in Versione Editoriale
Licenza: Dominio pubblico
Dimensione 404.3 kB
Utilizza questo identificativo per citare o creare un link a questo documento: `https://hdl.handle.net/11697/109728`