基于改进和声搜索算法的车间作业调度问题研究

《基于改进和声搜索算法的车间作业调度问题研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、分类号密级ＵＤＣ＾＾南責恣式义务ＮＡＮＪＩＮＧＵＮＩＶＥＲＳＩＴＹＯＦＳＣＩ巨ＮＣＥ＆ＴＥＣＨＮＯＬＯＧＹ硕壬专业学位论文基于改进和声搜索算法的车间作业调度问题研究（题名和副题名）朱航（作者姓名）指导教师姓名黄波副教授学位类别工程硕去专业名称计算机技术研究方向车间作业调度与智能算法论文提交时间２０１５年１月注１；《国际十进分类法ＵＤＣ》的类号注明。声明本学位论文是我在导师的指导下取得的研究成果，尽我所知，在本学位论文中，除了加Ｗ标注和致谢的部分外，不包含其他

2、人已经发表或公布过的研究成果，也不包含我为获得任何教育机构的学位或学历而使用过的材料一。与我同工作的同事对本学位论文做出的贡献均已在论文中作了明确的说明。一研究生签名？年月曰；來或ｙ＞｜、書巧学位论文使用授权声明南京理工大学有权保存本学位论文的电子和纸质文档，可Ｗ借阅或上网公布本学位论文的部分或全部巧容，可向有关部口或机构送交并授权其保存、借阅或上网公布本学位论文的部分或全部内容。对于保密论文，按保密的有关规定和程序处理。研究生签名：本漸／年？月；３日硕±学位论文基于改进和声捜索算法的车间作业调度问题研究摘要

3、一车间作业调度问题（ＪｏｂＳｈｏＳｃｈｅｄｕｌｉｎＰｒｏｂｌｅｍＪＳＳＰ）是现代生产制造系统中ｐｇ，个广受关注的典型生产线调度问题。由于车间作业调度具有工艺路径约束和资源（机器）独占性约束一，使其成为了个ＮＰ难问题。本文研巧了基于改进和声搜索算法和模拟退火算法的混合算法。（ＩＨＳＳＡ）及其在解决车间作业调度问题中的应用首先，提出了基于改进和声搜索算法和模拟退火算法的混合算法ＩＨＳＳＡ。改进和声捜索算法（旧Ｓ）解决了基本和声捜索算法的音调微调概率（ＰＡＲ）和波动范围化Ｗ）取值固定所引发的问题，而且加快了搜索，不仅保证了算法早期搜索时和声

4、解的多样性后期的算法收敛速度。然而改进和声捜索算法对初始解的依赖性仍未降低，为了解决送个问题，在和声搜索算法生成初始解的过程中引入模拟退火过程，提高和声记忆库中初始解的适应度。同时使用模拟退火算法对和声搜索算法生成的新和声解进行搜索，用最终搜索结果取代新和声解，提高了算法搜索到全局最优解的可能性，也加快了算法的收敛速度。然后使用基于工序的编码方式对车间作业调度问题进行编码。基于工序的编码方式一保证了生成解的合法性，但是作为种离散的编码方式，不能被适用于连续问题的和声搜索算法直接使用。本文使用最大位畳排序（ＬＰＶ）规则实现离散问题的连续编码。

5、针对和声搜索算法会产生非法解的问题，提出了基于工件号的排序规则（ＲＯＪ），保证生成新和声解的合法性。ＩＨＳＳＡ最后，使用本文提出的算法对单机器加工和复杂作业的调度系统进行仿真实验，通过和已有算法运行结果的比较，证明了该算法在解决车间作业调度问题上的正确性和有效性。关键词；车间作业调度，和声搜索算法，模拟退火算法，混合策略，仿真系统ＩＡｂｓｔｒａｃｔ硕±学位论文ＡＪｂｓ化ａｃｔＴｈｅｊｏｂｓｈｏｐｓｃｈｅｄｕｌｉｎｇｐｒｏｂｌｅｍ（ＪＳＳＰ）ｉｓａｔｙｐｉｃａｌｐｒｏｄｕｃｔｉｏｎｓｃｈｅｄｕｌｉｎｇｐｒ

6、ｏｂｌｅｍｉｎ，ｍｏｄｅｍｍａｎｕｆａｃｔｕｒｉｎｓｓｔｅｍ．ＩｔｈａｓｒｅｃｅｉｖｅｄｒｅｓｅａｒｃｈｅｒｓｗｉｄｅｓｒｅａｄａｔｔｅｎｔｉｏｎＩｔｇｙｐ．ｉｓａＮＰ－ｔｒｈａｒｄｒｏｂｔｔｔｌｅｍｂｅｃａｕｓｅｉｔｈａｓｌ：ｈｅｒｏｃｅｓｓｉｎａｔｈｃｏｎｓａｉｎｔａｎｄ；ｈｅｅｘｃｌｕｓｉｖｅｃｏｎｓｒａｉｎｏｆｐｐｇｐｒｅｓｏｕｒｃｅｓｍａｃｈｉｎｅｓ．Ｔｈｉｓａｅｒｓｔｕｄｉｅｓｔｈｅｈｂｒｉｄａｌｏｒｉｔｈｍｏｆｉｍｒｏｖｅｄｈａｒｍｏｎｓｅａｒｃｈ（）ｐｐｙｇｐｙａｎｄ

7、ｓｉｍｕｌａｔｅｄａｎｎｅａｌｉｎｇａｌｇｏｒｉｔｈｍＩＨＳＳＡ．Ｔｈｅｈｙｂｒｉｄａｌｇｏｒｉｔｈｍｉｓａｐｐｌｉｅｄｔｏｓｏｌｖｅｔｈｅｏｂ（）ｊｓｈｏｓｃｈｅｄｕｌｉｎｒｏｂｌｅｍｐｇ．ｐＦｉｒｓｔｏｆａｌｔｈｅｈｂｒｉｄａｌｏｒｉｔｈｍｃａｌｅＩＨＳｌｏｒｔｈｍｗｈｉｃｈｉｓｂａｓｅｄｏｎｉｍｒｏｖｅｄｌｌｄＳＡａ，ｙｇｇｐｈａｒｍｏ打ｙｓｅａｒｃｈａｎｄｓｉｍｕｌａｔｅｄａｎｎｅａｌｉｎｇａｌｇｏｒｉｔｈｍｉｓｐｒｏｐｏｓｅｄ．Ｉｍｐｒｏｖｅｄｈａｒｍｏｎ