基于粒子群优化和禁忌搜索的混合调度算法

摘要

A discrete particle swarm optimisation (PS0) algorithm is presented for Job Shop Scheduling problem. In the algorithm, a preference list-based representation code and update model for new positions are applied so as to make the PSO with incessant nature straight suitable for the Job Shop Scheduling problem. Based on excellent whole search ability of PSO and self-adaptive merit of Tabu Search (TS), two hybrid procedures, named GPS0 and PTS, are put forward by combining PSO and TS. Experimental results demonstrate that within the framework of two newly designed hybrid algorithms, the Job Shop Scheduling problem can be solved efficiently with high quality.%提出了用于解决作业车间调度问题的离散版粒子群优化算法.该算法采用基于先后表编码方案和新的位移更新模型,使具有连续本质的粒子群优化算法直接适用于车间调度问题.同时,利用粒子群优化算法的全局搜索能力和禁忌搜索算法的自适应优点,将粒子群优化算法和禁忌搜索结合起来,设计了广义粒子群优化算法和粒子群一禁忌搜索交替算法两种混合调度算法.实验结果表明,两种混合调度算法能够有效地、高质量地解决作业车间调度问题.