CAJ | 학술논문

车间作业调度算法是影响车间生产效率的重要因素之一. 由于调度算法属于NP-难问题,至今仍然没有办法在有限时间内找到最优解. 文章提出了一种元启发式搜索方法:侦查包围算法( PEA) ,通过局部搜索,旨在有限时间内最大可能的趋近于最优解. 该算法吸取了禁忌搜索算法和模拟退火算法的优点,对其缺点进行改进. 文中将此算法应用到柔性车间作业调度问题,阐述算法的实践. 实验结果与遗传算法和禁忌搜索进行比较,证明在作业数目较大的情况下,具有良好的效果.
차간작업조도산법시영향차간생산효솔적중요인소지일. 유우조도산법속우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.