基于遗传算法求解作业车间调度问题

辽宁科技大学本科生毕业设计第I页基于遗传算法求解作业车间调度问题摘要作业车间调度问题(JSP)简单来说就是设备资源优化配置问题。作业车间调度问题是计算机集成制造系统(CIMS)工程中的一个重要组成部分，它对企业的生产管理和控制系统有着重要的影响。在当今的竞争环境下，如何利用计算机技术实现生产调度计划优化，快速调整资源配置，统筹安排生产进度，提高设备利用率已成为许多加工企业面临的重大课题。近年来遗传算法得到了很大的发展，应用遗传算法来解决车间调度问题早有研究。本文在已有算法基础上详细讨论了染色体编码方法并对其进行了改进。在研究了作业车间调度问题数学模型和优化算法的基础上，将一种改进的自适应遗传算法应用在作业车间调度中。该算法是将sigmoid函数的变形函数应用到自适应遗传算法中，并将作业车间调度问题中的完工时间大小作为算法的评价指标，实现了交叉率和变异率随着完工时间的非线性自适应调整，较好地克服了标准遗传算法在解决作业车间调度问题时的“早熟”和稳定性差的缺点，以及传统的线性自适应遗传算法收敛速度慢的缺点。以改进的自适应遗传算法和混合遗传算法为调度算法，设计并实现了作业车间调度系统，详细介绍了各个模块的功能与操作。最后根据改进的编码进行遗传算法的设计，本文提出了一种求解车间作业调度问题的改进的遗传算法，并给出仿真算例表明了该算法的有效性。关键词：作业车间调度；遗传算法；改进染色体编码；生产周期辽宁科技大学本科生毕业设计第II页SolvingjopshopschedulingproblembasedongeneticalgorithmAbstractSimplyspeaking,thejobshopschedulingproblem(JSP)istheequipmentresourcesoptimizationquestion.JobShopSchedulingProblemasanimportantpartofComputerIntegratedManufacturingSystem(CIMS)engineeringisindispensable,andhasvitaleffectonproductionmanagementandcontrolsystem.Inthecompetionecvironmentnowadays,howtousetheassignmentsquicklyandtoplanproductionwithdueconsiderationforallconcernedhasbecomeagreatsubjectformanymanufactory.Inrecentyears,thegeneticalgorithmsobtainedgreatdevelopmentitwasusedtosolvethejobshopschedulingproblemearly.Thispaperdiscussesthechromosomecodemethodindetailbasedonthegeneticalgorithmsandmaketheimprovementonit.ThroughtheresearchonmathematicsmodelofJSPandoptimizedalgorithm,theimprovedadaptivegeneticalgorithm(IAGA)obtainedbyapplyingtheimprovedsigmoidfunctiontoadaptivegeneticalgorithmisproposed.AndinIAGAforJSP,thefitnessofalgorithmisrepresentedbycompletiontimeofjobs.Therefore,thisalgorithmmakingthecrossoverandmutationprobabilityadjustedadaptivelyandnonlinearlywiththecompletiontime,canavoidsuchdisadvantagesasprematureconvergence,lowconvergencespeedandlowstability.Experimentalresultsdemonstratethattheproposedgeneticalgorithmdoesnotgetstuckatalocaloptimumeasily,anditisfastinconvergence,simpletobeimplemented.thejobshopschedulingsystembasedonIAGAandGASHisdesignedandrealized,andthefunctionsandoperationsofthesystemmodulesareintroduceddetailedly.Intheend,accordingtothecodewithimprovedcarriesonthegeneticalgorithmsdesing,thispaperofferoneimprovedgeneticalgorithmsaboutsolovingtothejobshopschedulingproblem,andthesimulatedexamplehasindicatedthatthisalgorithmisvalid.Keywords:jopshopscheduling;geneticalgorithm;improvementchromosomecode;productioncycl辽宁科技大学本科生毕业设计第III页目录摘要............................................................................................................................................................IAbstract......................................................................................................................................................II1绪论.......................................................................................................................................................11.1课题来源.....................................................................................................................................11.2作业车间调度问题表述..........................................................................................................11.3车间作业调度问题研究的假设条件及数学模型............................................................21.3.1车间作业调度问题研究的假设条件.......................................................................21.3.2车间作业调度问题的数学模型................................................................................31.4课题研究内容及结构安排.....................................................................................................42遗传算法相关理论与实现技术............................................................................................62.1自然进化与遗传算法..............................................................................................................62.2基本遗传算法............................................................................................................................72.2.1遗传算法的基本思路...................................................................................................72.2.2遗传算法的模式定理...................................................................................................72.2.3遗传算法的收敛性分析..............................................................................................92.2.4基本遗传算法参数说明............................................................................................102.3遗传算法的优缺点.................................................................................................................112.3.1遗传算法的优点..........................................................................................................112.3.2遗传算法的缺点..........................................................................................................112.4遗传算法的进展.....................................................................................................................122.5小结............................................................................................................................................153用遗传算法对具体问题的解决与探讨................................