Groupe d’études et de recherche en analyse des décisions


Hybrid Heuristics for the Three-Stage Cutting Stock Problem


The three-stage cutting stock problem consists in laying out a set of ordered rectangular pieces on some rectangular strips, and then these strips are laid out on some stock sheets such that the number of utilized stock sheets is minimized. This way of cutting stock sheets is frequent in flat glass and wood industries. This problem is very difficult to solve to optimality for typical industrial instances, and heuristics are the only way to obtain good solutions in reasonable times. In this paper, we present a way of constructing heuristics. The solution process is split in 3 main steps. For each step, we propose a few methods to obtain a solution. A new heuristic is then constructed by choosing a method for each step. This kind of procedure allows the user to focus the energy (here energy = cpu time) on the real difficulty of the instance. We compare a typical heuristic with a slight variation of the well known Hybrid First Fit heuristic, see Chung et al. (1982), which is very fast and very performant.

, 20 pages