Algorithms For Two-Dimensional Multi-Stage Cutting Problem Using General Strips

Cutting stock problems can be found in manufacture industries, such as machinery manufacturing, aerospace, wood cutting and clothing industry. The rectangular cutting stock problem is the most widespread among these problems. The cutting stock problem is to seek a cutting plan that cuts all items in the minimum number of used plates. Cutting problems are the sub-problem of cutting stock problems, it seek for the cutting pattern that maximizes the total value of items produced from a single plate. This dissertation focuses on two-dimensional cutting problem. Due to the fact that the cutting plan comes from multiple calls of cutting problem algorithm, the quality of a cutting plan depends on the pattern generation algorithm.Some restricts are taken into consideration in practice:guillotine cut and constrained condition. guillotine cut means that each cut is from one side to the other side and the direction of cuts is parallel to one of the sides;. Constrained means that if the number of items cannot exceed a given demand.This dissertation presents two algorithms based on general strip using guillotine cutting. The first algorithm focuses on the unconstrained two-dimensional cutting problem. Strips can be generated preliminarily using complete knapsack method, and then the process of splicing will performed to maximize the value.The second algorithm discusses the constrained two-dimensional cutting problems. Strips will be produced using greedy strategy, in order to get a solution within reasonable time, the algorithm of this dissertation quotes branch-and-bound technology, using the result of the improved version of the unconstrained algorithm. Finally, the second algorithm is improved by using top-to-bottom recursive construction to decrease the computational time. Experiments show that the both the two algorithms can obtain larger pattern value than other algorithms in a reasonable time. The improved second algorithm can effectively shorten the computational time of the second algorithm.