布谷鸟算法求解置换流水车间调度问题

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

1、第35卷第3期数学理论与应用V01．35No．32015年9月MATHEMATICAITHEORYANDAPPLICATIONSSep．2015布谷鸟算法求解置换流水车间调度问题徐杨丽叶春明(上海理工大学管理学院，上海，200093)摘要置换流水车间调度问题是典型的生产调度问题，当其规模大于3时已被证明是Np—hard问题．布谷鸟算法是新妁群体智能算法，该算法选用参数少且有较强的全局寻优能力．采用最大位置法编码，以最小化最大完工时间为目标，为验证该算法在不同参数支配下的寻优效果，分别在不同影响因

2、素下对Car8问题独立运行100次．为验证算法的优化性能，将Carl—Car8问题的寻优结果与猫群算法寻优结果相比较．结果均证明该算法求解离散调度问题的优越的优化性能．关键词置换流水车间最小化最大完工时间布谷鸟算法最大位置法CuckooSearchAlgorithmforSolvingPermutationFlow——shopSchedulingProblemsXuYangliYeChunming(BusinessSchool，UniversityofShanghaiforScienceandT

3、echnology，Shanghai200093，China)AbstractPermutationFlow—shopSchedulingProblem(PFSP)isaclassicalproblemofproductionscheduling．ItiSshowntobeanNP—hardproblemwhenthescaleiSmorethanthree．CuckooSearch(CS)algorithmiSanewswarmintelligencealgorithm，whichhasstr

4、ongglobalsearchabilitywithfewparameters．TotesttheperformanceoftheCSalgorithmtheCar8problemforminimizingmakespanisrtln100timeswithdiferentparameters，wherethecoderuleisbasedonthemaximalpositionofeachnest．ComparedwiththecatSWalllloptimizationalgorithmin

5、sol—vingCarl—Car8problems，theCSgivesbetterperformance．KeywordsPFSPMakespanCuckooSearchMaximalposition1引言生产调度问题是对机器进行加工任务的安排，将工件分配到相应的机器上，确定各机器上加工操作的加工操作顺序和开始加工时间，使某一个或几个调度优化准则达到最优．有效的调度优化算法便于现代商业领域增加产出、减少周转时间、减少库存，提高生产效率，最终减少生产费用、增加利润，提高客户满意度．置换流水车间生

6、产调度问题(PermutationFlow—shop国家自然科学基金资助项目(71271138)；上海市一流学科建设项目(S1205YLXK)收稿日期：2015年4月23日90数学理论与应用SchedulingProblem，PFSP)是制造业生产中一类典型的Np—hard⋯问题，是生产调度问题的简化形式．对PFSP问题求解方法的研究，有利于企业在进行生产制造时及时找到优良的调度策略，合理分配资源和时间，节约成本，提高整个行业的效率．PFSP问题求解的方法很多，精确算法能求出问题的精确解，主要包

7、括分支定界法、整数规划法、动态规划法等，但是受问题规模和计算复杂度的影响，精确算法只适于求解小规模调度问题，对大规模调度问题求解能力不足；近似算法的出现解决了大规模调度问题寻优的难题，近似算法可分为构造型算法和智能优化算法．构造型算法如NEH启发式算法能够快速求得问题的调度解，但是构造比较复杂，且通常不能寻得问题最优解；智能优化算法等通过对邻域的不断搜索和对当前解的持续改进，能在较短的时间内寻得问题最优解或满意解，如粒子群算法口]、遗传算法]、萤火虫算法H以及各种算法的混合算法等均能取得较好的优

8、化效果，目前已广泛应用于多种生产调度问题．布谷鸟搜索算法(CuckooSearch，CS)，也叫杜鹃搜索，是由剑桥大学YangXin—She(杨新社)教授和S．Deb于2009年提出的一种新兴启发式算法．cs算法通过模拟某些种属布谷鸟(CuckooSpecies)的寄生育雏(BroodParasitism)来有效地求解最优化问题，这种算法简单高效、全局搜索能力强、选用参数少，搜索路径优．国内已有文献大多将布谷鸟算法应用于求解项目管理中资源调度]、函数优化]、整数规划等问题中，对布谷鸟算法应用到生