On cutting stock with due dates

• We develop an exact model of a combined cutting stock and scheduling problem.
• The size of the model is managed by decomposing the planning period.
• The approach is based on integer reformulation and column generation.
• The approach provides good solutions to real size problems.

Classical stock cutting calls for fulfilling a given demand of parts, minimizing raw material needs. With the production of each part type regarded as a job due within a specific date, a problem arises of scheduling cutting operations. We here propose an exact integer linear programming formulation, and develop primal heuristics, upper bounds and an implicit enumeration scheme. A computational experience carried out for the one-dimensional problem shows that our primal heuristics outperform known ones, and that the formulation has good features for finding exact solutions of non-trivial instances.