求解FJSP的混合遗传—蚁群算法

Hybrid genetic algorithm-ant colony optimization for FJSP solution

为更有效地求解柔性作业车间调度问题,综合考虑其中的机器分配与工序排序问题,建立了相关析取图模型,提出一种混合遗传—蚁群算法。该算法首先通过遗传算法获取问题的较优解,据此给出蚁群算法的信息素初始分布;之后充分利用蚁群算法的正反馈性进行求解,采用精英策略对蚁群的信息素进行局部更新;最后借鉴遗传算法交叉算子的邻域搜索特性扩大蚁群算法解的搜索空间,从而改善解的质量。通过3个经典算例的实验仿真,以及与其他算法的比较,验证了所提算法的可行性与有效性。

To solve Flexible Job-Shop Scheduling Problem（FJSP）more effectively, a related disjunctive graph model was built and a hybrid Genetic Algorithm（GA）-Ant Colony Optimization（ ACO） was proposed by considering equip- ments arrangement and operation sequencing. In this algorithm, a better solution to the problem was obtained by ge- netic algorithm, and pheromones initial distribution of ACO was provided on this basis. The positive feedback of ACO was used to solve the problem, and the local update of the pheromones were conducted by elitist strategy. The neighborhood searching feature of crossover operator in GA was used to increase the search space of ACO, thus the quality of solution was improved. Through the experimental simulation of 3 classical examples, the feasibility and effectiveness of proposed algorithm were verified.