基于改进遗传算法的调度问题研究

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

1、浙江大学硕士学位论文基于改进遗传算法的调度问题研究姓名：黄少锋申请学位级别：硕士专业：模式识别与智能系统指导教师：王宁20060501摘要遗传算法作为一种新型优化算法，由于具有简单、易操作、并行信息处理等特点，已经在许多领域的优化问题求解方面取得了成功的应用。但是遗传算法在理论上还不够完善，例如存在容易产生早熟现象以及局部寻优能力较差等问题，影响了其进一步的应用。本文针对常规遗传算法的不足，提出利用分布种群遗传算法求解Job-shop和Flow-shop问题，提出了一种基于启发式的遗传算法来求解单机加工时间可控问题，并进行数字计算研究。本文主要内容包括以下几个方面：

2、1．针对常规遗传算法的不足，给出了分布种群遗传算法的抽象形式，并分析了其收敛性，将该算法运用子Flow-shop和Job-shop问题计算，结果表明了该算法的有效性。2．针对单机加工时间可控调度问题，使用基于启发式遗传算法求解单机加工时间可控问题和单机加工时间离散问题。对具有多变量、非线性和不确定的此类问题的计算结果表明优化整定后的算法在性能上有了明显的提高·3．使用基于分布种群的遗传算法对Job-shop问题的加工时间可控问题进行了研究，完成了对加工可控Job-shop问题的智能算法求解研究，计算结果表明了所设计的算法具有优良的品质。关键词：遗传算法，分布种群，N

3、P-hard，单机加工时间可控，Job-shop，Flow-shopⅡAbstractAsanewoptimizationmethod，GAwaswidelyusedintheopfmaizationsofmanyfieldsowingtothefeatttresofsimpfic毋，easilyhandingandparallelprocessing．HoweverGAtheoryisnotperfect,suchasthereexisttheproblemsofeasilycreatingearlinessandbadabilityinlocaloptimal,

4、etc．Enlightenedbydism'butienofcreatureliving缸nature，themathematicmodeloftheDistr／bufionPopu／at／onbasedG∞eticAlgorithm(DPGA)isproposedinthispaper,anditsconvergenceanalysisa∞alsogiven．DPGAisappliedtooptimizetheJob-shopproblem(JSP)andHow-shopproblems(FSP),andthemodifiedGAbasedOllhem'istic

5、mlesispresentedforthesinglemachineschedulingproblemswithcontrollableprocessingtimes．ThethreeproblemsaretypicallyNl'-hard,whichlneallsthatitisimpossibletofindtheglobaloptimuminpolynomialcomplexity．Goodalgorithmsforthisproblemcanpromoteproductivityofenterprises．Thesimulationtests搬madeand

6、theresultsdemonstratetheefficiencyoftheabovemethedr-1nbemaincontentofthisthesisincludesthefollowing：。1．EnlightenedbydisU-ibutionofcreaturelivinginnaturalecologyenvironment，themathematicmodeloftheDistributionPopulationbasedGeneticAlgorithm,andtheconvergenceanalysisofDPGAaregiven．2．Theal

7、gorithmsbasedonDPGAisdesignedfortheJSPandFSP．ThesimulationtestsforsomebenchmarksshowtheefficiencyoftheDPGA．3．ThemodifiedGAispresentedtogettheoptimalresultsoftheNP-hardsinglemachineproblemwithcontrolhbleprocessingtimesandtheNP-hardsinglemachineproblemwilhdiser础controllableprocessingti