求解流水车间调度问题的分解多目标局部搜索算法

《求解流水车间调度问题的分解多目标局部搜索算法》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、’、、：‘＇巧．．、巧ｒ．＞，鴻苗＾幕巧：＇＂．．’．北／讓衣如ｉ．人％棋骑解’－．‘；龜義凉苗Ｃ，貫苗Ｋ；—；，人．、：巧：学巧代码ｆ１０２００巧巧生学皂：２０１３１０２４７４古：艇己＞替；茸Ｓ；、‘’．．。；－：．！巧：二．分类号：、＞，巧级：丞，声亞扯Ｕ若＾、；’．．＇＇游軒．心二、：．．请记辜；Ｔ．卢Ｖ、＇Ｉ＇．＂＇’’＇八．’心’‘‘：？林、｜，心，：成可棘共’械Ｉ＇＇‘－－．１．苗髮品：‘咸Ｖ，辨批讀？＾＾—成＞言謂？響遲讓瑜：碰：：；－．：勸娜：；；群錢賴蟲拆為端群东批洽Ａ這逼满藻餐義義心．：

2、巧藻麵為．Ｖ硕±学位论文寒｜１議．！鲁着雜瞧．扉難＼一，＾—：；Ｖ．乂解洗水车间伯度问巧巧芳魚多目推＼＇巧部巧＊募法＾音致掉棘：．讀違．＇、‘、：心、■，．＞在ｉ；声？飞、－成狂Ｍｕｈｏｂｔ－ｉｊｅｅｉｖｅＬｏｃａｌＳｅａｒｃｈＡｌｇｏｒｉ化ｍＢａｓｅｄＤ说ｏｍ而啤ｏｎｆｏｒｐ；々－．冉—．．ＰｅｒｍｉｉｔａｔｉｏｉｉＦｌｏｗＳｈ叩ＳｃｈｅｄｕｌｉｎＰｒｏｂｌｅｍ、ｇ，立妥：篇備輸—＇》吞響龜幾，．＇：漏議擊‘．‘．．：告刪顺研究方向．或终私：肆．，；礁苗鑛，哪乾談孫聲姆’’＇＾；．＇．：、学纖型卸巧±

3、、－．．；各．，；ｖＡ护巧，—鮮．每與遗气．、？、、辦．－．．ＮＶ；：，Ｓ器Ｉ發／靡謀媒皆茄巧！‘‘－．谭為為兵纖节纖載應＇二谭；人东北．吉师范大学学位评定委会；员．．可蠻２０１６６：年月卢巧屬兴詩‘＇游鱗巧游？．．．．耀＾’霉磬知；ｒ瑚轟雙；穩慣辩：，１＃裤為疆蜜学校代码：10200研究生学号：2013102474分类号：G423密级：硕士学位论文求解流水车间调度问题的分解多目标局部搜索算法Multi-objectiveLocalSearchAlgorithm-BasedDecompositionforPermutationFlowShopSchedu

4、lingProblem作者：李明杰指导教师：殷明浩教授一级学科：计算机科学与技术二级学科：计算机软件与理论研究方向：智能信息处理学位类型：学术硕士东北师范大学学位评定委员会2016年6月摘要多目标流水车间调度问题在现实产生中应用极为广泛，其关注如何合理利用有限的时间和资源，满足多个产生目标的需求，以提高企业的经济效益和运行效率。其已被证明是NP难问题，精确算法很难在有限的时间内求出令人满意的结果，然而基于群体智能的进化算法和一些邻域搜索策略在处理这类问题上表现出极大的优势，引起了国内外学者的广泛关注和研究。本文研究解决两类多目标调度问题，即常规的多目标流水车间调度问题和带顺序相关调整时

5、间的多目标流水车间调度问题，而且均考虑两个生产目标的优化，即最小化最终完工时间和总流程时间。第二类问题是在第一类问题的基础上考虑了顺序相关的调整时间，在现实生产调度中，相邻作业之间会存在着一定的调整时间，比如清洗机器，释放资源等，而这些时间的消耗在设计调度方案的时候是不可忽略的。针对所考虑的问题，本文提出了一种高效的分解多目标局部搜索算法框架（简称MOLSD）。该算法框架利用聚合函数将所求解的多目标问题分解为若干个单目标子问题，然后对这些单目标子问题进行搜索和优化，从而实现多目标问题的优化。首先，本文提出一种基于调度问题的NEH启发式策略来初始化种群，使种群保持较好的多样性和适应性；接

6、着，一种结合重干扰操作的Pareto局部搜索作用于非支配解集，以扩大优良个体的搜索邻域；其次，利用快速非支配排序方法将当前种群分为精英个体和普通个体，这两种个体在后续阶段将会经历不同的进化和搜索操作。在处理种群的每个个体的时候，本文提出了一种基于插入操作的局部搜素算法和迭代局部搜索机制，分别负责种群的开采和挖掘工作，从而平衡了算法的开发和搜索能力，提高了整体算法的全局寻优能力。为了避免算法陷入局部最优，本文提出了双重干扰机制，即轻干扰机制和重干扰机制，分别对没有提高的普通个体和精英个体进行干扰操作。为了提高算法的鲁棒性和健壮性，一种改进的重启机制将作用于那些经历多次迭代进化依然没有得到

7、改善和提高的个体。在实验阶段，本文选取了大量学者广泛使用的基准测试实例来对算法进行性能评价和比较实验。首先，文本分别对MOLSD中的参数进行性能测试和分析，接着对所涉及的一些算法策略和机制进行有效性评估，最后本文将MOLSD与当前若干种优秀的基准算法进行性能比较和分析。最终的实验统计结果表明，在解决这两类多目标流水车间调度问题上，MOLSD的性能要高于其他基准算法。关键词：进化多目标优化；流水车间调度；Pareto局部搜索；局部搜索；分解；非支