两阶段流水车间批调度问题的蚁群算法研究

《两阶段流水车间批调度问题的蚁群算法研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、中国科学技术大学硕士学位论两阶段流水车间批调度问题的蚁群算法研究作者姓名：学科专业：导师姓名：完成时间：陈成栋管理科学与工程陈华平教授二。一二年五月文Antcolonyoptimizationfortwo·stageflowshopschedulingproblemWI-t-nIIbatchprocessingmachinesAuthor’sName：ChengdongChenspeciality：ManagementScienceandEngineeringSupervisor：Prof．HuapingChenFinishedtim

2、e：May28n1，2012一a-ceh3，∞怜f，rL～斫叼y—J言；d0Sb。S叫rn3_l№bCh>耽弱dn¨m■■I，引旷雕幻Cn．旧OC“¨&甜O旷¨吟小．S引蛳垤d●■■_LnA圳A中国科学技术大学学位论文原创性声明本人声明所呈交的学位论文，是本人在导师指导下进行研究工作所取得的成果。除已特别加以标注和致谢的地方外，论文中不包含任何他人已经发表或撰写过的研究成果。与我一同工作的同志对本研究所做的贡献均已在论文中作了明确的说明。作者签名：尸灰威掀签字日期：劲

3、2霹y玛’s哆中国科学技术大学学位论文授权使用声明作为申请学位的条

4、件之一，学位论文著作权拥有者授权中国科学技术大学拥有学位论文的部分使用权，即：学校有权按有关规定向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅，可以将学位论文编入《中国学位论文全文数据库》等有关数据库进行检索9可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。本人提交的电子文档的内容和纸质论文的内容相一致。保密的学位论文在解密后也遵守此规定。

5、硇公开口保密(——年)．作者签名：区盎筮导师签名：签字日期：■型印印?寸，I签字日期：。孑础JZ,倭Sq战国摘要生产调度问题是一类常见的组合优化问题，在实际的生产中具有广

6、泛的应用。高效的调度方案可以提高生产设备利用率、降低成本，增加企业的利润。批调度问题是生产调度问题的一个分支，在半导体生产以及网络通信等领域都具有重要的研究价值。批调度问题中的批处理机指的是在同一时间能够加工多个工件的机器。将批调度问题与流水车间问题相结合，可以组成更为复杂的流水车间批调度问题。本文研究差异工件两阶段流水车间批调度问题，目标函数是最小化加工时间跨度。其中待加工工件具有不同的尺寸，批的加工时间等于批中工件加工时间的最大值，批中的工件尺寸之和不超过机器容量限制。目前对相同问题进行研究的文献还很少。本文首先对生产调度问题的概

7、念、分类、三参数表示法和求解方法进行了简单介绍，同时对两阶段流水车间批调度问题进行重点描述并做了文献回顾。其次对批调度问题的常用近似算法进行了回顾，包括基于简单启发式规则的算法和元启发式算法。分为单机批调度问题和两阶段流水车间批调度问题两个部分描述。接着，本文对两阶段流水车间批调度问题的蚁群优化算法求解过程进行了设计。蚁群优化算法采用基于批序列的编码方式；基于批中工件在每阶段的加工时间相似程度(标准差衡量)，提出一个能够提高批中工件加工时间相似水平的启发式信息；同时针对问题的特性设计了信息素的更新方式并引入基于工件交换策略的局部优化算

8、法来提高算法性能。另外，为了减少蚁群算法的求解运行时间，设计了多态蚁群算法在本文问题中的应用以降低解空间的搜索规模。仿真结果表明，与以往文献中的算法相比，蚁群算法具有较好的求解性能，尤其是在工件规模比较大的情况下；多态蚁群算法也具有很好的求解性能，尤其是在工件尺寸比较小的情况下。最后对本文的研究内容进行了总结并展望了问题的进一步研究方向。关键词：流水车间批处理机调度蚁群算法组合优化多态摘要IIAbstractABSTRACTProductionschedulingisoneofthecommoncombinatorialoptimiz

9、ationproblems，anditiswidelyusedintherealproductionenvironment．AnefficientschedulingschemeCanimprovetheutilizationsofequipments、reducecostsandincreasetheprofitsofenterprises．Batchschedulingisabranchofproductionscheduling．Ithasimportantresearchvalueintheareasofsemiconduct

10、ormanufacturingandnetworkcommunication．Inbatchscheduling，batchprocessingmachinesCanprocessmorethanonejobinthes