满足一刀切约束的卷型材矩形件排样方法研究

《满足一刀切约束的卷型材矩形件排样方法研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、分类号：UDC：密级：学校代号：11845学号：2111101003广东工业大学硕士学位论文(工学硕士)满足“一刀切"约束的卷型材矩形件排样方法研究何霖指导教师姓名、职称：塞4强副麴拯学科(专业)或领域名称：扭撼工猩学生所属学院：扭电工程堂医论文答辩日期：星Q!垒生墨旦JUllUlIIIIIIIIlY2581651ADissertationSubmittedtoGuangdongUniversityofTechnologyfortheDegreeofMaster(MasterOfEngineeringScience)ResearchonScrollPack

2、ingProblemWithGuillotineConstraintCandidate：HeLinSupervisor：LiuQiangMay2014SchoolofElectromechanicalEngineeringGuangdongUniversityofTechnologyGuangzhou，Guangdong，P-R．China，510006摘要卷型材矩形件排样问题是一类经典的NP完全问题，主要研究如何将矩形工件排放在长度可变的矩形原材料上，以获得高的材料利用率。受某些制造过程和工艺的影响，卷型材矩形件排样方案必须满足“一刀切”约束一一“从矩形

3、板材的一端，沿直线方向切割到另一端，将其分割成两个独立的矩形件”；受生产过程的约束，某些工件之间有配对要求，需要尽可能排放在一起。这些工艺约束和生产约束给卷型材矩形件排样问题的求解带来新的要求。卷型材矩形件排样问题在制造业中广泛存在，诸如造纸、薄钢板的加工或切割。对这一问题的有效求解方法直接影响企业的原料成本。本文重点研究工件可旋转的“一刀切”卷型材矩形件排样问题。提出了一种基于组块策略的启发式排样搜索算法GBHSA(Group．BasedHeuristicSearchApproach)。算法将二维矩形件排样问题分解成工件定位问题和工件组合问题，将多个工件

4、的组合工件组当成一个整体作为排样的基本单元；进而，提出一种构造性的排样递归搜索方法：利用“左下优先”原则解决工件的定位问题，将排样过程转化为“排放一切割”基本步骤的组合，并以利用率阈值作为回溯条件进行回溯。算法同时在切割方案的选择、排放工件的选择上运用了一系列的启发式规则。组块策略、启发式规则的使用有效缩减了搜索的解空间，提升了算法的速度，构造性的递归搜索在一定程度上保证了算法的全局寻优能力。通过使用国际上通用的一批标准测试案例进行测试，算法具有一定的先进性。同时，论文还研究了满足“一刀切”约束的矩形件交互式排样系统，开发了具有矩形件增、删、旋转和移动功能

5、的交互式排样组件；定义了原材料有效利用率这一核心概念，提出了一种以切割线总路径为优化目标的切割线生成算法；以自动生成排样方案的切割线，并保证切割方案的“一刀切”约束。最后，论文依据上述研究内容，开发了二维排样软件。关键字：卷型材排样；一刀切；启发式算法；交互式排样；切割线广东工业大学硕士学位论文ABSTRACTScrollPackingProblem(SPP)mainlyresearchonhowtoplacerectangularproductsonsheetmaterialwithvariablelengthinordertogethighmateri

6、alutilization．SPPsarewidespreadinthemanufacturingindustry,suchascuttingofpaperandsteelplate．SPPisonekindofclassicNP·CompleteProblem．Affectedbysomemanufacturingprocess，thepackingandcutsolutionofthemareaskedsatisfytheguillotineconstraint．Atthesametime，someworkpiecesarerequiredtobepa

7、ired．SuchparticularrequirementsbringnewchallengestOSPP．Goodlayoutsolutionscanincreasethematerialutilizationgreatlyandreducetheenterprise’Scost．ThisthesismainlyresearchesonTwo-DimensionalScrollPackingProblemwithRotatableRectangleandGuillotineConstraints(2DSPP-RG)．WeproposedaGroup-B

8、asedHeuristicSearchApproach，GBHSA