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

求解置换流水车间调度问题的布谷鸟算法.doc求解置换流水车间调度问题的布谷鸟算法
刘长平 1， 2， 叶春明 1
【摘 要】 摘要：分析了布谷鸟算法的优化机理和特点，针对最小化最大完工时 间的置换流水车间调度问题，采用基于最小位置值规则的随机键编码方式，应 用布谷鸟算法进行求解 .通过选取的标准算例对算法进行了仿真测试，并与萤火 虫算法和粒子群算法进行对比，测试结果表明了该算法求解置换流水车间调度 问题的有效性和优越性 .该方法可作为解决流水线生产调度问题的一种有效方法 . 【期刊名称】 上海理工大学学报
【年（卷）,期】2013（035）001
【总页数】 4
【关键词】 置换流水车间调度；布谷鸟算法；优化机理；最大完工时间 置换流水车间调度问题（ permutation flow shop scheduling problem ，
PFSP）是在流水车间调度问题约束的基础上，进一步增加所有工件在任一台机 器上的加工顺序均相同的约束后形成的生产调度问题，对 PFSP 的调度优化可 有效提高企业生产效益，但 Garey 等［ 1 ］早已证明机器数大于等于 3 的 PFSP 属于 NP 完全问题，尚无多项式计算复杂性的全局优化算法 .因此，针对 PFSP
研究和开发高效的优化技术具有重要的实际意义和工程价值 .综合现有文献，求
解 PFSP 的方法主要有经典算法、构造型算法和智能优化算法 .其中，经典算法 （如分支定界法、动态规划法等）可求得问题的精确解，但受问题规模和计算 复杂性的限制，只适于求解小规模问题 .构造型算法（如 NEH 法、 Rajendran 法等）能够快速建立问题的调度解，但构造复杂，且通常解的质量较差，主要 用于求解双机和三机 PFSP智能优化算法（如遗传算法［2 ］、蚁群算法］3 ］、