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

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