Bin Packing with due dates

In the Bin Packing problem (BP), items of different sizes must be assigned to a minimum number of bins. In the k-dimensional problem (kBP), items and bins are closed k-intervals. 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 kBP objective is the minimization of the makespan. We generalize the kBP problem to Bin Packing and Scheduling (kBPS) by changing the objective to any (even non-regular) function of the completion time of the jobs. Interesting applications are those in which each part (= job) is to be produced within a specific due date. Typical examples of regular functions are maximum lateness, weighted sum of jobs tardiness, etc. In practice, a convex combination of such functions is often considered. When the scheduling term in the objective function is the weighted sum of jobs tardiness or of tardy jobs, one can specialize an exact formulation for the Cutting Stock Problem with Due Dates (Arbib and Marinelli, 2014). An alternative, more general and perhaps more effective approach is to use an ad-hoc time-indexed formulation. This approach, which can encompass Dantzig-Wolfe decomposition and, consequently, column generation, is close to that described by van den Akker et al. (2005) for general time-indexed formulations applied to parallel scheduling. When column generation is used, the difficulty of k-dimensional packing is relegated to the pricing problem. To find a lower bound for the 2BPS one can then solve a relaxed 2-dimensional pricing problem by the arc-flow formulation (Macedo, Alves and V. de Carvalho, 2010). In alternative, one can implement conservative scales (Belov et al., 2013) via a time-indexed formulation for 1BPS. In this talk we just discuss a preliminary computational experience carried out for 1BPS with Lmax as scheduling term of the objective function