蚁群算法求解生调度问题研究.pdfVIP

蚁群算法求解生产调度问题研究 摘 要 生产调度作为工业生产过程的关键环节，其直接影响生产过程的效 率。本文在这样的背景下，以蚁群算法为工具，重点研究了生产调度问 题中的一类经典问题——Job Shop 问题。 首先，为了解决蚁群算法求解 Job Shop 问题计算量大的问题，本文 提出了蚁群算法求解 Job Shop 问题的机器分解方法。机器分解方法在每 次迭代中蚂蚁仅在子图中构造部分解，并与上次迭代中其他机器上的顺 序共同构成本次解，这样提高了蚁群算法求解 Job Shop 问题的效率。并 且在该算法中提出了一种新的状态转移规则和设计了蚂蚁起点位置选择 方法。通过在 Benchmark 算例上的仿真，与原有的一类集中式求解的蚁 群算法作了比较，仿真结果显示改进算法取得了较好的求解结果，大大 缩短了计算时间。 其次，在滚动优化思想的基础上，设计了基于时间分解的蚁群-滚动 算法求解确定性环境下的 Job Shop 问题。算法中按操作的到达时间，将 操作分为可加工与非可加工，对于可加工操作按选取规则选取相应操作 进入滚动窗口并用蚁群算法进行优化。仿真结果表明这一采用连续性滚 I 动策略或周期性滚动策略的局部优化算法求解结果优于分配规则，且其 大大的缩短了蚁群算法求解 Job Shop 问题的时间。 最后，对于不确定环境下的 Job Shop 问题本文建立了基于事件驱动 的仿真模型，通过自定义突发事件，研究不同的不确定环境下的 Job Shop 问题。在该模型基础上，本文用周期性与事件驱动结合调度策略的蚁群- 滚动算法对有机器损坏与修复，新工件到达，旧工件取消三种动态问题 进行了求解，仿真结果表明该算法可以满足不确定环境下的生产需要， 并且取得了不错的效果。 关键词：蚁群算法，异顺序车间调度，滚动窗口优化，机器分解 II RESEARCH ON PRODUCTION SCHEDULING PROBLEM BASED ON ANT COLONY ALGORITHM ABSTRACT Scheduling is one of the most pivotal part in manufacturing systems. It influence the efficiency of production directly. Under this background, this thesis has deeply studied on Job Shop Scheduling Problem JSSP , which is one of the most famous production scheduling problem, using ant colony algorithm. It consists of three parts as follow. The first part of this thesis proposes a machine-based decomposition method for JSSP based on ant colony algorithm to decrease the large computation of the ant colony algorithm when solving JSSP. The ant just gives the partial solution on one machine each time and the partial solution combining with the last solution on other machines construct the scheduling result this time. This method improves the efficiency of ant colony algorithm III to JSSP. A new state transition probability rule and the method of giving the ant start point are also presented. Compared with the original algorithm, the proposed algorithm is simulated for Benchmark instances and