基于蚁群粒子群算法求解多目标柔性调度问题

Ant colony and particle swarm optimization algorithm-based solution to multi-objective flexible job-shop scheduling problems

通过分析多目标柔性作业车间调度问题中各目标的相互关系,提出一种主、从递阶结构的蚁群粒子群求解算法。算法中,主级为蚁群算法,在选择工件加工路径过程中实现设备总负荷和关键设备负荷最小化的目标;从级为粒子群算法,在主级工艺路径约束下的设备排产中实现工件流通时间最小化的目标。然后,以设备负荷和工序加工时间为启发式信息设计蚂蚁在工序可用设备间转移概率;基于粒子向量优先权值的大小关系设计解码方法实现设备上的工序排产。最后,通过仿真和比较实验,验证了该算法的有效性。

A hybrid of ant colony and particle swarm optimization algorithms was proposed to solve the multi-objective flexible job-shop scheduling problem based on the analysis of objectives and their relationship. The hybrid was formulated in a form of hierarchical structure. The ant colony algorithm was performed at the master level to minimize the total load and bottleneck load through selecting job-processing route, while the particle swarm optimization algorithm was carried out at the slave level to minimize the makespan through scheduling the operations with machines without violating the result from the master level. The transfer probabilities of ant between machines were designed by using heuristic information of processing time and machine load. The decoding method of particle vector was well designed in order to sequence operations of every machine based on the size relations of element priority values. The simulation and results from comparison with other algorithms demonstrate the effectiveness of the proposed algorithm.