极小化总完工时间批调度问题的两种蚁群算法

《极小化总完工时间批调度问题的两种蚁群算法》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、万方数据第16卷第6期2010年6月计算机集成制造系统ComputerIntegratedManufacturingSystemsV01．16NO．6June2010文章编号：1006—591l(2010)06—1255—10极小化总完工时间批调度问题的两种蚁群算法许瑞，陈华平，邵浩，王栓狮(中国科学技术大学管理学院，安徽合肥230026)摘要：针对考虑工件尺寸不同，求鹪目标为极小化总完工时间的批调度问题，考虑不同的编码方式，提出了基于工件序列的蚁群算法和基于批序列的蚁群算法。基于工件序列的蚁群算法算法采用传统的工件序列编码，需要启发

2、式规则进行分批；基于批序列的蚁群算法算法利用蚁群算法构建性编码的特点。不需要启发式规则，而采取直接分批的方式编码，充分发挥蚁群算法自身的搜索能力。针对总完工时间的优化目标，基于批序列的蚁群算法算法引入批权重构建启发式信息；针对批调度特有性质，基于批序列的蚁群算法算法加入新的信息素更新变量，设置不同的信息素初始值，并采用局部优化技术等改进措施，以克服传统蚁群算法收敛速度慢，易陷入局部最优的缺点。通过对比实验验证_r所提算法的有效性。关键词：批调度；工件尺寸；总完工时间；蚁群算法；启发式算法中图分类号：TP301文献标志码：ATwokin

3、dsofantcolonyalgorithmstominimizethetotalcompletiontimeforbatchschedulingproblemXURui，CHENHua—ping，SHAOHao，WANGShuan—shi(SchoolofManagement。UniversityofScience＆TechnologyofChina，Hefei230026，China)Abstract：Aimingattheproblemofminimizingthetotalcompletiontimeforasinglebat

4、chprocessingmachinewithnon—identicaljobsizes，consideringdifferentcodingmethods，JobSequencebasedAntColonyAlgorithm(JSACA)andBatchSequencebasedAntColonyAlgorithm(BSACA)wereproposed．JSACAusedtraditionalcodingmethodbasedonjobsequence，batchingjobswithheuristic；BSACAtookadvan

5、tagesofconstructivecodingmethodofACAwithoutdependingontheheuristics．Itbatchedjobsdirectlyandplayeditsownoptimizationability．Aimingattheoptimizationobjectiveoftotalcompletiontime，BSACAintroducedbatch-weighttoconstructheuristics．Toover—comethedisadvantagesoflowerconvergen

6、cespeedandtrappinginlocaloptimuminthetraditionalACA．BSACAaddedanewpheromoneupdatevariable，setdifferentpheromoneinitialvalueandadoptedlocaloptimization，whichwerebasedonthecharacteristicsofbatchscheduling．Theeffectivenessoftheproposedalgorithmswasverifiedbycomparativeexpe

7、riment．Keywords：batchscheduling；jobsize；totalcompletiontime；antcolonyalgorithms；heuristicalgorithms0引言批调度是具有极强应用背景的一类新型调度问题。以往文献中求解批调度问题的优化目标多是极小化最大完工时间(C。。)，而在现实的工业生产环境中，还存在着许多目标为极小化总完工时间的批调度问题，在此简称此类问题为SUMCI问题。此类目标问题的求解，不仅要考虑分批的数目，还要考虑每批中的工件数目以及批排序的问题，这些特点使得SUMCI问题的求解

8、不同于传统的C。。问题。本文研究的是SUMCI的工件尺寸不同的批调度问题，采用生产调度环境的三参数表示法，即1B，Si收稿日期：2009-07—27；修订El期：2009—10—13。Received27July2009