Maximum lateness minimization in one-dimensional bin packing

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.