一种基于图的柔性作业车间调度方法  

Graph-based Approach for Flexible Job-shop Scheduling Problems

作　　者：王进峰[1] 范孝良[1] 万书亭[1] 

机构地区：[1]华北电力大学能源动力与机械工程学院,保定071003

出　　处：《系统仿真学报》2013年第10期2499-2502,2508,共5页Journal of System Simulation

基　　金：国家自然科学基金(51177046);中央高校基本科研业务费专项资金(13MS100);河北省自然科学基金(E2011502024)

摘　　要：提出了一种基于图的柔性作业车间调度问题(FJSP)的求解方法。通过工序节点集、有向弧集、无向弧集,构建了基于图的FJSP优化模型。应用蚁群算法求解柔性作业车间调度问题,以零件加工时间和弧段中堆积的信息素作为启发式信息,设计蚂蚁在各个节点间的转移概率。以最大完工时间最小化、机床最大负荷最小化、机床负荷均衡化为优化目标,通过加权处理设计了优化目标函数,将多目标优化问题转变为单目标优化问题。通过6X6的实例验证了该算法解决FJSP的可行性和有效性。A graph-based approach for the flexible job-shop scheduling problem （FJSP） was proposed. A graph-based optimization model for FJSP was constructed by the nodes set, the directed arcs set and the undirected arcs set. An ant colony optimization （ACO） was applied to solve the FJSP. The transfer probabilities of ants between nodes were designed by using heuristic information of parts＇ processing time and the amount of pheromone on the arc. Minimizing the makespan of the parts, the maximal load of the machines, the maximal load difference of the machines was set to be the optimization objective. The multi-objective optimization problem was transformed to single optimization problems by weighting the above three parameters. The algorithm was tested on instances of 6 jobs and 6 machines. The experimental results show that the proposed algorithm is a viable and effective approach for the FJSP.

关 键 词：FJSP 蚁群算法 信息素 多目标 

分 类 号：TP391.731[自动化与计算机技术—计算机应用技术] TP391.75[自动化与计算机技术—计算机科学与技术]