5. Conclusions
We presented and exact ILP formulation and a heuristic algorithm for a 1-dimensional bin packing problem with due dates, where the objective is to minimize a convex combination of the number of bins and the maximum lateness of parts. Cutting/packing problems with due dates are increasingly studied and have important practical applications. One quality of the approach here described is flexibility: in fact, a time-indexed formulation can easily be extended to different scheduling objectives. On the other hand, a typical drawback of this type of formulation is the quite large number of variables and constraints. The crucial role that in our experience lower and upper bounds played to strengthen activation constraints and to fix 0–1 variables suggests that, in future research, an adequate attention is to be paid to bounding effectively the objective function. Other issues, such as the design of an exact Branch-and-Price algorithm, the computation of the Pareto frontier of Cmax vs. Lmax and the extension of the bound strengthening technique to different scheduling objective functions deserve further investigation. Finally, future generalizations of the approach to the s-dimensional problem can take advantage from the decomposition here described.
