基于新的动态邻域算法的车间调度问题的研究

《基于新的动态邻域算法的车间调度问题的研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、摘要作业加工调度问题是NP难的，被认为是最难的组合优化问题之一。在解决工业生产、经济管理和网络通讯等诸多问题时，都要涉及求解这个问题。优质、快速地求解作业加工调度问题，既有重要的理论意义，又能带来巨大的经济效益。转换瓶颈算法是解决作业加工调度问题的最有效的算法之一，本论文中用转换瓶颈算法来产生问题的初始值，进而提高搜索效率。动态邻域算法的基本思想是利用两个主要工具“shake（振动）”和“localsearch（局部搜索）”，局部搜索用于探索一个更为优的结果，振动使局部最小跳入它的下一个邻域，从而继续进行局部搜索。本论文是依据这个基本思想研究和分析并进行改进，提出

2、一个新的算法。为了提高振动的效率，我们根据卡里尔定理[11]和格拉博夫斯基定理[7]提出了六个推论，以避免无用的局部邻域结构的切换，并且提出了新的邻域结构，即：“向前插入”，“向后插入”，“直接交换”。同时把振动分为“正常振动”和“贪婪振动”。实验表明基于六个推论，振动更加有驱动力。基于新的邻域结构，可以找到更好的某个点的邻域最小值。关键词：作业加工调度NP难问题启发式动态邻域算法AbstractThejobshopschedulingproblemisnotonlyNPhardproblem,butalsoregardedasoneofthemostdiffic

3、ultcombinatorialoptimizationproblemsaswell.Itiswellknownthattheproblemsinthosefieldsofindustrialproduction,economicmanagement,networkcommunicationandcryptographyetc.makedirectappealtothisproblem.Therefore,solvingthejobshopschedulingproblemefficientlyandeffectivelywillmakeagreatofecono

4、micbenefits.Jobshopschedulingproblemiswellknowntobeadifficult，stronglyNP—completeproblem，theobjectiveofthisisminimizingthecompletiontimeofallthejobs，calledthemakespan，subjecttotheconstraintsofthiskindofproblem．TheShiftingBottleneckProcedure(SBP)proposedbyAdams,Balas&Zawackisaneffectiv

5、eheuristicmethodforsolvingthejobshopschedulingproblem.Inmyresearch,theSBPwillbeusingtogeneratetheinitialsolution.Ourpurposeistocutdowntheexecutingtime.VariableNeighborhoodSearchisarecentmeta-heuristicforsolvingcombinatorialandglobaloptimizationproblems.Itsbasicideaisthesystematicchang

6、eofneighborhoodwithinthelocalsearch.InanordinaryVNSalgorithmtwomainfunctions‘shake’and‘localsearch’playanimportantrole.Localsearchexploresforanimprovedsolutionwithinthelocalneighborhood,whileshakediversifiesthesolutionbyswitchingtoanotherlocalneighborhood.Intherelatedstudy,resultantef

7、fectivenessandcomputationalefficiencystillremainchallengingtask.Inthisthesis，inordertoimprovetheefficiencyofshakefunctionweproposed6propositionstoavoiduselessneighborhoodstructuresinExchange,Forward-Insert,Backward-Insert,moreoverdividetheshakefunctiontonormalshakeandintensifiedshake.

8、Inthe