An exact solution approach for an integrated packing and scheduling problem

Cutting stock and bin-packing problems are both well known to be NP-hard problems. An interesting variant of these standard problems is the one that consider due dates. The time periods and the need to determine an order by which the orders should be cut increase the practical complexity of these problems. The objective of these variants is to find a cutting plan that minimizes both the total waste (the number of stock rolls used) and the tardiness of all the orders. In this paper, we address the particular case of the bin-packing problem with due dates. We describe the preliminary version of an integer programming model based on an arc-flow formulation. The solution of this model determines both the cutting plan of the items and the tardiness of the orders, i.e. the difference between the due date and the production time. Preliminary computational results on instances from the literature are presented and discussed at the end of the paper