应用并行进化规划求解Job Shop调度问题

USING PARALLEL EVOLUTIONARY PROGRAMMING TO SOLVE THE JOB SHOP SCHEDULING PROBLEM

本文提出了运用进化规划方法求解具有柔性加工路径的Jop Shop调度问题.为了更有效地搜索解空间,在进化规划的变异操作中加入了启发式信息,同时为了防止群体过早收敛,采用并行进化规划,并对选择操作进行了改进.在并行进化规划中群体被平分为一些子群,每个子群体独立进化,周期性地交换最优个体.子群间的通信方式分为串行通信和并行通信两种.文中最后给出了仿真算例,并比较了这两种通信方式的优劣.

In this paper, an evolutionary programming based scheduling algorithm is presented to solve the Job Shop scheduling problem with flexible routings. In order to exploit the search space more efficiently, heuristic information is embedded in the mutation operators. In the mean time the parallel evolutionary programming is used with the modification on selection operator to prevent the population from precoovengence. In the proposed parallel evolutionary programming the population is divided into several subpopulations equally. Each subpopulation evolves independently and the bast individuals are exchanged between them periodically. The communication between subpopulations is classified into two classes, namely serial and parallel one. Finally simulation results are given to illustrate the efficiency of the presented algorithm and a comparison between the two communication schemes is also presented.