刘 敏 张超勇 张国军 孙 艺
华中科技大学数字制造装备与技术国家重点实验室,武汉,430074
置换流水车间调度问题(permutation flow shop scheduling problem,PFSSP)是目前研究最广泛的一类典型调度问题,具有很重要的工程应用价值。然而,绝大多数PFSSP(工件数n≥3)是NP-hard问题,不存在多项式精确求解算法,因此,对该问题的研究不仅具有重要的实际意义,而且具有重要的理论意义。
国内外学者在过去几十年里做了大量研究,提出了许多解决置换流水车间调度问题的方法。这些方法大致可分为三类:精确算法、启发式算法和元启发式算法。由于NP-hard问题的复杂性,精确算法只适用于小规模问题的求解。启发式算法能够快速构造解,但是通常解的质量较差。元启发式算法能在较短时间内获得较高质量的解,因此在求解置换流水车间调度问题中获得广泛应用。
粒子群优化(particle swarm optimization,PSO)算法是受鸟群捕食启发产生的元启发式算法,也是一种基于群体的优化算法,最早由Kennedy等[1]于1995年提出。PSO算法是通过种群内粒子之间的合作与竞争而产生的群体智能优化算法。与遗传算法(genetic algorithm,GA)相比,PSO算法保留了基于种群的全局搜索策略,搜索模型简单,收敛速度快,鲁棒性高,但是,PSO算法主要用于无约束连续函数的优化。
目前,PSO算法在解决连续函数优化方面取得了成功,但在如何应用于离散组合优化问题方面尚处于探索阶段,其解决离散组合优化问题主要有以下两条途径,一是采用基于随机键的最小位置值(smallest position value,SPV)规则将标准PSO算法应用于组合优化问题中,二是采用向量编码方式的离散粒子群算法解决离散组合优化问题。……