Abstract: This paper proposes an ant colony algorithm based new approach to analyze the job shop scheduling problem with limited capacity. The model is constructed with constraints on the cost and the machine load capacity. The ant colony algorithm runs through the BOM table to search for the knot positions, rank order workouts, and organizes all the workout orders into an integrated solution. An improved ant colony algorithm is introduced to solve the cost problem by modifying pheromone and global updating strategies. A self adaptive pheromone evaporation rate is proposed, which can accelerate the convergence rate and improve the ability of searching an optimum solution. Evidences show that ACA’s positive feedback mechanism and its search capability are very effective for plans with large number of product pieces. The improved ACA can produce load specific outsourcing plans for the limited capacity workshops, and provide the due date based outsourcing cost sensitivity analysis for decision making.

Key words: job shop scheduling problem, Bill Of Material, ant colony algorithm, decision making

摘要： 通过对有限产能车间调度问题的分析，提出了基于蚂蚁算法求解该问题的方法。在模型的构建中增加了成本和机器负荷约束。通过产品的BOM表采用蚂蚁算法搜寻节点，做各阶层工序安排，将各阶层工序安排组合成一完整解。对蚂蚁算法进行了改进，在基本蚂蚁算法的基础上，通过修改信息素局域更新规则和全局更新规则，引入自适应信息素挥发系数来提高算法的收敛速度和全局最优解搜索能力。算例分析表明，蚂蚁的正向反馈及探索功能对求解较大工件数的生产计划非常有效。而且在有限产能的环境中根据产能负荷状况产生不同的外包组合，将满足交货期的各种外包组合成本做敏感性分析，供决策者参考。

关键词: 作业车间调度, 物料清单（BOM）表, 蚂蚁算法, 决策