Maximum lateness minimization in one-dimensional Bin Packing problems

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 minimization of the number of bins corresponds to the minimization of the makespan. We here generalize the problem to the case in which each item is due by some date: our objective is to minimize a convex combination of makespan and maximum lateness. We propose a time indexed ILP formulation to solve the problem. The formulation can be decomposed and solved by column generation, in which case single-bin packing is relegated to a pricing problem: therefore, extensions to s-dimensional problems can be dealt with independently. We show how to couple the formulation with quite simple bounds to (individual terms of) the objective function, so as to get very good gaps with instances that are considered difficult for the 1-BP.