线性规划算法启发式算法随机搜索算法基于分层随机搜索算法的维非连续多段下料研究分层随机搜索算法的原理分层随机算法原理启发式评价算法步骤算法优化维非连续多段下料的算法设计非连续多段下料的数学模型非连续多段下料的算法原理算法讨论基于的薄膜瑕疵检测介绍及瑕疵检测流程概述介绍瑕疵检测流程概述万方数据图像预处理灰度化薄膜图像的去噪处理腐蚀膨胀瑕疵判断图像分割轮廓提取薄膜分切下料系统的设计及实验计算薄膜分切系统的设计实验算例结论与展望工作与总结展望参考文献万方数据图清单图排样方式分层组合示意图图获取种排样方式及其评价值的方法起并应用到实际生产中在已有的文献中鲜有提及。根据对当地些大型的薄膜生产企业进行调研，传统的薄膜分切流程如下图图传统的薄膜分切流程图的订单组合筛选和计算环节基本都是由人工完成，需要大量的时间成本，而且当薄膜待分切的种类较多时，人工计算出的排样方案通常较为不合理。此外，由于分切时没有对薄膜的品质进行检测，即薄膜中存在的瑕疵在分切之前没有排除，造成分切出的薄膜的质量存在不合格的可能性。这种不合格的产品交付给客户时，就会造成企业信誉与销量的下降，对企业造成经济损失同时也造成了薄膜产品的浪费。因此，建立个如下图所示的薄膜瑕疵的检测及智能分切系统，通过图像采集系统把实时检测到的瑕疵大小位置坐标等信息存入服务器的数据库中，当该批次薄膜进行下料分切时，下料分切软件从服务器的数据库中读取出该批次薄膜的瑕疵信息再进行维非连续分段下料计算，最后把计算出的结果打印出分切报表，指导现场工人分切下料。把维下料问题同瑕疵检测技术相结合，具有较大的意义。万方数据中国计量学院硕士学位论文图薄膜瑕疵的检测及智能分切系统示意图本文的主要研究内容及章节安排本文研究的是薄膜材料的维下料问题，考虑到薄膜材料的特殊性，在生产过程中因拉伸等原因经常出现新产出的薄膜大卷中有段或多段存在瑕疵的部分，即维下料问题中的非连续分段下料问题，同时研究了基于图像处理技术的薄膜的瑕疵检测，检测出薄膜瑕疵的位置及大小，并把对应大卷薄膜的编号及瑕疵信息导入到数据库中，下料分切系统通过读取数据库中的相应信息进行下料分切。本文的主要研究内容有维下料算法的研究。设计并开发了种基于分层随机搜索算法的启发式算法，下料方法上按优先级从高到低对的三个目标进行生产切割的优化。首要目标是使原材料消耗最少，即薄膜原材料消耗的总卷数最少其次，还要追求最终排样方式数少最后，要求最后种排样方式剩余的余料长度较大。维非连续多段下料算法的研究。在基于分层随机搜索算法的启发式算法的基础上，针对薄膜中存在到多段瑕疵的部分导致不能整段分切的情况，在维连续下料算法的基础上设计并开发了维非连续多段下料算法。薄膜图像的瑕疵检测研究。通过对采集的图像通过进行预处理腐蚀膨胀二值化轮廓检测等操作，确定图像瑕疵的大小及位置，把瑕疵的信息保存到数据库中，供分切下料系统使用。万方数据中国计量学院硕士学位论文本文的各章节划分如下第章绪论。对本课题的背景和研究现状进行了总结和分析，并对论文工作的必要性和研究意义进行了阐述，另外还分章节对论文工作进行了简介。第二章维下料问题的典型算法。对典型的维下料算法进行介绍。第三章基于分层随机算法的维非连续多段下料研究。详细介绍本文算法的算法思想及其具体实现。第四章薄膜瑕疵的检测与定位。介绍了薄膜瑕疵检测的方法及实现。第五章薄膜分切下料系统的设计与实验计算。介绍了薄膜分切下料系统的各功能模块，并通过多组实验算例验证算法的有效性。第六章对全部论文工作进行了个总结，并对未来的研究做了相应的展望。万方数据中国计量学院硕士学位论文维下料问题的典型算法维下料问题属于运筹学的范畴，维下料的数学模型通常都可以用线性规划的方法表示出来。但由于维下料问题是个问题，其线性规划的模型中行向量的的个数是不确定的，即排样方式数的不确定。此外，维下料问题通常需要得到整数解，这也给线性规划算法带了定的难度。所以，除了传统的线性规划算法，各种各样的启发式算法以及随机搜索算法被众多学者深入研究并用于解决该问题。本章将对这些典型算法进行介绍。线性规划算法年，和基于单纯形法提出了推迟列生成法来解决该问题。该模型考虑只有种原材料的情况，设原材料长度为，需切割成个规格的坯料，各坯料的长度分别为，所对应的需求数分别为，设排样方案中共有种排样方式，每格的材料使用的数量分别为，，其中表示第种排样方式。设为使用的材料总根数，以原材料消耗的总卷数最少为目标函数，和给出的数学模型如下其中，且为整数。这里排样方案是指针对该模型的整个下料方案切割方案，而排样方式是指种排样方案中的种下料方式。由式中的附加条件，看出，该模型允许生产出的各个规格的原材料适当大于各规格原材料的需求数。通常情况下，，以个包括种宽度分别为的规格的小坯料排样任务为例总宽度取，单位均为，我们用种优化过的万方数据中国计量学院硕士学位论文枚举法对其可行的排样方式进行分析，其中，仅满足余料为的就有种，满足余料小于的就有种。枚举组合难以对排样方案进行筛选，且随着规格数种树的增加，排样方式数曾指数级的增长。因此，直接用线性规划方法来求解该问题是十分困难的。和提出了种列推迟法首先不考虑该问题的整数约束条件，根据原材料坯料的规格种数设立个阶基矩阵的可行解，采用了修正单纯形法的思想，通过对当前进行动态的价值评判，不断的迭代修改该可行解的成员元素来代替原可行解，直至无法得到更优秀的解为止。在算法满足终止条件后输出最终的解，再对解进行近似整数优化处理。该方法的提出使得求解下料问题特别是原材料坯料种数较多时变为可能，只考虑了中排样方式，避免了对大量可行排样方式的枚举，具有定的意义。但是该方法的缺点也非常明显由于求得的解通常不是整数，需要进步的近似整数优化处理，容易造成给出的方案大于或小于需求量的情况此外，给出的排样方案的排样方式种数般接近，而较多的排样方式往往会增加生产中的更换切割刀具位置带来的成本损耗，通常不被采用。启发式算法启发式算法的概念是相对于最优化算法提出的，自然界中的些数学问题是存在最优解的，而另类问题，诸如问题，通常无法在规定的时间内得出该问题的最优解。启发式算法通过设立各种启发式规则可以在定时间内得到该问题的可行解或次优解，但其同最优解的偏离程度是无法估计的。鉴于以上的特性，启发式算法就比较适合应用于下料问题当中。针对维下料问题的众多启发式算法中，提出的顺序启发式算法具有定的代表性。在文章中首次提出在下料过程中调整下料切割机器的切割模式也会带来下料费用，即排样方案中的每种排样方式都会带来定的下料费用。国内学者也曾提出企业也非常重视调整切割模式带来的额外费用。因此，以线性规划算法的下料模型为基础，提出了种新的数学模型，同样设其原材料长度为，设为第种排样方式的切边损失万方数据中国计量学院硕士学位论文则其数学模型为其中为原材料浪费产生的费用，为改变排样方式产生的费用，为和分别为需求材料的上下界，当时，表明该种排样方式没有被使用，因此不用改变排样方式，即费用为当时，。顺序启发式算法的步骤为设定预设参数。根据当前参数来设定预设值。根据下料模型来获取种排样方式。若当前的排样方式满足要求，转否则，降低预定数，转。求出该排样方式的最大可使用次数并使用判断剩余的原材料是否使用完成否则，。顺序启发式算法是借鉴人工下料过程中通常采取的些方法，这种算法的优点是算法易于实现原材料的坯料种数不多时具有计算速度快得到的解定是整数解整体节材效果较好等优点。缺点是在获取种排样方案时优先采用效果好的排样方式，可能会导致后面生成的排样方式效果不好，造成最终排样方案的材料利用率不太高，排样方式数稍多的情况。基于这个问题，许多学者开展了大量相关的研究，以该方法为基础提出了系列的改进算法，如加入多种启发式策略，从中优选效果最好的，或与其他优化算法结合在起使用，都对排样结果有定的改进，但缺点是当需求材料种数较多时，计算时间太长。随机搜索算法随机搜索算法也是种较为常见的解维下料问题的算法。简单来说，随机搜索算法就是对待排样的各规格坯料进行随机的组合，组合成万方数据硕士学位论文薄膜的瑕疵检测与下料分切研究作者卢伟康导师邹细勇副教授学科物理电子学中国计量学院二〇四年三月万方数据，万方数据中图分类号学校代码密级公开硕士学位论文薄膜的瑕疵检测与下料分切研究作者卢伟康导师邹细勇副教授申请学位工学硕士培养单位中国计量学院学科专业物理电子学研究方向嵌入式技术二〇四年三月万方数据独创性声明本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取得的研究成果，除了文中特别加以标注和致谢之处外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含为获得中国计量学院或其他教育机构的学位或证书而使用过的材料。与我同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示了谢意。学位论文作者签名签字日期年月日学位论文版权使用授权书本学位论文作者完全了解中国计量学院有关保留使用学位论文的规定。特授权中国计量学院可以将学位论文的全部或部分内容编入有关数据库进行检索，并采用影印缩印或扫描等复制手段保存汇编以供查阅和借阅。同意学校向国家有关部门或机构送交论文的复印件和磁盘。保密的学位论文在解密后适用本授权说明学位论文作者签名导师签名签字日期年月日签字日期年月日万方数据万方数据致谢两年多的研究生生涯即将结束，经过这两年多的历练，我收获了很多，也感悟了很多。在此之际，我发自内心的对我的学校我的导师我的同窗们表示由衷地感谢。首先我要感谢的是我的导师邹细勇副教授，在我初入研究生生涯之初，什么都不太懂的我在邹老师的细心教导下，逐步的对研究生生涯有了个好的规划，并且从中学到了不少科研的知识。邹老师可谓亦师亦友，在教导我的同时，也会同我探讨学术问题，并且也会关心的我个人生活问题，给了我个很好的生活和科研环境，使我能全身心的投入科研，投入学习中去。除此之外，邹老师为人和善，有着严谨的科研态度，在我的论文的选题研究及论文的完成上都倾注了他全心全意的指导和帮助。邹老师的是我学习生涯中非常重要的位导师，更是我人