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

《蚁群算法求解生产调度问题研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、蚁群算法求解生产调度问题研究摘要生产调度作为工业生产过程的关键环节，其直接影响生产过程的效率。本文在这样的背景下，以蚁群算法为工具，重点研究了生产调度问题中的一类经典问题——JobShop问题。首先，为了解决蚁群算法求解JobShop问题计算量大的问题，本文提出了蚁群算法求解JobShop问题的机器分解方法。机器分解方法在每次迭代中蚂蚁仅在子图中构造部分解，并与上次迭代中其他机器上的顺序共同构成本次解，这样提高了蚁群算法求解JobShop问题的效率。并且在该算法中提出了一种新的状态转移规则和设计了蚂蚁起点位置选择方法。通过在Benchmark算例上的仿真，与

2、原有的一类集中式求解的蚁群算法作了比较，仿真结果显示改进算法取得了较好的求解结果，大大缩短了计算时间。其次，在滚动优化思想的基础上，设计了基于时间分解的蚁群-滚动算法求解确定性环境下的JobShop问题。算法中按操作的到达时间，将操作分为可加工与非可加工，对于可加工操作按选取规则选取相应操作进入滚动窗口并用蚁群算法进行优化。仿真结果表明这一采用连续性滚I动策略或周期性滚动策略的局部优化算法求解结果优于分配规则，且其大大的缩短了蚁群算法求解JobShop问题的时间。最后，对于不确定环境下的JobShop问题本文建立了基于事件驱动的仿真模型，通过自定义突发事件，

3、研究不同的不确定环境下的JobShop问题。在该模型基础上，本文用周期性与事件驱动结合调度策略的蚁群-滚动算法对有机器损坏与修复，新工件到达，旧工件取消三种动态问题进行了求解，仿真结果表明该算法可以满足不确定环境下的生产需要，并且取得了不错的效果。关键词：蚁群算法，异顺序车间调度，滚动窗口优化，机器分解IIRESEARCHONPRODUCTIONSCHEDULINGPROBLEMBASEDONANTCOLONYALGORITHMABSTRACTSchedulingisoneofthemostpivotalpartinmanufacturingsystems.

4、Itinfluencetheefficiencyofproductiondirectly.Underthisbackground,thisthesishasdeeplystudiedonJobShopSchedulingProblem(JSSP),whichisoneofthemostfamousproductionschedulingproblem,usingantcolonyalgorithm.Itconsistsofthreepartsasfollow.Thefirstpartofthisthesisproposesamachine-baseddeco

5、mpositionmethodforJSSPbasedonantcolonyalgorithmtodecreasethelargecomputationoftheantcolonyalgorithmwhensolvingJSSP.Theantjustgivesthepartialsolutionononemachineeachtimeandthepartialsolutioncombiningwiththelastsolutiononothermachinesconstructtheschedulingresultthistime.Thismethodimp

6、rovestheefficiencyofantcolonyalgorithmIIItoJSSP.Anewstatetransitionprobabilityruleandthemethodofgivingtheantstartpointarealsopresented.Comparedwiththeoriginalalgorithm,theproposedalgorithmissimulatedforBenchmarkinstancesanditillustratesthattheimprovedalgorithmshowsmuchbetterandmore

7、efficientresults.Thesecondpartproposesatime-baseddecompositionmethod,ant-rollingalgorithm,whichbenefitfromrollingwindowoptimizationinpredictivecontroltheory,tosolvecertainparameterJSSP.Accordingtotheoperation’sarrivaltime,itdividestheoperationsthatwaitingforprocessingintotwosets.On

8、eisoperationswhicharewaiti