基于粒子群算法的并行多机调度问题研究

《基于粒子群算法的并行多机调度问题研究》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、万方数据第12卷第2期206年2月计算机集成制造系统ComputerIntegratedM删facturlⅡgSystemsV01．12No2Feb．206文章编号：1006—5911(2006)02—0183—05基于粒子群算法的并行多机调度问题研究刘志雄“2，王少梅2(1武汉科技大学机械自动化学院，湖北武汉430082．武汉理工大学物流工程学院，湖北武汉430063)摘要：将港口拖轮作业调度问题描述为一类带特殊工艺约束的并行多机调度问题，采用粒子群算法求解该类调度问题，提出了一种2维粒子表示方法，通过对粒子位置向量进行排序生成有效调度，并采用粒子位置向量多次交换的局部搜索方法来提高

2、算法的搜索效率。最后，通过计算验证了混合粒子群算法的有效性。关键词：粒子群算法；并行多机调度；特殊工艺约束；港口拖轮调度中圈分类号：TPl8文献标识码：AResearchoilparallelmachinesschedulingproblembasedonparticleswamioptimizationalgorithmLIUZhi--xion91⋯，WANGShaoⅧ，(1．Coil．ofMachinery＆Automation，WuhanUnivofS&T，Wuhan430081，China；2．Coil．dLogisticsEng．，WuhanUniv．ofTech．，W“1a

3、n430083，China)Abstract：PorttugboatoperationschedulingisregardedasparallelmachiaesschedulingproblemwithspecialprocessconstraintParticleswarmoptimizationalgorithmwasusedtosolvetheschedulingproblem．Thetwo—dimensionalparticlerepresentationofparallelmachinesschedulingwanpmposed，andvalidschedulingwasg

4、eneratedbysequencingpositionvectorsofparticles．ThelocalsearchapproachofrepeatedinterchangesoftheparticlepositionvectorswasproposedtoimprovesearchefficiencyFinallythehybridparticleswarlTtalgorithmwasvalidatedbycomputa—tion．Keywords：particleswarlTloptimizationalgorithm；parallelmachinesscheduling；s

5、pecialprocessconstraint；porttugboatscheduling0引言粒子群算法(ParticleSwarmOptimization，PSO)是由美国的Kennedy博士和Eberhar博士于1995年提出的一种基于群智能的进化类算法“_3]。该算法通过粒子在解空间追随最优粒子进行搜索，操作简单．易于实现。因此，一经提出，就得到了广大学者的关注，已经在函数优化、神经网络训练、模糊系统控制等领域得到了有效的应用，并进行了不断的改进。粒子群算法目前在离散的组合优化方面的研究还很少““，在生产调度领域的应用研究也亟待发展。本文通过分析港口拖轮作业过程，将拖轮调度看作

6、一类带特殊工艺约束的并行多机调度问题，采用基于粒子群算法与局部搜索方法相结合的方法，对该调度问题进行了研究。收稿日期：20041122；修订日期：2005叭17。Received22Nov．2004；acceptedl7Jan．2005．基金项目：武汉科技大学机械传动与制造工程湖北省重点实验室开放基金资助项目(2005A17)。FoundationitemzTheOpenResearchProjectsSupportedbytheProjectFundoftheHubeiProvinceKeyLaboratoryofMechanicalTransmissionandManufactur

7、ingEngineeringWuhanUniversityofS＆T，China(No．2005A17)．作者简介：刘志雄(1975)，男，湖北麻城人，武汉理工大学物流T程学院博士研究生，主要从事物流系统仿真优化及生产调度的研究。E—mailI[iLlzhixiong@mail．whutedu．cn。万方数据计算机集成制造系统第12卷1带特殊工艺约束的并行多机调度1．1港口拖轮调度港口拖轮作业系统口3是港口服务系统的重要组成部分，在港口，船舶排