Exact algorithms for the guillotine strip cutting/packing problem
The strip cutting/packing problem consists of cutting a large strip with a fixed-width and unlimited length into smaller subrectangles, without violating the demand values imposed on each subrectangle. Computer science, industrial engineering, logistics, manufacturing, management, production processes are among obvious fields of applications. In this paper we propose exact approaches for solving optimally the strip cutting/packing problem. The proposed algorithms are based upon branch-and-bound and dynamic programming procedures. In this paper we present exact algorithms for strip cutting/packing problems. The proposed algorithms are based upon branch-and-bound procedures. In this paper we present exact algorithms for strip cutting/packing problems. The proposed algorithms are based upon branch-and-bound procedures. In the first algorithm, the problem is reduced to a series of two-dimensional constrained cutting stock problems. Each step of this algorithm is solved by using a recent algorithm (called MVB) developed by Hifi [Hifi, M., An improvement of Viswanathan and Bagchi's exact algorithm for cutting stock problems. Computers and Operations Research, 1997, 24(8), 727736.]. The second algorithm considers a large stock rectangle, constructed by using a heuristic algorithm for limiting the length of the initial strip. Then, we apply the MVB algorithm by using the best-first search strategy. Computational results show that the proposed exact algorithms are able to solve some small and medium problem instances within reasonable execution times. These algorithms are easily parallelizable and this is one of their important futures.
branch-and-bound dynamic programming heuristics combinatorial optimization cutting and packing