matlab生产调度问题及其优化算法

整理文档很辛苦,赏杯茶钱您下走!

免费阅读已结束,点击下载阅读编辑剩下 ...

阅读已结束,您可以下载文档离线阅读编辑

资源描述

生产调度问题及其优化算法(采用遗传算法与MATLAB编程)信息014孙卓明二零零三年八月十四日-1-生产调度问题及其优化算法背景及摘要这是一个典型的Job-Shop动态排序问题。目前调度问题的理论研究成果主要集中在以Job-Shop问题为代表的基于最小化完工时间的调度问题上。一个复杂的制造系统不仅可能涉及到成千上万道车间调度工序,而且工序的变更又可能导致相当大的调度规模。解空间容量巨大,N个工件、M台机器的问题包含MN)!(种排列。由于问题的连环嵌套性,使得用图解方法也变得不切实际。传统的运筹学方法,即便在单目标优化的静态调度问题中也难以有效应用。本文给出三个模型。首先通过贪婪法手工求得本问题最优解,既而通过编解码程序随机模拟优化方案得出最优解。最后采用现代进化算法中有代表性发展优势的遗传算法。文章有针对性地选取遗传算法关键环节的适宜方法,采用MATLAB软件实现算法模拟,得出优化方案,并与计算机随机模拟结果加以比较显示出遗传算法之优化效果。对车间调度系列问题的有效解决具有一定参考和借鉴价值。一.问题重述某重型机械厂产品都是单件性的,其中有一车间共有A,B,C,D四种不同设备,现接受6件产品的加工任务,每件产品接受的程序在指定的设备上加工,其工序与加工周期如下表:(S-设备号、T-周期)工序产品12345678STSTSTSTSTSTSTST1C8A2B4C24D62A4D5B3C43C3D7A15B20A84B7C6D21A1D16C35D10B4C8D4A12C6D16A1B4A7C3D5A2C5A8(表一)条件:1、每件产品必须按规定的工序加工,不得颠倒;2、每台设备在同一时间只能担任一项任务。(每件产品的每个工序为一个任务)问题:做出生产安排,希望在尽可能短的时间里,完成所接受的全部任务。要求:给出每台设备承担任务的时间表。注:在上面,机器A,B,C,D即为机器1,2,3,4,程序中以数字1,2,3,4表示,说明时则用A,B,C,D-2-二.模型假设1.每一时刻,每台机器只能加工一个工件,且每个工件只能被一台机器所加工,同时加工过程为不间断;2.所有机器均同时开工,且工件从机器I到机器J的转移过程时间损耗不计;3.各工件必须按工艺路线以指定的次序在机器上加工多次;4.操作允许等待,即前一操作未完成,则后面的操作需要等待,可用资源有限。三.符号说明及初始数据表达分析iJ-第i个工件(i=1…6)MJ-机器顺序阵)(jiJM,表示i工件的第j个操作的机器号jM-第j台机器(j=1…4)JM-工件排列阵),(jiMJ表示i机器上第j次加工的工件号T-加工时间阵),(jiT为i工件的第j个操作的时间周期C-整个任务完成时间整理数据后得到:MJ=[CABCD000]T=[824246000][ADBC0000][45340000][CDABA000][3715208000][BCDADC00][7621116300][DBCDACD0][1048412610][ABACDACA][14735258]上述二阵直接从题目得出,而JM则是我们要求的。关于工件的加工时间表:(表二)产品/工件(i):123456总计iJ总净加工时间(周期)441653544535247iJ加工工序总数(个)54567835关于机器的加工时间表:(表三)机器/设备(j):ABCD总计jM总净加工时间60427075247jM加工操作次数10610935分析:由于各产品总净加工时间和各机器总净加工时间之中最大值为75,而总计为247,那么总时间C介于[75,247]。同时各工件加工繁杂程度不一,各机器的任务量也有轻重之别。合理的调度排序是对于节省时间和资源是必要的。希望最优化答案是75,这样达到最小值,如果答案是75,那么意味着机器D不间断工作,直至全部加工任务完成。-3-四.贪婪法快速求解如果按照一定规则排序,当多个工件出现“抢占”同一机器的局面的时候,我们可以制定如下的工序安排规则:1.优先选择总剩余时间或总剩余操作较多的工件。(如果出现总剩余加工时间多者总剩余操作数反而较少的情况时,按照程度具体情况具体分析)。2.机器方面来说,尽量避免等待空闲时间,优先考虑剩余净加工时间或者剩余加工总次数较多的机器,尤其是机器D,即倘若能够使机器D不间断工作且其他机器完工时间均不多余75时,那么就可以得到最优解。首先按照最优化时间为75的设想避免D出现等待,排序后得到升以下具体排列顺序。各机器承担任务表为(其中粗体字为对应工件产品号,括号内为对应时间周期段):操作1操作2操作3操作4操作5操作6操作7操作8操作9操作10A6(1)2(2-5)1(12-13)6(14-20)3(21-35)4(36)5(43-54)6(55-56)3(57-64)6(66-73)B4(1-7)6(8-11)5(12-15)1(16-19)3(36-55)2(56-58)C3(1-3)1(4-11)4(12-17)5(18-25)6(26-28)1(29-52)5(55-60)6(61-65)2(66-69)4(70-72)D5(1-10)3(11-17)4(18-38)5(39-42)6(43-47)2(48-52)4(53-68)1(69-74)5(75)(表四)10371784421646484253167524201516231666151242388101020304050607080D机器C机器B机器A机器(图一)上图为加工周期图(甘特图),标注数字为相应操作的周期,完工时间为第75周期。-4-五.计算机随机模拟(编程)1.编码:随机产生生产的工序操作优先顺序,进行编码,如:K=[43566231416354536641551326224415665](注:同时作为下文的染色体之用)意思为:工件4优先被考虑进行第一次操作,然后3进行其第一步操作,然后5操作,6操作,再6操作其第二步工序,依次进行。如果前后互相不冲突,则可同时在不同机器上操作。通过排列组合得出,总共有类似K的排列序列22310多种!当然,这其中只对应解[75,247],意味着有大量排列序列对应同一加工方案,而大量加工方案又对应同一时间解。2.解码:即对编码进行翻译,产生具体可操作工序安排方案,这里采用活动化解码算法。例如工件2第i步操作(记为MJ(2,i),且在机器A上进行)被安排在工件3第j步操作(记为JM(3,j))后面进行,那么如果安排好MJ(3,j)后,只要MJ(2,i)在工件2已经排序好的操作之后进行,那么操作MJ(2,i)可插入到机器A处最前可安置的时间段进行。在这里,一个编码序列对应一个加工方案,而一个加工方案可对应一个或多个编码序列,这就是二者之关系。3.编程:通过一组随机编码产生一生产加工优先序列,通过解码过程产生相应加工方案及其总耗费时间C.N次模拟后即可得出解C的概率密度分布情况以及相对最优解(N个C的最小值,如80,77等,甚至出现75)。4.计算机模拟所得数据分析a.进行100次模拟得出最优解情况:(共运行10次)82,83,82,84,78,80,81,83,87,82平均值82.2,每回耗时约3秒b.进行1000次模拟得出最优解情况:(共运行10次)80,79,78,78,79,79,76,80,77,78平均值78.4,每回耗时25秒c.进行10000次模拟得出最优解情况:(共运行10次)76,77,77,75,76,76,77,76,76,77平均值76.3,每回耗时4分钟d.模拟1000000次得到的解C的概率密度分布情况为:(如图二所示)-5-(图二)(注:75处为17次(概率为17/1000000=1/58823),76处为40次,77处167次)结论:如果想将22310中排序序列以平均出现一次的可能性进行模拟,即运行22310次,计算机需运行将近150万亿年!当然,我们没有这个必要,因为我们只需要运行数万次,就很可能得到最优解75,(在随机模拟1000000次后出现17次75,那么意味着概率大约17/1000000=1/58823,另外76处为40次,77处167次)。六.遗传算法模型建立和步骤解法遗传算法(GeneticAlgorithm)作为一种优化算法特别适合于对象模型难于建立、搜索空间非常庞大的复杂问题的优化求解。它和模糊控制技术一样,虽然在理论上还没有完善,但是在实践中已经得到了广泛的应用。遗传算法的基本思想是:模仿生物系统“适者生成的原理,通过选择、复制、交叉、变异等简单操作的多次重复来达到去劣存优的目的,从而获得问题的优化结果。遗传算法的实现由两个部分组成,一是编码与解码,二是遗传操作。其中遗传操作又包括选择、复制、交叉、变异等步骤。本文根据实际情况采取了1-6整数编码。数字1,2,3,4,5,6分别代表6件待加工产品。本文遗传算法基本流程:通过编码,解码程序随机产生N个(有一定数量,如50或100)个体构成初始种群a)从初始中群中选取2个具有最优染色体(最有排序方案)的个体作为临时个体(父代);b)如果此2个体中有一个个体通过解码操作能够实现最优排序(即使总时间为75周期),那么结束此算法,得到最优解;c)对2个临时个体以一定方式(循环交叉)执行染色体交叉变换和变异选择(小概率,互换操作),产生2个新的个体;d)对父代和子代共4个个体进行选择,从中选出最佳的2个个体,做为下一代的父代;e)重复执行第二步(b)操作;f)如果执行完M步后仍然未得出答案75,那么将目前的最优解作为本算法的最优解答案。-6-1.编码和解码(同上)2.交叉变换(crossover)对2个父代临时个体进行染色体交叉变换,采用循环交叉方法(CyclecrossoverCX),如父代染色体为:X:[926473581]和Y:[345816729],如果随机选到第二位开始交叉,那么X的2对应Y的4,X的4对应Y的8,X的8对应Y的2,这样就确定了以上为不变的染色体,其余位置的染色体互换位置,最后得到X:[325416789],Y:[946873521],实现交叉变换。3.变异选择(mutation)采用互换操作(SWAP),,即随机交换染色体中两不同基因的位置。如上面的染色体为:X:[325416789]。随机产生变换位置号,如产生随机数3和5,那么交换数字后得到染色体:[321456789],变异概率取0.1。4.选择操作(selection)对父代2个体f1,f2和子代2个体f3,f4进行选择,通过编码操作确定具有最优解的2个个体,成为新一代f1和f2。如此,通过多次编码和解码随机产生一定数量的个体,选取2个最佳个体进行交叉变换操作,产生2个新个体,然后对4个个体进行选择,产生下一代,如果某时刻通过解码操作得出最优解(所有解的下限,这里是75周期),那么算法结束,否则循环进行,直至预先给定的循环次数达到为止,以最后得到的最优解作为最终最优解。七.遗传算法模拟(采用MATLAB工具编程)主程序如下:(子程序见略)%本程序为主程序,调用以下各分支程序task='Welcome!Waitamomentplease!---Writer:孙卓明,信息014',f1=zeros(1,35);f2=zeros(1,35);whilef1==f2;%此步避免初始染色体f1,f2相同,导致以下死循环[minminmax1,s1]=chushijie(N);%种群初始化;基于操作的编码策略;活动化解码算法;chushijie(N)参数N为初始种群数f1=s1;minminmax1,%选取的第一个初始个体[minminmax2,s2]=chushijie(N);%再次种群初始化f2=s2;minminmax2,%选取的第二个初始个体end;fore=1:M;%e=1:M进行M次遗传操作(交叉-变异-选择)[D]=jiaocha(f1,f2);%交叉变化(循环交叉操作,cyclecrossoverCX),选取f1;f2;“染色体”无需变动部分基因[f3,f4]=jiaocha_

1 / 13
下载文档,编辑使用

©2015-2020 m.777doc.com 三七文档.

备案号:鲁ICP备2024069028号-1 客服联系 QQ:2149211541

×
保存成功