柔性Job Shops集成调度启发式算法

Hybrid heuristic algorithm for integrated scheduling in flexible Job Shops

为有效解决柔性作业车间(Job Shops)的加工与搬运集成调度问题,以最小化最大完工时间(Makespan)为调度目标,建立非线性规划模型,提出基于贪婪启发式策略的变邻域搜索算法(GRS-RVNS).根据准时(JIT)生产和均衡生产思想构建贪婪启发式策略快速求初始解.利用析取图表示可行解并根据析取图调度的性质定理构建有效的搜索邻域,进而利用随机变邻域搜索算法对初始解进行优化.对提出的算法进行仿真实验分析,结果表明:该算法求解时间短、调度方法有竞争性.

The non-linear programming model was developed with an objective of minimizing system Makespan to solve the integrated scheduling problem of processing and handling in flexible job shops effectively.A greedy heuristic strategy based variable neighborhood search algorithm（GRS-RVNS）was put forward.The greedy heuristic strategy was designed with the combination of the just in time（JIT）and balanced production ideas,in order to get initial solution rapidly.An effective neighbor was constructed based on the disjunctive graph representations of the feasible solutions and properties and theorems of the disjunctive graph scheduling.The neighbor was used in the random variable neighborhood search algorithm.Finally,the experiments were designed for the proposed algorithm.Results indicate that the computing time of the proposed algorithm is short and the scheduling method is promising.