离散猫群优化算法求解带交货期的FJSP问题

针对带交货期的柔性作业车间调度问题(flexible job shop scheduling problem,FJSP),提出一种离散猫群优化算法(discrete cat swarm optimization,DCSO),以优化工件最大完工时间和平均提前/拖期时间.首先,设计一种两段式离散编码方式,用于表示调度解,并采用启发式算法实现种群初始化;其次,为了使算法能够直接在离散调度空间内运行,在搜寻模式下设计基于3种不同邻域结构的搜寻方法,并在跟踪模式下提出一种新型离散个体更新公式;再次,采用线性自适应猫群行为模式选择策略,协调算法全局搜索和局部搜索的能力;最后,为了进一步改善计算结果,在算法中嵌入一种局部搜索策略.通过基准算例测试DCSO算法的性能,仿真结果表明所提DCSO算法在求解FJSP问题方面的有效性.

Discrete cat swarm optimization algorithm for solving the FJSP with due date

For the flexible job shop scheduling problem(FJSP) with due date, a discrete cat swarm optimization(DCSO) algorithm is proposed to optimize the makespan and the mean earliness/tardiness. Firstly, a two-phase discrete encoding approach is designed to represent the scheduling solution, and a heuristic-based method is adopted to fulfill the population initialization. Then, in order to make the algorithm work directly in a discrete scheduling space, a seeking method is developed based on three different neighborhood structures in the seeking mode, and a new discrete individual updating equation is proposed in the tracking mode. To coordinate the global and local search capability of the proposed algorithm, a linear adaptive selection strategy of cat''s behavior modes is used. In addition, a local search strategy is embedded into the algorithm to further improve the computational results. Finally, the performance of the DCSO algorithm is tested based on the benchmark instances, and experimental data demonstrate the effectiveness of the proposed DCSO algorithm on solving the FJSP.