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

作业车间调度是优化生产效率和资源利用的重要工作。

在实际工厂生产中，作业车间的调度问题往往十分复杂，需要考虑多个因素和约束条件。

为了解决这一问题，许多研究者提出了多种优化算法，其中遗传算法是一种常用且有效的方法之一。

一、遗传算法概述遗传算法是一种模拟自然选择和遗传机制的优化算法，其核心思想是通过模拟自然界的进化过程，利用交叉、变异、选择等操作不断迭代，最终找到最优解。

遗传算法广泛应用于组合优化、函数优化、机器学习等领域，其灵活性和高效性受到了广泛认可。

二、遗传算法在作业车间调度中的应用1.问题建模作业车间调度问题可以理解为将一组作业分配到多台设备上，并确定它们的顺序和时间安排，以最大化生产效率和资源利用率。

这一问题的复杂性体现在多个方面，例如设备之间的关系、作业的执行时间、优先级约束等。

2.遗传算法解决方案遗传算法作为一种全局搜索算法，能够有效地处理作业车间调度问题中的复杂约束条件和多目标优化。

通过编码、交叉、变异和选择等操作，遗传算法可以逐步优化作业的调度方案，找到最优解或较优解。

三、基于Python的作业车间调度遗传算法实现基于Python语言的遗传算法库有许多，例如DEAP、Pyevolve、GAlib等。

这些库提供了丰富的遗传算法工具和接口，使得作业车间调度问题的求解变得简单且高效。

1.问题建模针对具体的作业车间调度问题，首先需要将问题进行合理的数学建模，包括作业集合、设备集合、作业执行时间、约束条件等。

然后根据问题的具体性质选择适当的遗传算法编码方式和适应度函数。

2.遗传算法实现利用Python的遗传算法库进行实现，首先需要定义遗传算法的相关参数，如种裙大小、迭代次数、交叉概率、变异概率等。

然后通过编码、交叉、变异和选择等操作，逐步优化作业的调度方案，直至达到收敛或达到一定迭代次数。

3.结果评估与分析得到最终的调度方案后，需要对结果进行评估和分析。

可以比较遗传算法得到的调度方案与其他常规方法的效果，如贪婪算法、模拟退火算法等。

基于遗传算法的作业车间调度优化研究作业车间调度是指针对多个作业和多个机器，通过合理的调度算法，使得作业能够在最短的时间内得到完成的过程。

在实际生产中，作业车间调度对于提高效率、降低成本具有重要意义。

而基于遗传算法的作业车间调度优化研究则是通过遗传算法这一优化方法，对作业车间调度问题进行求解和优化，以实现最佳调度方案的制定。

遗传算法是一种模拟生物进化过程的优化算法，其核心思想是通过模拟自然选择、遗传和突变的过程，从群体中选择出适应度最高的个体，并通过交叉和变异操作产生新的后代个体，逐渐寻找到全局最优解。

在作业车间调度问题中，遗传算法可以应用于寻找最佳作业顺序、最佳机器分配等方面，以提高生产效率和减少生产时间。

在基于遗传算法的作业车间调度优化研究中，首先需要建立数学模型或规则，定义适应度函数。

适应度函数用于评估染色体的优劣程度，通常是根据完成时间、机器利用率、生产延误等因素进行综合评价。

然后，根据问题的具体要求，设计合适的遗传算子，如选择、交叉和变异算子，用于模拟自然选择、遗传和突变的过程，以产生新的个体。

在遗传算法的每一代中，根据适应度函数对个体进行选择、交叉和变异，以逐步优化种群中的染色体。

在基于遗传算法的作业车间调度优化研究中，还需要考虑到实际生产中的约束条件，如作业之间的先后关系、机器之间的可用时间等。

在设计适应度函数和遗传算子时，需要充分考虑这些约束条件，以确保生成的解能够满足实际要求。

此外，为了提高算法的收敛速度和效果，还可以引入其他启发式算法，如局部搜索算法等，以进一步优化调度方案。

基于遗传算法的作业车间调度优化研究可以在很大程度上提高生产效率和降低成本。

通过优化调度方案，可以实现作业的合理分配和机器的充分利用，从而减少生产时间和资源浪费。

此外，遗传算法的适应度函数和遗传操作可以灵活调整，适应不同的调度需求和约束条件，使得算法更加通用和可扩展。

然而，基于遗传算法的作业车间调度优化研究也存在一些挑战和限制。

鲁东大学学报(自然科学版)　Ludong University Journal(Na tural Science Edition)2007,23(2):133—135　 收稿日期622;修回日期22 作者简介苏子林(—),男,副教授,硕士,主要从事计算机集成制造与管理信息系统的研究,()z y @63求解作业车间调度问题的多种群改进遗传算法苏　子　林(鲁东大学交通学院,山东烟台264025)摘要:在求解作业车间调度问题上,针对遗传算法的早熟收敛、对初始种群敏感等不足,提出了多种群改进遗传算法.该算法在进化过程中通过引入具有优良性能的修正种群替换进化种群的较差个体,实现了多种群杂交,以保持种群的多样性,提高了搜索效率.应用实例分析和算法对比证明了改进算法的效果和优越性.关键词:作业车间调度问题;遗传算法;修正种群;早熟收敛中图分类号:TP273 文献标识码:A 文章编号:167328020(2007)022******* 由于作业车间调度问题(JSP )固有的计算复杂性,很难找到一个有效的求解算法,因此该问题一直是生产管理领域研究的热点之一.遗传算法利用生物进化机制,在一个较大的初始解空间中通过优胜劣汰的方法进行优化求解,具有全局优化、隐含并行、自组织、自适应和自学习性等特点[1],因此,很快成为解决此类组合优化问题的主流算法.但由于遗传算法的固有特征,在求解JSP 时也存在以下不足[2]:(1)由于相对优秀的个体被选作父代个体参与交叉的概率较高,因此很容易出现“近亲结合”现象,导致在进化过程中失去种群多样性,出现早熟收敛问题;(2)搜索效率不高;(3)对初始种群很敏感,即解的质量受初始种群的影响较大.为了克服这些不足,本文进行了改进研究,提出了求解作业车间调度问题的多种群改进遗传算法(m ulti 2population i mp r oved genetic a lgorithm ,MP I G A ).1　作业车间调度问题描述 经典的作业车间调度问题可描述如下:加工系统中有n 个工件和m 台机床,每个工件均需要不重复地经历所有机床加工.工件的工艺路线和加工时间事先已知,同时假设:(1)一个工件同一时刻只能在一台机床上加工;(2)一台机床同一时刻只能加工一个工件;(3)工序一旦开始加工不能中断;(4)任何工件没有抢先加工的特权.调度问题的求解目标是如何安排生产,使生产周期最短.2　多种群改进遗传算法 为了提高算法的搜索效率,降低初始种群敏感性,防止早熟收敛,借鉴生物学中杂交试验的思想,提出了修正种群概念,并设计了修正种群生成的条件和过程.211　修正种群的概念 人们为了使农作物具有多种优良特性,采用具有不同优良特性的农作物进行杂交,在后代中选择优良个体,并与具有优良特性的个体再次杂交,如此不断进化,直到得到具有稳定的多种优良特性的新品种[3].本文对模拟自然界遗传进化现象的遗传算法进行改进,即在算法的总流程中,根据一定条件,引入部分优良个体替换较差的个体,对于进化中的种群进行修正.这些优良个体总称为修正种群.较差的个体是指具有较低适应度并且不利于种群多样性的个体.修正种群进入正在进化的种群后,与其他个体具有相同的交叉、变异和选择机会,共同进化. 当通过个体的交叉和变异,种群很难产生优于亲本的子代个体时,就发生早熟收敛.此时的交叉简单重复当前的亲本,进一步优化完全依赖于变异,非常缓慢.此时引入修正种群替换部分较差:2000929:20070219:1970E -mail su ilin t .134　鲁东大学学报(自然科学版)第23卷　的个体,可以提高种群的多样性,加快种群的进化速度,从而提高搜索效率.由于算法不断引入修正种群,不同适应度的大量个体不断进入算法,能大大提高算法的随机搜索能力,因此,算法对初始种群的敏感性大大降低.212　修正种群的生成 1)修正条件的定义　由于MP I G A算法在接近或进入早熟收敛状态时引入修正种群,因此必须把“接近或进入早熟收敛状态”作为修正种群引入的修正条件.早熟收敛有两种表现:一种是种群的最大适值长久不增加;另一种是种群中个体的相似性很大,多样性大大降低.算法实践证明,个体的相似性判断大大增加了算法的计算量,因此修正条件在MP I G A中定义为:超出遗传代数T后,种群的最大适值仍没有增加.定义中的遗传代数T经过多次实验,确定为25—35. 2)较差个体的判断　修正种群引入后要替换具有较低适应度并且不利于种群多样性的个体,因此,较差个体的判断应依据个体的适值和相似性.个体的相似性采用个体间的广义海明距离(ha mm ing distance)定义.扩展二进制格雷码中海明距离[4]的概念,定义个体间的广义海明距离为H(Xi (t),Xj(t))=6Lk=1|Xik(t)-Xjk(t)|.(1)(1)式中Xi(t)表示第t代进化种群的第i个个体,Xik (t)表示Xi(t)中的第k个基因,L为编码长度,运算符“-”连接个体的两个等位基因.若两个操作数表示的工件编号和工序编号完全相同,则运算结果为0,否则为1.修正种群替换较差个体的过程是:首先对种群的所有个体按照适应值降序排序;然后对适应值相同的多个个体,根据与其他个体的广义海明距离的平均值降序排列,如果与某个体的平均广义海明距离为零,则移到最后;最后生成规模为p′的修正种群,并替换当前种群的后p′个个体.p′一般定义为p/4—p/3(p为种群规模). 3)修正种群的生成过程　修正种群中的个体应具有某些优良特性,相对于初始种群,修正种群应具有较高的适应度,且个体的多样性较高.修正种群个体的生成分为两步:(1)采用文献[5]的基于优先度规则的启发式算法生成个体;()随机选择个体中同机床加工的两个工序,并交换其加工顺序,如果个体的适应度降低,则拒绝交换,否则接受交换,直到接受交换次数达到L/2.另外,为了保证修正种群中个体的多样性,新生成的个体Xi加入后,计算其与其他个体的广义海明距离,如果与某个体X j的广义海明距离小于编码长度的1/3,则删除X i和X j中适应度低的个体;如果删除了Xi,则停止计算,否则继续计算Xi与其他个体的广义海明距离,直到处理完修正种群的所有其他个体.213　算法的编码和总体流程 目前已经提出了多种JSP编码方法,本文采用基于工件的编码.例如编码“123133212”中,第一个“1”表示工件1的第一道工序,第二个“1”表示工件1的第二道工序,依此类推.这种编码空间对应整个解空间,并且每个染色体都对应可行的调度. 为了提高初始种群个体的适应值,有些算法[6]中初始种群个体依据启发式算法生成,只是提高了初始种群的整体适应性,对于算法的进化速度没有影响.MPIG A也不同于具有多个并列种群的并行遗传算法[7],其总体流程如图1.图1　多种群改进遗传算法的总体流程图t为遗传代数;t′为种群最大适值无增加的遗传代数3　实例分析 MP I G A选择遗传代数为终止条件,采用两点交叉的交叉算子和表示同机床加工工序的基因互换的变异算子,利用Java编程来实现算法.算法的选择操作是:对于父代个体和交叉变异得到的个体,首先选择适值最高的个体进入下一代,然后根据轮盘赌选择方法选择p-1个不同个体进入下一代.这样父代个体和交叉变异得到的个体具有同等的选择机会,既能将最优个体保留到下一代,又便于保持子代的多样性实验证明,与传统的轮盘赌选择方法相比,这种选择方法在收敛速2.　第2期苏子林:求解作业车间调度问题的多种群改进遗传算法135　度和质量上都有提高.文[8]提出的实例ft10已经成为公认的检验调度算法优劣的基准实例[8].选择标准遗传算法(G A)和与启发式规则相结合的遗传算法(HG A)作为比较,其种群规模p,交叉概率p c和变异概率p m都相同(p=400,p c=0.8,p m=0.15).对实例ft10运行20次的平均结果如图2.由图2可见,G A的起点在2000左右,时间在210,收敛于次优解1120;HG A起点较低,在1280,时间在260,收敛于次优解985;本文的MP I2G A由于起点在2000左右,在初始阶段不如HG A,在时间60时超过H G A,此后在时间262时,收敛于最优解930,具有较高的搜索效率.图2　MP IG A与G A,HG A的收敛情况 为了验证MP I G A对于不同规模实例的适应性,将多个不同规模的经典实例与HG A进行了对比实验,20次运行的平均结果见表1.表1显示,MP I G A的最优解都优于HG A,运行时间较短,标准差较小,充分说明了MP I G A具有较高的搜索效率和进化速度,更加稳定.表1　M P IG A与HG A对解决不同规模问题的比较问题n,mMPIG Ac′t s′HG Ac′t s′ft1010,10930262 1.0985260 4.5ft2020,51165281 1.11374432 4.7la2115,101055275 1.5109735619.9 la2620,1012181000 2.11245130015.7 la3130,1017841267 2.7188415600la3615,1512991220 6.61382146012.4 注:n为工件数;m为机床数;c′为算法得到的最优解;t为算法的平均收敛时间;s′为最优解的标准差4　结语 为了避免遗传算法出现早熟收敛问题,降低算法对初始种群的敏感程度,提高搜索效率,本文提出了多种群改进遗传算法.该算法在进化过程中,通过引入新的种群个体不断淘汰相似和适应值较低的个体,保持了种群的多样性.实例分析表明,改进算法大大提高了搜索效率,有效避免了早熟收敛现象,降低了对初始种群的敏感性,更加稳定.参考文献:[1]　XU AN Guang2nan,CHE NG Run2wei.Gene tic Alg o2rit hm s and Engi neering Desig n[M].Ne w Y ork:Johnwiley&S ons,1996:100—140.[2]　王正志,薄涛.进化计算[M].长沙:国防科技大学出版社,2000:188—210.[3]　严明建,黄文章,吕直文,等.高产杂交水稻新组合万优6号的选育[J].作物杂志,2005:66—67. [4]　吴养会,王乃信,王正中.一种新的改进遗传算法及其性能分析[J].西北农林科技大学学报(自然科学版),2004(32):124—126.[5]　张德富,李新.求解作业车间调度问题的快速启发式算法[J].计算机集成制造系统,2005.2(11):237—241.[6]　张克宇,周浚哲,郝永平,等.基于遗传算法车间流控制中调度问题的研究[J].小型微型计算机系统,2004,4(25):743—746.[7]　CHE N YW.A pa rallel genetic alg orit hm based on theisland model for i m age rest ora ti on[C]∥P r oceedi ngsof I EEE.Shir�o U sui.IEEE Neura l Net works Council,1996:109—118.[8]　WANG L i,ZH ANG Da2zh ong.An effective hybrid op2ti m izati on strategy for j ob2shop scheduli ng proble m s[J].Comput e rs&Opera tions Resea rch,2001,6(28):585—596.(下转第141页)　第2期李仁璞,等:基于粗糙集理论的软计算融合系统研究综述141　IEEE Transacti ons on Syste m s,Man and Cybe rne t 2i c s,1994,24:1114—1124.[33]　Ahn B S,Cho S S,Ki m C Y .The integrated me t h 2odol ogy of rough set t heory and artifi c ial neura l ne t 2work for busine ss fa ilure predic ti on [J ].Ex pe rt Sys 2t em s with Applica ti on,2000,18:65—74.[34]　Pa l S K,M itra P.Case generati on using rough s e tswith fuzzy representati on [J ].IEEE Trans ac tions on Kno wledge and Da ta Enginee ring,2004,16:292—300.[35]　D r wal G,Sik ora M.Induc ti on of fuzzy decisi on rulesba sed upon rough sets theory [C ]∥IEEE Confe r 2ence on Fuzzy Syst em s .B udapest :I EEE P ress,2004.1391—1395.[36]　InuiquchiM.Structure 2based approache s t o attributereduction in variable p recision rough se t mode ls[C ]∥L i n T Y,Yager R R,Zhang B.2005IEEE Interna 2ti ona l Confe rence on Granul a r Computing,Be ijing :IEEE P ress,2005:34—39.Rev i ew of Hybr i d Sof t C o m put i n g Syste m s Ba sed on Rough Set Theor yL I Ren 2pu,ZHANG Fu 2zeng,ZH AO Y ong 2sheng,S ONG L i 2hua(Schoo l of Compu t er Sci ence and Technol ogy,Ludong Un i versity,Yantai 264025,Ch ina )Abstrac t:A survey of hybrid soft computing syste m s based on r ough se t theory is pr ovided in the field of da ta m ining .The se hybrid syste m s a r e summ arized according t o thr ee different functi ons of r ough se ts:prep r oce ss 2ing data,measuring uncerta inty and m ining kno w ledge .General observa tions about r ough sets based on hybrid syste m s are presented .S om e challenges of existing hybrid system s and direc tions for future research are als o indicated .Key wor ds:data m ining;soft computing;r ough se t theory;neur a l net wor k;genetic algorithm(责任编辑　司丽琴)(上接第135页)Ab stra ct I D :167328020(2007)02201332EAAn i m pr oved M u lti 2popul a ti on Gen eti c Algor i thmfor J ob 2shop Scheduli n g P r oble mS U Zi 2lin(School of Traffic,L udong University,Yantai 264025,Ch i na )Abstrac t:I n or de r to avoid pre m ature convergence pr oblem ,lo wer a lgorithm ’s sensitivity to origina l popula 2ti on,and i m p r ove convergent speed,an i mp r oved m ulti 2populati on genetic algorithm is put f or ward.Correc ti on popula tion which has e m inent perf or m ance is continually i m ported during inheritance and evoluti on,and cur 2rent populati on ’s baddish individuals are re p laced;thus m ulti 2populati on crossover is realized t o keep popula 2ti on ’s dive rsification .The i mpr ove m ent m ethod ’s effect and the algorithm ’s superiority are m ade sure by ana l 2y f x K y j 2;;;(责任编辑　司丽琴)sis o e a mple and comparis on with gene tic algorith m s .e wor ds:ob shop scheduling pr oble m genetic algorithm correcti on popula tion p r emature convergence。

基于遗传算法的Job-Shop调度问题研究陶泽;张海涛【摘要】研究单目标作业车间调度问题(JSP),提出了一种基于遗传算法以缩短生产周期为目标的Job-Shop调度问题.通过建立数学模型,设置编码、解码方案,以及确定选择、交叉、变异等遗传算子,充分利用遗传算法的特点解决加工车间静态、动态问题,并通过Gantt图给出调度方案.结合应用实例进行分析,分析结果表明该方法是有效的、可行的.【期刊名称】《沈阳理工大学学报》【年(卷),期】2016(035)002【总页数】5页(P60-64)【关键词】作业车间调度;遗传算法;Gantt图【作者】陶泽;张海涛【作者单位】沈阳理工大学机械工程学院,沈阳110159;沈阳理工大学机械工程学院,沈阳110159【正文语种】中文【中图分类】TP311作业车间调度(Job-Shop Scheduling)是车间调度中最常见的调度类型，是最难的组合优化问题之一[1]，对其研究具有重大的现实意义。

科学有效的生产调度不但可以提高生产加工过程中操作工人、设备资源的高效利用，而且还可以缩短生产周期，降低生产成本。

随着遗传算法在组合优化问题的广泛应用，许多人开始对遗传算法进行深度研究，并应用它求解车间调度问题。

目前，对作业车间调度问题的研究大都集中在静态调度上，对动态调度的研究很少。

因为动态调度要比静态调度复杂得多，另外因为在研究动态调度问题时，由于在实际的生产加工过程中不确定以及随机因数太多，任何单一的规则都较难适用于所有的动态环境。

在最近几年，对动态调度问题的研究方法主要有人工智能方法、仿真方法等[2]。

这些方法不但开发成本高，而且开发周期也很长，不适应于企业的应用。

相比之下，遗传算法作为一种新型仿生算法为求解生产调度问题提供了新的解决思路。

因此，本文提出了一种应用遗传算法求解作业车间动态调度的方法，为了评价这种方法的有效性，以最优完工时间为目标[3]模拟加工车间，通过模拟结果可以观察出应用遗传算法求解此类问题是有效的。

基于遗传算法求解作业车间调度问题摘要作业车间调度问题(JSP)简单来说就是设备资源优化配置问题。

作业车间调度问题是计算机集成制造系统(CIMS)工程中的一个重要组成部分，它对企业的生产管理和控制系统有着重要的影响。

在当今的竞争环境下，如何利用计算机技术实现生产调度计划优化，快速调整资源配置，统筹安排生产进度，提高设备利用率已成为许多加工企业面临的重大课题。

近年来遗传算法得到了很大的发展，应用遗传算法来解决车间调度问题早有研究。

本文在已有算法基础上详细讨论了染色体编码方法并对其进行了改进。

在研究了作业车间调度问题数学模型和优化算法的基础上，将一种改进的自适应遗传算法应用在作业车间调度中。

该算法是将sigmoid函数的变形函数应用到自适应遗传算法中，并将作业车间调度问题中的完工时间大小作为算法的评价指标，实现了交叉率和变异率随着完工时间的非线性自适应调整，较好地克服了标准遗传算法在解决作业车间调度问题时的“早熟”和稳定性差的缺点，以及传统的线性自适应遗传算法收敛速度慢的缺点。

以改进的自适应遗传算法和混合遗传算法为调度算法，设计并实现了作业车间调度系统，详细介绍了各个模块的功能与操作。

最后根据改进的编码进行遗传算法的设计，本文提出了一种求解车间作业调度问题的改进的遗传算法，并给出仿真算例表明了该算法的有效性。

关键词：作业车间调度；遗传算法；改进染色体编码；生产周期Solving jopshop scheduling problem based ongenetic algorithmAbstractSimply speaking, the job shop scheduling problem(JSP) is the equipment resources optimization question. Job Shop Scheduling Problem as an important part of Computer IntegratedManufacturing System (CIMS) engineering is indispensable, and has vital effect onproduction management and control system. In the competion ecvironment nowadays, how touse the assignments quickly and to plan production with due consideration for all concernedhas become a great subject for many manufactory.In recent years,the genetic algorithms obtained great development it was used to solve the job shop scheduling problem early.This paper discusses the chromosome code method in detail based on the genetic algorithms and make the improvement on it. Through the research on mathematics model of JSP and optimized algorithm, theimproved adaptive genetic algorithm (IAGA) obtained by applying the improved sigmoidfunction to adaptive genetic algorithm is proposed. And in IAGA for JSP, the fitness ofalgorithm is represented by completion time of jobs. Therefore, this algorithm making thecrossover and mutation probability adjusted adaptively and nonlinearly with the completiontime, can avoid such disadvantages as premature convergence, low convergence speed andlow stability. Experimental results demonstrate that the proposed genetic algorithm does notget stuck at a local optimum easily, and it is fast in convergence, simple to be implemented. the job shop scheduling system based on IAGA and GASH is designed andrealized, and the functions and operations of the system modules are introduced detailedly. In the end ,according to the code with improved carries on the genetic algorithms desing, this paper offer one improved genetic algorithms about soloving to the job shop scheduling problem, and the simulated example has indicated that this algorithm is valid.Keywords: jop shop scheduling; genetic algorithm; improvement chromosome code; production cycl毕业设计（论文）原创性声明和使用授权说明原创性声明本人郑重承诺：所呈交的毕业设计（论文），是我个人在指导教师的指导下进行的研究工作及取得的成果。