Research On Two-Dimensional Cutting Stock Problems Under Several Constraints

The two-dimensional cutting stock problem is an urgent problem in practice, which is very difficult in computation theory. It possess important situation in industrial manufacturing. The problem has great economic benefits. Improving the utilizing ratio of raw material is one of the main methods of reducing the product cost and improving the competitiveness. The task of arranging the parts on the sheet is known as nesting. The process of nesting is an important step of the whole process in industries, the result of nesting will affect the later process directly. So the resolving of the cutting stock problems is of far-reaching theoretical and practical signification.The thesis is organized as follows:Chapter 1: What is the computer aided cutting stock problem? What is the "guillotine" cut? And what is the maximal cutting length constraint. The paper discusses these problems and their relative research works in chapter 1. The main research aim and our work are also introduced there.Chapter 2: First, introduce the research situation of the two-dimensional cutting stock problems. Then, enumerate several algorithms of general two-dimensional cutting stock problems and two-dimensional guillotine cutting stock problems respectively. Finally, give several rules always used in the two-dimensional cutting stock problems.Chapter 3: The two-dimensional guillotine cutting stock problem is discussed. In this chapter a heuristic approach CONS based on guillotine cut is described in detail. Then, several methods are proposed to improve the algorithm.Chapter 4: Introduce Wang's algorithm. Then, propose several methods to improve its computation speed. Finally, I extend it to make it can deal with the maximal cutting length constraint.Chapter 5: Summarizes all achievements of this dissertation, reviews innovation points and defects, and gives the further work in the future.