【作者】 杨传民；

【导师】 王树人；

【作者基本信息】 天津大学 ， 机械设计及理论， 2007， 博士

【摘要】 本文较为系统地研究了二维装填布局和切割布局、三维装填布局的一些理论与方法。论文取得了如下创新成果:在二维装填布局方面,提出了基于6块结构的长方形装填布局启发性算法,采用了Herz标准装填(切割)点,具有隐含枚举机制。提出了利用较习惯装填方法提高效率及理论上界(连续上界)评价方法,本文提出了较为严格的连续上界。通过计算,绝大部分优化结果接近理论上届。提出了圆的蛇形布局结构(snake array)启发性算法,提出了稳定性判据,推导的三圆关系公式是余量调整及判定稳定性依据公式。在二维斩断切割布局方面,提出了基于4块结构的斩断切割启发性算法,并提供了切割次数及利用率上界公式。提出了基于条块结构二维斩断切割布局方案和启发性规则,建立了数学模型,此种方法兼容了条状切割布局方法,又保持3级切割的简单性,同时增加了寻优的选择性。通过计算表明上述两种方法的有效性。对于Up Side Up箱型的定向装填布局(2+1维布局),提出了基于集装箱及基于子集装箱按比例装填布局启发性算法,并进行了计算。考虑远洋运输及全球气候变化,进行了纸箱堆码强度实验,重点考虑温度、湿度、尺寸对堆码强度的影响规律。将堆码强度作为约束引入到Up Side Up箱型的装填布局,提出了Up Side Up纸箱装填布局承载能力准则。对于任意摆放箱型三维装填布局静态方法,提出了一种平面优化附加垂直方向摆层优化的方法—“平垂法”,具有装填结构简单的特点。提出了多种任意摆放箱型按比例装填的平垂法。提出的改进习惯装填方法采纳了习惯装填方法中实体部分又充分考虑了边缘剩余空间的利用。对于任意摆放箱型三维装填布局动态方法,提出了基于Best-First规则和树搜索的全位法一步法及两步法。提出一种动态和静态混合方法---全位法与平垂法的混合法。混合法是集平垂法和全位法优点于一身的更好优化方法。总体上看,优化装填方法相对于习惯装填方法平均提高装填能力为11.36%。本文得到了天津市自然科学基金及天津市高校发展基金“平面几何图形智能布局”项目、天津市教委“低温物流中关键技术及管理研究(子项目:低温物流中产品防护特性与装填布局研究)”重大专项的支持。更多还原

【Abstract】 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.更多还原