EXACT ALGORITHMS FOR THE GUILLOTINE STRIP CUTTING PACKING PROBLEM/

In this paper we present exact algorithms for strip cutting/packing pr oblems. The proposed algorithms are based upon branch-and-bound proced ures. In the first algorithm, the problem is reduced to a series of tw o-dimensional constrained cutting stock problems. Each step of this al gorithm is solved by using a recent algorithm (called MVB) developed b y Hifi [Hifi, M., An improvement of Viswanathan and Bagchi's exact alg orithm for cutting stock problems. Computers and Operations Research, 1997, 24(8), 727-736.]. The second algorithm considers a large stock r ectangle, 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 p roposed exact algorithms are able to solve some small and medium probl em instances within reasonable execution times. These algorithms are e asily parallelizable and this is one of their important futures. (C) 1 998 Elsevier Science Ltd. All rights reserved.