求解置换流水车间调度问题的memetic算法

《求解置换流水车间调度问题的memetic算法》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、第２３卷第６期厦门理工学院学报Ｖｏｌ．２３Ｎｏ．６２０１５年１２月ＪｏｕｒｎａｌｏｆＸｉａｍｅｎＵｎｉｖｅｒｓｉｔｙｏｆＴｅｃｈｎｏｌｏｇｙＤｅｃ．２０１５求解置换流水车间调度问题的Ｍｅｍｅｔｉｃ算法苏志雄，伊俊敏（厦门理工学院管理学院，福建厦门３６１０２４）［摘要］针对以最小化最大完工时间为目标的置换流水车间调度问题，建立了０－１型混合整数线性规划模型。在对模型进行Ｂｅｎｄｅｒｓ分解的基础上，提出了问题的求解策略，进而设计了一种Ｍｅｍｅｔｉｃ调度算法，并探讨了基于组合规则的种群初始化方法和混合遗传操作。为了提高算法的

2、搜索效率，采用了更加高效的适应度值计算方法以及两种邻域搜索方法。最后，基于Ｂｅｎｃｈｍａｒｋ算例的仿真实验结果表明了该算法的有效性，可以找到２６个算例中的１７个最优解（６５?３８％），且其平均相对误差的均值仅为０?８８％。［关键词］生产调度；置换流水车间；Ｍｅｍｅｔｉｃ算法；邻域搜索［中图分类号］Ｆ２７３；ＴＰ２７８［文献标志码］Ａ［文章编号］１６７３－４４３２（２０１５）０６－００２５－０５流水车间调度问题通常可以描述为ｎ个工件要在ｍ台机器上加工，每个工件有ｍ道工序，每道工序都要在不同的机器上加工，所有工件的加工顺序

3、都相同，各工件在各机器上的加工时间已知，调度目标是确定每台机器上工件的加工顺序及开工时间，使得特定的性能指标最优。置换流水车间调度问题（ｐｅｒｍｕｔａｔｉｏｎｆｌｏｗｓｈｏｐｓｃｈｅｄｕｌｉｎｇｐｒｏｂｌｅｍｓ，ＰＦＳＰ）是对流水车间调度问题的进一步约束，即约定每台机器上所有工件的加工顺序相同，其解空间的规模为ｎ！，远远小于流水车间调度问题的规模ｍ（ｎ！）。ＰＦＳＰ中的最小化最大完工时间问题，利用三元组表示法可以记为ＦｐｒｍｕＣ，此类调度ｍａｘ问题是研究流水车间调度问题最为自然的起点，其研究成果可以为更加复杂的实际调度

4、问题研究提供基础，因此研究和开发高效的生产调度算法具有非常重要的理论意义和应用价值。［１］［２－５］由于此类调度问题的ＮＰ难特性，精确算法只能求解很小规模的算例，而启发式算法可以在很短的时间内获得调度解，但是其求解质量和通用性较差。因此，近期的研究重点更多地集中在元［６－１１］启发式算法。遗传算法作为一种常用的元启发式算法，具有鲁棒性、通用性、隐含并行性等特点，在求解ＰＦＳＰ上取得了较好的效果。然而，传统的遗传算法存在进化停滞和计算时间长等问题，故本文在问题分析和已有算法研究的基础上，提出了一种将遗传算法与邻域搜索相结

5、合的Ｍｅｍｅｔｉｃ算法（ｍｅｍｅｔｉｃａｌｇｏｒｉｔｈｍ，ＭＡ），其关键在于种群初始化策略、遗传操作、邻域搜索算法的设计。最后，通过基于ｂｅｎｃｈｍａｒｋ算例的对比实验对其有效性进行了验证。一、ＰＦＳＰ的数学模型１．符号说明为了叙述方便，引入下列符号：ｉ为机器编号，ｉ∈｛１，…，ｍ｝；ｊ为工件编号，ｊ∈｛１，…，ｎ｝；ｋ为排列中的位置编号，ｋ∈｛１，…，ｎ｝；π为所有工件的一个排列，即工件加工顺序方案，π＝｛π，π，１２…，π｝；ｐ为工件ｊ在机器ｉ上的加工时间；Ｐ为工件π在机器ｉ上的加工时间；ｘ为１，如果工件ｎｉｊｉｋ

6、ｋｊｋｊ位于排列π中的第ｋ个位置，否则为０；Ｃ为工件π在机器ｉ上的完工时间；Ｃ为最大完工时间，ｉｋｋｍａｘ［收稿日期］２０１５－１０－１３［修回日期］２０１５－１１－１３［基金项目］国家自然科学基金项目（７１３７１１６２）；福建省自然科学基金项目（２０１４Ｊ０１２７１）；厦门理工学院高层次人才项目（ＹＳＫ１０００９Ｒ）［作者简介］苏志雄（１９８０－），男，讲师，博士，研究方向为生产计划与调度、运输调度。Ｅ⁃ｍａｉｌ：ｚ．ｓｕ＠１６３．ｃｏｍ·２６·厦门理工学院学报２０１５年即ｍａｋｅｓｐａｎ。２．模型的建立基于上述符号

7、说明，本文建立如下所示的０－１型混合整数线性规划模型（以下称为［Ｐ］模型）：ｍｉｎＣ，（１）ｍａｘｓ?ｔ?Ｃ＝Ｃ，（２）ｍａｘｍｎＣ≥Ｃ＋Ｐ，∀ｉ，ｋ，（３）ｉｋｉ，ｋ－１ｉｋＣ≥Ｃ＋Ｐ，∀ｉ，ｋ，（４）ｉｋｉ－１，ｋｉｋｎＰ＝∑ｘｐ，∀ｉ，ｋ，（５）ｉｋｊｋｉｊｊ＝１ｎ∑ｘｊｋ＝１，∀ｋ，（６）ｊ＝１ｎ∑ｘｊｋ＝１，∀ｊ，（７）ｋ＝１ｘ∈｛０，１｝，∀ｊ，ｋ，（８）ｊｋＣ≥０，∀ｉ，ｋ；Ｃ＝０，∀ｉ；Ｃ＝０，∀ｋ。（９）ｉｋｉ００ｋ上述模型中：式（１）表示目标函数为最小化最大完工时间；约束（２）表示最后一个工件在最后

8、一个机器上的完工时间为Ｃ；约束集（３）表示资源约束，即在同一机器上前一工件加工完，下ｍａｘ一工件才能开始加工；约束集（４）表示同一工件前一道工序完成后下一道工序才能开始；约束集（５）表示ｐ与Ｐ之间的关系，Ｐ取决于排序变量ｘ；约束集（６）表示排列中的每一位置有且仅有ｉｊｉｋｉｋｊｋ一个工件；约束集（７）表示每一个工件有且仅有一个位置