基于蚁群算法的平行流水作业计划方法

Identical Parallel Flow Shop Scheduling Problem Based on Ant Colony Optimization

在分析实际生产作业方式的基础上,提出了平行流水作业这一新概念,其实质为平行机作业方式和流水作业方式的综合,属于非多项式计算时间问题。采用网络理论构造了平行流水作业的非连接图模型,提出了采用蚁群算法求解平行流水作业计划问题,以及求解过程中可行路径表的建立方法。算例研究表明10次随机计算的平均结果与最优结果差异率小于2%,计算重复精度高;对于75×20等较大规模问题,10次随机计算的平均时间少于280s,计算效率较高,能满足生产实时调度的需要。

Based on the analysis of practical production operation, a new concept of“identical parallel flow shop scheduling problem （IFSP）” is put forward. This concept is the integration of identical parallel machine scheduling with flow shop scheduling. The solution to IFSP is a non - polynomial computation of time problem. A disjunctive graph model is established for IFSP with network theory. The ant colony algorithm is used in solving IFSP and the feasible route table is introduced in the use of ant colony optimization. The computational experiments demonstrate that the difference between the mean value of ten stochastic computations and their best value is less than 2%, indicating a good computation repeatability of the algorithm. It only takes less than 280 seconds averagely to complete the computational experiment 75 × 20 in ten experiments, resulting in high computational efficiency. Thus, the algorithm can meet the requirement of on - line scheduling.