Branch and Price algorithm for the two stage guillotine stock problem
Mrad, Mehdi . 2012
We investigate the two-stage guillotine two-dimensional cutting stock problem. This problem commonly
arises in the industry when small rectangular items need to be cut out of large stock sheets. We propose an integer programming formulation that extends the well-known Gilmore and Gomory model by explicitly considering solutions that are obtained by both slitting some stock sheets down their widths and others down their heights. To solve this model, we propose an exact branch-and-price algorithm. To the best of our knowledge, this is the first contribution with regard to obtaining integer optimal solutions to Gilmore and Gomory model. Extensive results, on a set of real-world problems, indicate that the proposed algorithm delivers optimal solutions for instances with up to 809 items and that the hybrid cutting strategy often yields improved solutions. Furthermore, our computational study reveals that the proposed modelling and algorithmic strategy outperforms a recently proposed arc-flow model-based solution strategy.
In this paper, we address a real-world optimization problem; the scheduling of a Bank Information Technologies (IT) staff. This problem can be defined as the process of constructing optimized work…
In this paper, we address the problem of minimizing the consumed electric energy for a personal rapid transit transportation system, in order to fulfil a planned list of trips, performed by a set…
We investigate the two-stage guillotine two-dimensional cutting stock problem. This problem commonly