蚁群算法在工艺规划与车间调度集成优化中的应用

Integrated process planning and scheduling based on an ant colony algorithm

为了解决工艺规划与车间调度集成(IPPS)问题,提出了一种改进的蚁群优化(ACO)算法.通过节点集、有向弧集、无向弧集,构建了一种基于图的IPPS优化模型.以零件加工时间作为启发式信息,设计蚂蚁在各节点间转移概率.通过蚂蚁访问图中不同的节点,构建对应的调度方案.根据不同阶段调度方案的最大完工时间调整各弧段信息素的挥发速度,提高了蚂蚁的搜索效率.为避免陷入局部收敛,通过重启算法和重置各弧段信息素初值,动态更新各弧段信息素量,以获得全局最优解.将该算法应用于具体的仿真实例,结果表明该算法能有效地解决工艺规划与调度集成问题,为企业生产提供借鉴.

An improved ant colony optimization algorithm is proposed to integrate process planning and scheduling （IPPS）. A graphbased optimization model for the IPPS is constructed by the nodes set, the directed arcs set and the undirected arcs set. The transfer probabilities of ants between nodes are designed by using heuristic information of parts＇ processing time. The corresponding schedule so lutions are achieved through the ants visiting different nodes of the graph. The volatile speed of pher omone on different arcs is adjusted according to the makespan of schedule solutions specified at dif ferent stages of the algorithm to improve search efficiency. The intensity of pheromone on all arcs is dynamically updated so as to avoid the local convergence and obtain global optimal solution by the restarting algorithm and resetting the pheromone on all arcs to the initial value. The algorithm is ap plied to specific simulation examples and the simulation results demonstrate the validity of the pro posed algorithm for the IPPS, which provides a reference for enterprise production.