用蚁群算法求解Job-Shop问题的机器分解方法  

A Machine Decomposition Method for Job Shop Scheduling Problem Based on Ant Colony Algorithm

作　　者：薛拾贝[1] 席裕庚[1] 

机构地区：[1]上海交通大学自动化研究所,上海200240

出　　处：《计算机仿真》2008年第11期187-190,225,共5页Computer Simulation

基　　金：国家自然科学基金(60474002;60504026);国家863计划(2006AA04Z173)

摘　　要：针对生产调度中Job-Shop问题,蚁群算法在求解Job-Shop问题时有计算量大的缺点,为了提高求解效率,将机器分解方法引入蚁群算法。机器分解方法在每次迭代中蚂蚁仅在子图中构造部分解,并与上次迭代中其他机器上的顺序共同构成本次解,提高了蚁群算法求解Job-Shop问题的效率。并且在算法中提出了一种新的状态转移规则和设计了蚂蚁起点位置的方法。通过在Benchmark算例上的仿真,与原有的一类集中式求解的蚁群算法作了比较,结果显示改进后的算法取得了较好的结果,大大缩短了计算时间,说明机器分解方法的有效性。To decrease the large computation of the ant colony algorithm when solving Job Shop Scheduling Problem （JSSP）, this paper proposes a machine decomposition method for JSSP based on ant colony algorithm. The ant just gives the partial solution on one machine each time, and the partial solution combining with the last solution on other machines constructs the scheduling result this time. This method improves the efficiency of ant colony algorithm for solving Job Shop Scheduling Problem. A new state transition probability rule and a method of giving the ant Start point are also presented. Compared with the original algorithm, the proposed algorithm is simulated for Benchmark instances and it illustrates that the improved algorithm shows more better and more efficient results and saves many computation time.

关 键 词：蚁群算法 异顺序车间调度 机器分解 

分 类 号：TP278[自动化与计算机技术—检测技术与自动化装置]