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

针对生产调度中Job-Shop问题,蚁群算法在求解Job-Shop问题时有计算量大的缺点,为了提高求解效率,将机器分解方法引入蚁群算法。机器分解方法在每次迭代中蚂蚁仅在子图中构造部分解,并与上次迭代中其他机器上的顺序共同构成本次解,提高了蚁群算法求解Job-Shop问题的效率。并且在算法中提出了一种新的状态转移规则和设计了蚂蚁起点位置的方法。通过在Benchmark算例上的仿真,与原有的一类集中式求解的蚁群算法作了比较,结果显示改进后的算法取得了较好的结果,大大缩短了计算时间,说明机器分解方法的有效性。