Theory And Methodology Of Packing Problems And Guillotine Cutting Problems

We systematically discuss some theory and methodology for the two-dimensional and three-dimensional packing problem, as well as two-dimensional guillotine cutting stock problem. We make following contributions in this dissertationFor the two-dimensional rectangular packing problem, a heuristic with 6 block pattern and the implicit enumeration mechanism is presented, where Herz normal points are adopted. Evaluation of the effectiveness is made, compared with continuous upper bound and results of experiential packing methods. Computational results approximately equal to the upper bound. For the two-dimensional circular packing problem, a heuristic with snake array pattern is proposed, the model for the relations of three circles is established and stability principle is put forward.Guillotine cutting stock problems are considered. An algorithm based on 4 block structure is provided, including cutting times and upper bounds of area utilization ratio. New heuristic rules and models for the guillotine cutting stock problem with strip-block patterns are established, where the approach keeps 3 staged cutting and also covers strip cutting properties. The calculation results show the effectiveness of the above two heuristics, compared with those of benchmark instances.For the fixed orientation packing problems of Up Side Up cardboard boxes, the algorithms with the constraints of proportional packing for the container and sub-container loading are discussed, and calculation are carried out. The effects of temperature, humidity, and cardboard box dimensions on the bearing strength of the box are systematically considered and a large quantity of experiment are made, as to find some regularity. Bearing strength constraint is included in Up Side Up cardboard boxes packing, and bearing strength safety rule is provided.Two heuristics for the rotated box packing with static procedure are proposed. One is the approach combining the two-dimensional packing with optimal perpendicular layer loading in any of three directions, denoted by FP, which has simple packing structure property and is applied to proportional packing. The other is an improved method of experiential packing, where trade-off between space utilization of solid part and side space of the container is made as to raise the whole utilization ratio.Based on Best-First rule and tree search, two heuristics for the rotated box packing with dynamic procedure are discussed. In the first heuristic, denoted by LIA, the layer with best utilization ratio is first considered to pack. In the second, denoted by 2LIA, two layers with best combined utilization ratio in two generations of the tree search are first packed. Finally, a mixed approach combining LIA and FP is put forward, which contains advantages both LIA and FP. Evaluation is made for the rotated box packing heuristics and utilization ratio is averagely raised 11.36%, compared with those of experiential packing methods.This dissertation is complished under the several projects supported by Municipal Committee of Science and Technology, and Municipal Committee of Education.