解决柔性车间作业调度问题的侦查包围搜索算法

摘要

车间作业调度算法是影响车间生产效率的重要因素之一. 由于调度算法属于NP-难问题,至今仍然没有办法在有限时间内找到最优解. 文章提出了一种元启发式搜索方法:侦查包围算法( PEA) ,通过局部搜索,旨在有限时间内最大可能的趋近于最优解. 该算法吸取了禁忌搜索算法和模拟退火算法的优点,对其缺点进行改进. 文中将此算法应用到柔性车间作业调度问题,阐述算法的实践. 实验结果与遗传算法和禁忌搜索进行比较,证明在作业数目较大的情况下,具有良好的效果.%Scheduling Algorithm has become one of the most important factors which influence Job-shop productivity. Because of being proved as NP-hard problem, there are no Job-shop Scheduling Algorithms can achieve optimal solution. This paper proposes a meta-algorithm:Probe and Encircle Algorithm ( PEA) aim to get the approximate optimum solution via local search within a limited time. This algorithm absorbs the merit of Taboo Search Algorithm ( TSA) and The Simulated Annealing Algorithm ( SAA) , and so do a-void their flaws. A Flexible Job-shop Scheduling Problem has been solved by Probe and Encircle Algorithm which will be described in detail. Compared with GA and TS, it has been proved more effective in large scale problems.