文档介绍：该【生产调度问题及其优化算法 】是由【青山代下】上传分享，文档一共【14】页，该文档可以免费在线阅读，需要了解更多关于【生产调度问题及其优化算法 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。:..生产调度问题及其优化算法<采用遗传算法与MATLAB编程)信息孙卓明二零零三年八月十四日生产调度问题及其优化算法背景及摘要这是一个典型的Job-Shop动态排序问题。目前调度问题的理论研究成果主要集中在以JobShop冋题为代表的基于最小化完工时间的调度冋题上。一个复杂的制造系统不仅可能涉及到成千上万道车间调度工序,而且工序的变更又可能导致相当大的调度规模。解空间容量巨大,N个工件、M台机器的问题包含凹种排列。因为问题的连环嵌套性,使得用图解方法也变得不切实际。传统的运筹学方法,即便在单目标优化的静态调度问题中也难以有效应用。本文给出三个模型。首先通过贪婪法手工求得本问题最优解,既而通过编解码程序随机模拟优化方案得出最优解。最后采用现代进化算法中有代表性发展优势的遗传算法。文章有针对性地选取遗传算法关键环节的适宜方法,采用MATLAB^件实现算法模拟,得出优化方案,并与计算机随机模拟结果加以比较显示出遗传算法之优化效果。对车间调度系列冋题的有效解决具有一定参考和借鉴价值。一?问题重述某重型机械厂产品都是单件性的,其中有一车间共有A,B,C,D四种不同设备,现接受件产品的加工任务,每件产品接受的程序在指定的设备上加工,其工序与加工周期如下表:<S-设备号、T-周期)工序产品STSTSTSTSTSTSTSTCABCrDADBC:A:CDABBCDADCDBCD:A:C:DABACDACA(表一>条件:、每件产品必须按规定的工序加工,不得颠倒;每台设备在同一时间只能担任一项任务。<每件产品的每个工序为一个任务):..问题:做出生产安排,希望在尽可能短的时间里,完成所接受的全部任务。要求:给出每台设备承担任务的时间表。注:在上面,机器AB,C,D即为机器,,,,程序中以数字,,,表示,说明时则用A,B,C,D二?模型假设?每一时刻,每台机器只能加工一个工件,且每个工件只能被一台机器所加工,同时加工过程为不间断;?所有机器均同时开工,且工件从机器I到机器J的转移过程时间损耗不计;?各工件必须按工艺路线以指定的次序在机器上加工多次;?操作允许等待,即前一操作未完成,则后面的操作需要等待,可用资源有限。三?符号说明及初始数据表达分析凶-第i个工件<i=…)-机器顺序阵二一表示i工件的第j个操作的机器号S-第j台机器<j=…)IrJ-工件排列阵上|[表示i机器上第j次加工的工件号匡-加工时间阵—I为i工件的第j个操作的时间周期-整个任务完成时间整理数据后得到:工=[CABCD]~[At=[][DBC]][CDABA][][BCDADC][][DBCDACD][][ABACDACA][]上述二阵直接从题目得岀,而丨则是我们要求的:(>关于工件的加工时间表表二产品/工件<i):总计-总净加工时间<周期)凶加工工序总数<个):(>关于机器的加工时间表表三机器/设备(j>:总计ABCD因总净加工时间M加工操作次数分析:因为各产品总净加工时间和各机器总净加工时间之中最大值为,而总计为,那么总时间C介于[,]。同时各工件加工繁杂程度不一,各机器的任务量也有轻重之别。合理的调度排序是对于节省时间和资源是必要的。希望最优化答案是,这样达到最小值,如果答案是,那么意味着机器D不间断工作,直至全部加工任务完成。:..四?贪婪法快速求解如果按照一定规则排序,当多个工件出现“抢占”同一机器的局面的时候我们可以制定如下的工序安排规则:.优先选择总剩余时间或总剩余操作较多的工件。<如果出现总剩余加工时间多者总剩余操作数反而较少的情况时,按照程度具体情况具体分析)。.机器方面来说,尽量避免等待空闲时间,优先考虑剩余净加工时间或者剩余加工总次数较多的机器,尤其是机器D,即倘若能够使机器□不间断工作且其他机器完工时间均不多余时,那么就可以得到最优解。首先按照最优化时间为的设想避免D出现等待,排序后得到升以下具体排列顺序。各机器承担任务表为(其中粗体字为对应工件产品号,括号内为对应时间周期段>:操作操作操作操作操作操作操作操作操作操作A丁(>(->(->(->(->(>(->(->(->(->B「(->J(->(->(->(->(->C::::(->(->(->(->(->(->(->(->(->(->D(->(->(->(->(->(->(->(->(>(表四>(图一>上图为加工周期图<甘特图),标注数字为相应操作的周期,完工时间为第周期五?计算机随机模拟<编程).编码:随机产生生产的工序操作优先顺序,进行编码,如:K=[:..]<注:同时作为下文的染色体之用)意思为:工件优先被考虑进行第一次操作,然后进行其第一步操作,然后操作,操作,再操作其第二步工序,依次进行。如果前后互相不冲突,则可同时在不同机器上操作。通过排列组合得出,总共有类似K的排列序列厂I多种!当然,这其中只对应解[,],意味着有大量排列序列对应同一加工方案,而大量加工方案又对应同一时间解。.解码:即对编码进行翻译,产生具体可操作工序安排方案,这里采用活动化解码算法。例如工件第i步操作<记为而<,i),且在机器A上进行)被安排在工件第j步操作<记为JM<,j))后面进行,那么如果安排好回<,j)后,只要回<,i)在工件已经排序好的操作之后进行,那么操作因<,i)可插入到机器A处最前可安置的时间段进行。在这里,一个编码序列对应一个加工方案,而一个加工方案可对应一个或多个编码序列,这就是二者之关系。.编程:通过一组随机编码产生一生产加工优先序列,<N个C的最小值,如,等,甚至出现)。.:(共运行次>,,,,,,,,,平均值.,:(共运行次>,,,,,,,,,平均值.,:(共运行次>,,,,,,,,,平均值.,:<如图二所示)(图二>:..<注:处为次<概率为/=/),处为次,处次)结论:如果想将中排序序列以平均出现一次的可能性进行模拟,即运行匕I次,计算机需运行将近万亿年!当然,我们没有这个必要,因为我们只需要运行数万次,就很可能得到最优解,<在随机模拟次后出现仃次,那么意味着概率大约/=/,另外处为次,处次)。六?遗传算法模型建立和步骤解法遗传算法<icAlgorithm)作为一种优化算法特别适合于对象模型难于建立、搜索空间非常庞大的复杂问题的优化求解。它和模糊控制技术一样,虽然在理论上还没有完善,但是在实践中已经得到了广泛的应用。遗传算法的基本思想是:模仿生物系统适者生成的原理,通过选择、复制、交叉、变异等简单操作的多次重复来达到去劣存优的目的,从而获得问题的优化结果。遗传算法的实现由两个部分组成,一是编码与解码,二是遗传操作。其中遗传操作又包括选择、复制、交叉、变异等步骤。本文根据实际情况采取了-整数编码。数字,,,,,分别代表件待加工产品。:本文遗传算法基本流程通过编码,解码程序随机产生N个<有一定数量,如或)个体构成初始种群a)从初始中群中选取个具有最优染色体<最有排序方案)的个体作为临时个体<父代);b)如果此个体中有一个个体通过解码操作能够实现最优排序<即使总时间为周期),那么结束此算法,得到最优解;(><,c)对个临时个体以一定方式循环交叉执行染色体交叉变换和变异选择小概率互换操作),产生个新的个体;d)对父代和子代共个个体进行选择,从中选出最佳的个个体,做为下一代的父代;e)重复执行第二步(b>操作;f)如果执行完M步后仍然未得出答案,那么将目前的最优解作为本算法的最优解答案。:...编码和解码<同上).交叉变换(crossover〉对个父代临时个体进行染色体交叉变换,采用循环交叉方法vCyclecrossoverCX,如父代染色体为:X:[]和Y:[],如果随机选到第二位开始交叉,那么X的对应Y的,X的对应Y的,X的对应Y的,这样就确定了以上为不变的染色体,其余位置的染色体互换位置,最后得到-J:[],:[],实现交叉变换。.变异选择vmutation)采用互换操作<SWAp,,即随机交换染色体中两不同基因的位置。如上面的染色体为:II:[]。随机产生变换位置号,如产生随机数和,那么交换数字后得到染色体:[],变异概率取.。.选择操作<selection:对父代个体f,f和子代个体f,f进行选择,通过编码操作确定具有最优解的个个体,成为新一代f和f。如此,通过多次编码和解码随机产生一定数量的个体,选取个最佳个体进行交叉变换操作,产生个新个体,然后对个个体进行选择,产生下一代,如果某时刻通过解码操作得出最优解<所有解的下限,这里是周期),那么算法结束,否则循环进行,直至预先给定的循环次数达到为止,以最后得到的最优解作为最终最优解。<采用MATLA工具编程)主程序如下:<子程序见略)task='e!Waitamomentplease!---Writer:%本程序为主程序,调用以下各分支程序f=zeros(,>。>。孙卓明,信息',f=zeros(,whilef==f。%(N>此步避免初始染色体f,f相同,导致以下死循环[minminmax,s]=chushijie。%种群初始化;基于操作的编码策略;活动化解码算法。f=s。minminmax,%chushijie(N>参数N为初始种群数(N>[minminmax,s]=chushijie%选取的第一个初始个体。f=s。minminmax,%再次种群初始化end。选取的第二个初始个体Mfore=:%e=:M[D]=jiaocha(f,f>。%进行M次遗传操作<交叉-变异-选择>f。f。“染色体”无需变动部分基因交叉变化<循环交叉操作,cyclecrossoverCX),选取[f,f]=jiaocha_bianyi(f,f,D>=%f。f。生成交叉后的“染色体”,并进行变异选择[f,f]=xuanze(f,f,f,f>。%f。f。选择:对父代f,f和子代f,f进行解码,得出个较优个体,成为下一代的父代[minmaxf,a,b]=tongbujinzhan(f>。%求该时刻个体f的最优时间(因为f优于f>ifminmaxf==。f,a,b,minminmax,minminmax,minminmax_last=minmaxf,task='Finish!essful!Bestanswer!Congratulation!',return。end。end。:..f,a,b,minminmax,minminmax,minminmax_last=minmaxf,ifminminmax_last>=。task='Finish!Actionagainplease!',end。ifminminmax_last>=&&minminmax_last<。task='Finish!',end。ifminminmax_last<。task='Finish!essful!',end。八?遗传算法模拟结果首先给出最优方案:在进行某次n=,m=的操作后得到模拟最优结果周期时间:minminmax=minminmax=*二个初始较优个体解)f=[]<f为各工件优先选择顺序排列,即“染色体”)a=:<a,b为四台机器空闲周期段)b=minmi最终最优解)=<nmax其中机器A空闲时间段为:-,-,-,-。机器B则为:-,-。机器C为:-,-,-。机器D无空闲。以下为:取不同N和M值情况下数据优化过程以及时间上的比较:(表五>NNM第次运仃第二次运行第三次运行第四次运行第五次运行平均运行时间:--------/P--:----------/----------/--------.(s>------------(s>----------/----------/----------.(s>----------(s>----------/----------(s>----------(s>说明:以最后一行第一次运行“--”为例,和分别为次N取时得到的*个随机解中的最优解,为经过M=代的遗传(交叉变异选择>后得到的最终最优解。明显地发现:M的增大所产生的优化效果明显好于N增大产生的优化效果M从----的变化使最优解有从*--*--*的变化规律,:..N的--的变化则不明显。因此相对于随机取解,经过遗传算法优化之后效果是显著的另外对采用遗传算法前后模拟所得数据进行比较:第一次第二次第三次第四次第五次均值平均时间「N=,M=(S>.N=,N=,M=.P.(S>:(表六>由上表看来,虽然在均值方面相差不显著,但是时间上采用遗传算法之后节约了约三分之二的运行时间,效率显而易见。九?模型优缺点及改进模型优点,采用遗传算法可对一个理论上无法求尽的NP问题以较有效方法在较短时间内得到较精确解。缺点,采用遗传算法还不全面,只是一个简单模型,未考虑收敛性,适配值等,对参数设置与最优解关系研究还不够深入。模型本身还具有漏动,仍需改进,较好设想为采用和模拟退火算法的混合遗传算法,因为时间紧迫,在此就不再深入给出模型及分析了。[]:参考文献?车间调度与遗传算法王凌清华大学出版社?,.<第二版)潭浩强清华大学出版社信息孙卓明年月日本文网上下载地址(个人主页>:子程序一:(种群初始化,得较优个s=。体>%编码程序:基于操作的编码策略function[minminmax,ss]=chushijie(n>k=。%种群初始化,以下为编码和解码过程,同时对n次fort=:。选取最优化个体I=randint(,,[,]>。Jm=[。。whileJm(I,>==。。。I=randint(,,[,]>。。]。end。minminmax=。s(k>=loford=:n。k=k+oX=o:..whilex<=。Jm(l,x>=Jm(l,x+>ox=x+oendoJm(I,>=oendoJm=[ooooo]oT=[ooooo:..ifflag(s(i>><=flag_(q>。解码程序:活动化解码算法fori=:。k(i>=。flag(s(i>>=flag_(q>+t。flag_(q>=flag_(q>+t。end。forq=:。elseifflag(s(i>>>flag_(q>。forx=:。forx=:。。。ifa(q,x>==&&v==。a(q,x>=b(q,x>=flag_(q>=end。a(q,x>=flag_(q>end。b(q,x>=flag(s(i>>。v=。end。forp=:。flag(p>=。flag(s(i>>=flag(s(i>>+t。end。flag_(q>=flag(s(i>>。fori=:。end。q=Jm(s(i>,k(s(i>>>。t=T(s(i>,k(s(i>>>end。z=。v=。k(s(i>>=k(s(i>>+。forx=:。。end。minmax=。ifmax(flag(s(i>>,a(q,x>>+t<=b(q,x>&&z==。ifforq=:。flag(s(i>><=a(q,x>&&a(q,x>+t==b(q,x>。ifminmax<flag_(q>。flag(s(i>>=b(q,x>。minmax=flag_(q>。y=x:。a(q,y>=a(q,y+>end。end。b(q,y>=b(q,y+>。forifendminminmax>minmaxz=。%得出初始最优解minminmax=minmax。elseifss=s。flag(s(i>><=a(q,x>&&a(q,x>+t<b(q,x>a(q,x>=a(q,x>+tend。。flag(s(i>>=a(q,x>。z=end。elseif子程序二:<父代交叉变换)flag(s(i>>>a(q,x>&&a(q,x>+t==b(q,x>function[D]=jiaocha(f,f>%化<循环交叉操flag(s(i>>=b(q,x>。b(q,x>=b(q,x>-t。z=。作,CX),选取“染色体动部分基因elseifs=randint(,,[,]>。fory=:x+。whilef(s>==f(s>。a(q,y>=a(q,y->。b(q,y>=b(q,y->s=randint(,,[,]>。flag(s(i>>>a(q,x>&&a(q,x>+t<b(q,x>。end。end。forp=:。b(q,x+>=b(q,x>。b(q,x>=flag(s(i>>a(q,x+>=flag(s(i>>+tD(p>=。flag(s(i>>=a(q,x+>。z=。end。end。z=。j=。D(j>=s。j=j+。end。fori=:。end。ifz==。iff(i>==f(s>&&z==。:..。j=j+。z=。end。end。iff(D(j->>==f(s>。end交叉变无需变:..d=randint(,,[,]>。。end。whiled==d。form=:。d=randint(,,[,]>。z=。end。m=f(d>。f(d>=f(d>。f(d>=m。fori=:。end。iff(i>==f(D(j->>&&z==。子程序四:<四者中选取最优二个体)w=。fort=:j。functionif(i-D(t->>>||(i-D(t->><。[f,f]=xuanze(f,f,f,f>%w=w+。end。对父代f,f和子代f,f进行解码,得出个较优个end。体,成为下一代的父代min=。min=。min=。min=。h=。ifw==j-。g=。D(j>=i。j=j+。z=。[min]=tongbujinzhan(f>。end。[min]=tongbujinzhan(f>。end。[min]=tongbujinzhan(f>。end。[min]=tongbujinzhan(f>。iff(D(j->>==f(s>&&z==。ifmin<=min&&min<=min&&min<=min。return。h=f。ifmin<=min&&min<=min。g=f。end。elseifmin<=min&&min<=min。g=f。end。elseifmin<=min&&min<=min。g=f。end。end。子程序三:<变异选择,形成子代)elseifmin<=min&&min<=min&&min<=min。functionh=f。ifmin<=min&&min<=min。g=f。[f,f]=jiaocha_bianyi(f,f,D>%生成交叉后的“染色elseifmin<=min&&min<=min。体”,并进行变异选择g=f。g=f。g=f。fori=:。elseifmin<=min&&min<=min。ifD(i>>。g=f。g(D(i>>=f(D(i>>。g(D(i>>=f(D(i>>。end。end。elseifmin<=min&&min<=min&&min<=min。end。f=g。f=g。h=f。ifmin<=min&&min<=min。g=f。c=randint(,,[,]>。elseififc==。g=f。d=randint(,,[,]>。elseifd=randint(,,[,]>。g=f。whiled==d。endd=randint(,,[,]>。elseifmin<=min&&min<=min&&min<=min。end。h=f。ifmin<=min&&min<=minm=f(d>。f(d>=f(d>。f(d>=m。g=f。elseifc==。elseifmin<=min&&min<=mind=randint(,,[,]>。:..。min<=min&&min<=minmin<=min&&min<=minelseifmin<=min&&min<=min:..elseifend。a(q,x>=a(q,x>+t。flag(s(i>>=a(q,x>。z=elseifend。flag(s(i>>>a(q,x>&&a(q,x>+t==b(q,x>flag(s(i?=b(q,x>end。b(q,x>=b(q,x>-t。z=f=h。f=g。elseifwhilef==f。flag(s(i>>>a(q,x>&&a(q,x>+t<b(q,x>。[minminmax,s]=chushijie(>。f=s。fory=:x+end。a(q,y>=a(q,y->子程序五:<循环之中,同步求解)end。function。b(q,y>=b(q,y-b(q,x+>=b(q,x>[minmaxf,a,b]=tongbujinzhan(f>a(q,x+>=flag(s(i>>+t%求该时刻个体f的最优时间flag(s(i>>=a(q,x+>>b(q,x>=flag(s(i>>Jm=[。。end。z=。end。。]。end。T=[。。。。ifz==。。]ifflag(s(i>><=flag_(q>。。flag(s(i>>=flag_(q>+t。s=f。flag_(q>=flag_(q>+t。活动化解码算法%解码程序:elseifflag(s(i>>>flag_(q>。fori=:。forx=:。k(i>=。ifa(q,x>==&&v==end。a(q,x>=flag_(q>。b(q,x>=flag(s(i>>。v=。end。forq=:。forx=:。endflag(s(i>>=flag(s(i>>+ta(q,x>=。flag_(q>=flag(s(i>>。flag_(q>=。b(q,x>=。end。end。end。end。forp=:。k(s(i>>=k(s(i>>+。flag(p>=。end。end。minmaxf=。fori=:。forq=:。q=Jm(s(i>,k(s(i>>>。ifminmaxf<flag_(q>。t=T(s(i>,k(s(i>>>。z=。v=。forx=:。minmaxf=flag_(q>。end。ifmax(flag(s(i>>,a(q,x>>+t<=b(q,x>&&z==。end。ifa=a。b=b。flag(s(i>><=a(q,x>&&a(q,x>+t==b(q,x>。申明:flag(s(i>>=b(q,x>。fory=x:。a(q,y>=a(q,y+>。b(q,y>=b(q,y+>。所有资料