基于启发性规则及关键路径调整的柔性作业调度优化算法

为克服传统进化算法求解较大型柔性作业调度问题计算时间长和结果不稳定的缺点,提出了一种启发性规则求解方法.该方法用一个启发性规则产生初始调度解,再利用一些启发式规则对初始调度过程中的关键工件及关键工序进行搜索,并对关键路径进行优化调整得到较优解,通过比较得到柔性调度问题的优化调度解.用本文方法对典型柔性调度问题进行求解,并与其他算法的求解结果进行比较,对于15×10问题,采用本文方法的计算结果与混合基因算法相同,计算时间为3.2 s,减少了42%;对于23×10及25×10的较大型问题,表明启发性规则的引入能提高求解效率,与传统进化算法相比,更适合求解较复杂的柔性作业调度问题.

Optimization Algorithm for Flexible Job-Shop Scheduling Problem Based on Heuristic Rules and Adjustment of Critical Paths

In order to overcome the disadvantages of long computing time and unstable result of traditional evolutionary algorithms in solving the optimization for large flexible job-shop problems(FJSPs),a heuristic critical path approach(HCPA) was proposed.This method first uses a heuristic rule to get some preliminary schedules.Then,critical workpieces and key process of these preliminary schedules are searched and critical paths are locally adjusted using some heuristic rules for better solutions.Finally,the optimal schedule of FJSP is obtained by comparison among these solutions.The proposed approach was applied to benchmark FJSPs,and the solutions were compared with those of other approaches.The results show that for the 15×10 FJSP,the values of evaluation indexes computed by the proposed method are nearly the same as those by the integrated genetic algorithm,but the computing time(only 3.2 s) is reduced by 42%.The large FJSPs of 23×10 and 25×10 are also calculated,reflecting that introduction of heuristic rules can improve the computing efficiency and solution stability;compared with the traditional evolutionary algorithms,the proposed method is more suitable for real-time solution of difficult FJSPs.