基于遗传算法求解两类复杂JobShop调度问题

《基于遗传算法求解两类复杂JobShop调度问题》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、山东大学硕士学位论文基于遗传算法求解两类复杂JobShop调度问题姓名：乔威申请学位级别：硕士专业：控制理论与控制工程指导教师：王冰20070508山东大学硕士学位论文摘要随着全球经济一体化和知识经济的出现，企业之间的竞争将日益激烈。为了提高企业的核心竞争力，企业必须加强其内部的生产运作管理，而车间调度是生产管理的核心任务，因此，研究车间调度问题，不仅具有较大的学术价值，而且还有很大的实际意义。车间调度问题的突出特点是其复杂性。柔性JobShop调度问题(FlexibleJobShopSchedulingProblem，简称FJ

2、SSP)和不确定性JobShop调度问题(UncertainJobShopSchedulingProblem，简称UJSSP)相对于一般JobShop调度问题更具有复杂性：FJSSP的加工工件面临着机器选择的问题，加工路径有可选择性；UJSSP具有不确定加工时间和交货期窗口。由于这两类车间调度问题存在高度的计算难处理性，因而可供选择的算法比较少。遗传算法(GeneticAlgorithm，GA)作为一种全局随机搜索算法具有通用性、隐含并行性和全局解空间搜索等特点，已经在机器学习、模式识别、图像处理、组合优化及调度领域等领域得到了

3、成功应用。本文用遗传算法来求解上述两类复杂的JobShop调度问题，主要作了如下两方面的工作：(1)对于一类FJSSP基于自适应策略的遗传算法来求解，通过仿真实验验证了算法的有效性。本文针对模型的特殊性(机器可选择)，在染色体的解码操作中，同时考虑加工时间、工件最早允许JJnT时间和机器当前空闲时间三种因素，来选择相应机器。将基于自适应策略的遗传算法运用到模型的求解中，通过仿真实验验证了所提出的调度算法在解决FJSSP上能获得较好的结果。(2)对于存在不确定加工时间和交货期窗口的一类JobShop进行了研究。对企业而言，研究uj

4、ssP更具有实际意义，也更有利于将理论研究的成果应用于实际企业的调度问题中。本文对不确定加工时间用区间数来表示，以工件提前或者拖期遭受惩罚的可能性的总加权和最小作为优化目标。设计了带精英交叉策略的遗传算法搜索最优排序，通过仿真实验研究了该算法解决此类问题的有效性。关键词：JobShop调度；遗传算法；柔性；不确定性山东大学硕士学位论文AbstractWiththecomingfonlloftheglobaleconomyintegrationandknowledgeeconomy，thecompetitionamongenter

5、priseswillbemolefierce．Inordertoincreasetheircolecapacityofcompetition,enterprisesmustimprovetheirinnermanagementofproductionandopermionWhilethejobshopschedulingisthecoreofproductionmanagement．Therefore,theresearchonthejobshopschedulinghasnotonlytremendousacademicval

6、ue，butalsohasgreatpracticalmeaning．Thedramaticcharacteristicofthejobshopschedulingproblemisitscomplexity．FlexibleJobShopSchedulingProblem(FJSSP)andUncertainJobShopSchedulingProblem(UJSSP)aremorecomplicatedthangeneraljobshopschedulingproblems：theroutesandmachinesareop

7、tionalforthejobsintheFJSSP；UJSSPhaveuncertainprocessingtimesandduedatewindows．Becausethereismuchdifficultyinprocessinginthesetwotypesofjobshopscheduling，fewoptionalalgorithmsareavailable．Thegeneticalgorithm(OA)，asaglobalrandomsearchingmethodwhichischaracterizedbygene

8、rality,implicitparallelismandglobalsearching，hasbeensuccessfullyappliedinthefieldofmachine—learning，patternrecognition,imageprocess