基于微粒群算法的多阶段流水车间批调度问题研究

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

1、中国科学技术大学硕士学位论文基于微粒群算法的多阶段流水车间批调度问题研究作者姓名：学科专业：导师姓名：完成时间：朱颀管理科学与工程陈华平教授二。一二年五月UniwsityofS‘ndTechnol(g)ofChinaUniversicienceandechnoloS’．qyofChinaAdissertationformasterSdegreeMulti_-stageFlowShopSchedulingwithBatchProcessingMachinesBasedonParticleSwarmOptimizationAuthor

2、’SName：ZhuQispeciality：ManagementScienceandEngineeringSupervisor：ProfHuapingChenFinishedtime：May28nl，2012中国科学技术大学学位论文原创性声明本人声明所呈交的学位论文，是本人在导师指导下进行研究工作所取得的成果。除己特别加以标注和致谢的地方外，论文中不包含任何他人已经发表或撰写过的研究成果。与我一同工作的同志对本研究所做的贡献均己在论文中作了明确的说明。作者签名：丞塑中国科学技术大学学位论文授权使用声明作为申请学位的条件之一，学位

3、论文著作权拥有者授权中国科学技术大学拥有学位论文的部分使用权，即：学校有权按有关规定向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅，可以将学位论文编入《中国学位论文全文数据库》等有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。本人提交的电子文档的内容和纸质论文的内容相一致。保密的学位论文在解密后也遵守此规定。团公开口保密(——年)作者签名：趣签字日期：三!l羔：查：!星导师签名：签字日期：摘要流水车间批调度问题(flowshopschedulingproblem，FSP)是调度问题中流

4、水车间问题与批调度问题的组合。此类问题与一般流水车间问题的不同之处在于，流水车间中的机器均为批处理机。由于此类问题不光需要将所有工件分成不同的批，还要安排批的加工顺序，因此比普通的置换流水车间问题(permutationflowshopproblem，PFSP)更加复杂。差异工件的分批问题已被证明为NP难题，而机器数量大于2台的流水车间问题也被证明为NP难题，因此流水车间批调度问题在差异工件的情况下也为NP难题。FSP问题是生产调度问题当中一类十分重要的问题，在实际的生产环境中流水车间普遍存在，而其中包含批处理机的情况也很多。一个

5、实际的例子为电子工业的环境应力筛选，整个过程可抽象为一个典型的流水车间批调度问题。环境应力筛选由半导体工业的老化试验发展而来，整个产品需要在用户设定的不同环境下进行测试，每个筛选试验箱可以看作一个批处理机，数量由待测试的装配车间的数量以及特定装备车间的测试数量决定。因此，对FSP问题的研究显得十分必要。流水车间批调度问题目前已经有了一些研究文献，但是研究的方向多为两阶段的情况，即两台机器的情况。其中包括两阶段均为批处理机的研究，也有批处理机与普通机器或者平行机的混合情况。多阶段(即大于两阶段)的情况目前鲜有研究。在总结了FSP问题

6、目前的研究现状的基础上，本论文做了以下主要工作：(1)首先本文介绍了目前生产调度最为通用的描述方式，介绍了调度问题的分类。之后通过介绍计算复杂性的相关知识引出了FSP问题在多阶段情况下的研究特点和难点。对调度问题的研究方法做了梳理和总结。对智能算法中新兴的微粒群算法(particleswal'moptimization，PS0)做了介绍，结合微粒群算法的原理、特点以及参数设置，总结微粒群算法的优缺点并对微粒群算法的改进策略做了思考。(2)研究了流水车间差异工件批调度问题的求解方法，鉴于目前只有小规模工件的研究，尝试了大规模工件下的

7、求解，并将研究重点放在如何优化批的加工方面。在工件分批阶段采用了BestFit(BF)规则生成分批，采用Palmer启发式规则对工件序列做了初始化；在批的加工阶段，由于PSO算法的编码方式十分适合求解多阶段流水车间批调度问题，本文首次尝试了将其应用于批加工阶段，同时选取了NEH启发式规则作对比算法。在仿真实验中对分批算法的改进性能以及NEH(Nawaz，EnscoreandHam)和PSO算法在批加工阶段的性能做了实验分析。(3)在论文的第四章针对PS0算法的不足之处做了进一步改进：在微粒的初始摘要化阶段，对其中的部分微粒采用了N

8、EH算法初始化了部分微粒；为了平衡PSO算法的全局搜索和局部搜索效果，采用了一种自适应惯性权系数(adaptiveinertiaweightfactor,A1WF)；在PSO算法更新gbest时引入了变邻域搜索(variableneighborho