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

生产调度问题及其优化算法（采用遗传算法与MATLAB编程）信息014 孙卓明八月十四日生产调度问题及其优化算法背景及摘要这是一种典型的Job-Shop动态排序问题。目前调度问题的理论研究成果重要集中在以Job-Shop问题为代表的基于最小化竣工时间的调度问题上。一种复杂的制造系统不仅也许波及到成千上万道车间调度工序，并且工序的变更又也许导致相称大的调度规模。解空间容量巨大，N个工件、M台机器的问题涉及种排列。由于问题的连环嵌套性，使得用图解措施也变得不切实际。老式的运筹学措施，即便在单目的优化的静态调度问题中也难以有效应用。本文给出三个模型。一方面通过贪婪法手工求得本问题最优解，既而通过编解码程序随机模拟优化方案得出最优解。最后采用现代进化算法中有代表性发展优势的遗传算法。文章有针对性地选用遗传算法核心环节的合适措施，采用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二模型假设1每一时刻，每台机器只能加工一种工件，且每个工件只能被一台机器所加工 ，同步加工过程为不间断；2所有机器均同步动工，且工件从机器I 到机器J 的转移过程时间损耗不计；3各工件必须按工艺路线以指定的顺序在机器上加工多次；4操作容许等待，即前一操作未完毕，则背面的操作需要等待，可用资源有限。三符号阐明及初始数据体现分析 - 第i个工件 （i=16）- 机器顺序阵 表达i工件的第 j个操作的机器号- 第j台机器 （j=14）- 工件排列阵 表达i机器上第j次加工的工件号 - 加工时间阵 为i工件的第 j个操作的时间周期 - 整个任务完毕时间整顿数据后得到：= C A B C D 0 0 0 = 8 2 4 24 6 0 0 0 A D B C 0 0 0 0 4 5 3 4 0 0 0 0 C D A B A 0 0 0 3 7 15 20 8 0 0 0 B C D A D C 0 0 7 6 21 1 16 3 0 0 D B C D A C D 0 10 4 8 4 12 6 1 0 A B A C D A C A 1 4 7 3 5 2 5 8 上述二阵直接从题目得出，而则是我们规定的。有关工件的加工时间表：(表二)产品/工件（i）:123456总计 总净加工时间（周期）441653544535247 加工工序总数（个）54567835有关机器的加工时间表：(表三)机器/设备(j):ABCD总计 总净加工时间60427075247 加工操作次数10610935分析：由于各产品总净加工时间和各机器总净加工时间之中最大值为 75，而总计为247，那么 总时间 C 介于75，247。同步各工件加工繁杂限度不一，各机器的任务量也有轻重之别。合理的调度排序是对于节省时间和资源是必要的。但愿最优化答案是75，这样达到最小值，如果答案是75，那么意味着机器D不间断工作,直至所有加工任务完毕。四贪婪法迅速求解如果按照一定规则排序，当多种工件浮现“抢占”同一机器的局面的时候,我们可以制定如下的工序安排规则: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) (表四) (图一) 上图为加工周期图（甘特图），标注数字为相应操作的周期，竣工时间为第75周期。五计算机随机模拟（编程）1编码：随机产生生产的工序操作优先顺序，进行编码，如：K= 4 3 5 6 6 2 3 1 41 6 3 5 4 5 3 6 6 4 1 5 5 1 3 2 6 2 2 4 4 1 5 6 6 5 （注：同步作为下文的染色体之用） 意思为：工件4优先被考虑进行第一次操作，然后3进行其第一步操作，然后5操作，6操作，再6操作其第二步工序，依次进行。如果前后互相不冲突，则可同步在不同机器上操作。通过排列组合得出，总共有类似K的排列序列 2多种！固然，这其中只相应解 75，247，意味着有大量排列序列相应同一加工方案，而大量加工方案又相应同一时间解。2解码： 即对编码进行翻译，产生具体可操作工序安排方案，这里采用活动化解码算法。例如工件2第i步操作（记为（2，i），且在机器A上进行）被安排在工件3第j步操作（记为JM（3,j）背面进行，那么如果安排好（3,j）后，只要（2，i）在工件2已经排序好的操作之后进行，那么操作（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的概率密度分布状况为： （如图二所示）( 图二 ) （注：75处为17次（概率为17/1000000=1/58823），76处为40次，77处167次）结论：如果想将2中排序序列以平均浮现一次的也许性进行模拟，即运营2次，计算机需运营将近150万亿年！固然，我们没有这个必要，由于我们只需要运营数万次，就很也许得到最优解75，（在随机模拟1000000次后浮现17次75，那么意味着概率大概17/1000000=1/58823，此外76处为40次，77处167次）。六遗传算法模型建立和环节解法遗传算法（Genetic Algorithm）作为一种优化算法特别适合于对象模型难于建立、搜索空间非常庞大的复杂问题的优化求解。它和模糊控制技术同样，虽然在理论上还没有完善，但是在实践中已经得到了广泛的应用。遗传算法的基本思想是：模仿生物系统“适者生成的原理，通过选择、复制、交叉、变异等简朴操作的多次反复来达到去劣存优的目的，从而获得问题的优化成果。遗传算法的实现由两个部分构成，一是编码与解码，二是遗传操作。其中遗传操作又涉及选择、复制、交叉、变异等环节。 本文根据实际状况采用了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，那么将目前的最优解作为本算法的最优解答案。1编码和解码 （同上）2交叉变换(crossover) 对2个父代临时个体进行染色体交叉变换，采用循环交叉措施（Cycle crossover CX），如父代染色体为：X：9 2 6 4 7 3 5 8 1和Y：3 4 5 8 1 6 7 2 9，如果随机选到第二位开始交叉，那么X的2相应Y的4，X的4相应Y的8，X的8相应Y的2，这样就拟定了以上为不变的染色体，其他位置的染色体互换位置，最后得到: 3 2 5 4 1 6 7 8 9, : 9 4 6 8 7 3 5 2 1,实现交叉变换。3变异选择（mutation） 采用互换操作（SWAP），即随机互换染色体中两不同基因的位置。如上面的染色体为：: 3 2 5 4 1 6 7 8 9 。随机产生变换位置号，如产生随机数3和5，那么互换数字后得到染色体： 3 2 1 4 5 6 7 8 9， 变异概率取0.1 。4选择操作（selection） 对父代2个体f1,f2和子代2个体f3,f4进行选择，通过编码操作拟定具有最优解的2个个体，成为新一代f1和f2 。 如此，通过多次编码和解码随机产生一定数量的个体，选用2个最佳个体进行交叉变换操作，产生2个新个体，然后对4个个体进行选择，产生下一代，如果某时刻通过解码操作得出最优解（所有解的下限，这里是75周期），那么算法结束，否则循环进行，直至预先给定的循环次数达到为止，以最后得到的最优解作为最后最优解。七遗传算法模拟（采用MATLAB工具编程）主程序如下：（子程序见略）% 本程序为主程序，调用如下各分支程序task= Welcome! Wait a moment please! - Writer: 孙 卓 明 ,信息 014,f1=zeros(1,35);f2=zeros(1,35); while f1=f2; % 此步避免初始染色体 f1,f2 相似，导致如下死循环 minminmax1,s1=chushijie(N); % 种群初始化；基于操作的编码方略；活动化解码算法;chushijie(N) 参数 N 为初始种群数 f1=s1 ; minminmax1, % 选用的第一种初始个体 minminmax2,s2=chushijie(N); % 再次种群初始化 f2=s2 ; minminmax2, % 选用的第二个初始个体 end;for e=1:M; % e=1:M 进行 M 次遗传操作（交叉-变异-选择) D=jiaocha(f1,f2); % 交叉变化（循环交叉操作，cycle crossover CX）,选用f1; f2; “染色体”无需变动部分基因 f3,f4=jiaocha_bianyi(f1,f2,D); % 生成交叉后的“染色体”,并进行变异选择 f3; f4; f1,f2=xuanze(f1,f2,f3,f4); % 选择：对父代f1,f2和子代f3,f4进行解码，得出2个f1; f2; 较优个体，成为下一代的父代 minmaxf1,a1,b1=tongbujinzhan(f1); % 求该时刻个体f1的最优时间(由于f1优于f2) if minmaxf1=75; f1,a1,b1,minminmax1,minminmax2,minminmax_last=minmaxf1, task=Finish! Successful! Best answer! Congratulation! , return ; end; end;f1,a1,b1,minminmax1,minminmax2,minminmax_last=minmaxf1, if minminmax_last=90; task=Finish! Action again please!,end;if minminmax_last=80&minminmax_last90; task=Finish! , end;if minminmax_last80; task=Finish! Successful!, end;八遗传算法模拟成果一方面给出最优方案:在进行某次n=100,m=200的操作后得到模拟最优成果75周期时间：minminmax1 =83 minminmax2 =78 （二个初始较优个体解）f1 =4 5 6 6 3 1 3 6 4 5 6 1 3 2 5 4 5 3 1 5 2 6 4 5 6 4 6 6 4 3 2 2 5 1 1 （f1为各工件优先选择顺序排列,即“染色体”）a1 = 5 35 39 64 0 0 0 0 0 （a1,b1为四台机器空闲周期段） 15 24 0 0 0 0 0 0 0 17 53 65 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0b1 =11 38 42 65 0 0 0 0 0 20 35 0 0 0 0 0 0 0 18 54 68 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0minminmax = 75 （最后最优解）其中机器A空闲时间段为:5-11,35-38,39-42,64-65; 机器B则为:15-20,24-35; 机器C为:17-18,53-54,65-68;机器D无空闲。如下为:取不同N和M值状况下数据优化过程以及时间上的比较: ( 表五 )NNM第一次运营第二次运营第三次运营第四次运营第五次运营平均运营时间111104-114-9898-105-9392-93-92100-132-9586-86-84/1110106-97-86108-100-89102-87-8799-90-9088-104-84/1110094-81-8181-102-7891-105-91101-84-8090-101-90/111000107-100-7892-101-76101-100-8288-97-8691-93-878.5(s)111000088-105-77103-81-7789-99-84107-104-7893-105-7880(s)10101090-108-90104-91-83104-100-9395-98-87105-106-87/101010098-96-9693-99-9088-90-80105-92-8091-95-85/10101000101-96-7891-89-8096-104-87105-105-8488-99-789.5(s)10101000099-92-7797-95-7596-104-7689-99-7691-101-7590(s)10010010095-100-8698-90-80104-99-7893-88-8192-99-80/1001001000109-98-8591-100-82100-99-77114-101-8496-110-7611(s)1001001000096-101-78101-86-76101-97-8099-110-7699-111-77100(s)阐明: 以最后一行第一次运营 “96-101-78”为例,96和101分别为2次N取100时得到的100*2个随机解中的最优解,78为通过M=10000代的遗传(交叉变异选择)后得到的最后最优解。明显地发现: M 的增大所产生的优化效果明显好于N增大产生的优化效果 M 从1-10-100-1000-10000的变化使最优解有从9*-8*-7* 的变化规律， N 的1-10-100的变化则不明显。 因此相对于随机取解, 通过遗传算法优化之后效果是明显的。此外对采用遗传算法前后模拟所得数据进行比较:第一次第二次第三次第四次第五次均值平均时间N=1000 ,M=0 78 79 818079 794 25(S)N=1,N=1,M=1000 80 75 77 7682 78.0 8.5(S) (表六)由上表看来,虽然在均值方面相差不明显,但是时间上采用遗传算法之后节省了约三分之二的运营时间,效率显而易见。九模型优缺陷及改善模型长处，采用遗传算法可对一种理论上无法求尽的NP问题以较有效措施在较短时间内得到较精确解。缺陷，采用遗传算法还不全面，只是一种简朴模型，未考虑收敛性,适配值等，对参数设立与最优解关系研究还不够进一步。 模型自身还具有漏动，仍需改善，较好设想为采用和模拟退火算法的混合遗传算法，由于时间急切，在此就不再进一步给出模型及分析了。参照文献：1 车间调度与遗传算法 王凌 清华大学出版社2数值计算的算法与分析 张可村 赵英良 科学出版社3Permutation Based GAs and Ordered Greed Peter G. Anderson,4MATLAB6.0 与科学计算 王沫然 电子工业出版社5C程序设计（第二版） 潭浩强 清华大学出版社 信息014 孙 卓 明 8月14日 本文网上下载地址(个人主页): 附录：子程序一：(种群初始化，得较优个体) function minminmax,ss=chushijie(n) % 种群初始化,如下为编码和解码过程，同步对n次选用最优化个体Jm=3 1 2 3 4 0 0 0 ;1 4 2 3 0 0 0 0 ;3 4 1 2 1 0 0 0 ;2 3 4 1 4 3 0 0 ;4 2 3 4 1 3 4 0 ;1 2 1 3 4 1 3 1 ;minminmax=200;for d=1:n; s=0; % 编码程序：基于操作的编码方略 k=1; for t=1:35 ; I=randint(1,1,1,6); while Jm(I,1)=0; I=randint(1,1,1,6); end; s(k)=I; k=k+1; x=1; while x=7; Jm(I,x)=Jm(I,x+1); x=x+1; end; Jm(I,8)=0; end;Jm=3 1 2 3 4 0 0 0 ;1 4 2 3 0 0 0 0 ;3 4 1 2 1 0 0 0 ;2 3 4 1 4 3 0 0 ;4 2 3 4 1 3 4 0 ;1 2 1 3 4 1 3 1 ;T=8 2 4 24 6 0 0 0;4 5 3 4 0 0 0 0;3 7 15 20 8 0 0 0;7 6 21 1 16 3 0 0;10 4 8 4 12 6 1 0;1 4 7 3 5 2 5 8 ; % 解码程序：活动化解码算法 for i=1:6; k(i)=1; end ; for q=1:4; for x=1:9; a(q,x)=0;b(q,x)=0;flag_(q)=0; end; end; for p=1:6; flag(p)=0; end;for i=1:35; q=Jm(s(i),k(s(i); t=T(s(i),k(s(i); z=0; v=0; for x=1:9; if max(flag(s(i),a(q,x)+t=b(q,x)&z=0 ; if flag(s(i)=a(q,x)&a(q,x)+t=b(q,x); flag(s(i)=b(q,x); for y=x:8; a(q,y)=a(q,y+1);b(q,y)=b(q,y+1); end; z=1 ; elseif flag(s(i)=a(q,x)&a(q,x)+ta(q,x)&a(q,x)+t=b(q,x) ; flag(s(i)=b(q,x);b(q,x)=b(q,x)-t;z=1; elseif flag(s(i)a(q,x)&a(q,x)+tb(q,x); for y=8:x+2; a(q,y)=a(q,y-1);b(q,y)=b(q,y-1); end;b(q,x+1)=b(q,x);b(q,x)=flag(s(i);a(q,x+1)=flag(s(i)+t; flag(s(i)=a(q,x+1);z=1; end; end; end; if z=0; if flag(s(i)flag_(q); for x=1:9; if a(q,x)=0&v=0; a(q,x)=flag_(q);b(q,x)=flag(s(i);v=1; end; end;flag(s(i)=flag(s(i)+t;flag_(q)=flag(s(i); end; end; k(s(i)=k(s(i)+1;end;minmax=0; for q=1:4; if minmaxminmax ; % 得出初始最优解 minminmax=minmax ;ss=s ;end ;end;子程序二：（父代交叉变换）function D=jiaocha(f1,f2) % 交叉变化（循环交叉操作，CX）,选用“染色体”无需变动部分基因s=randint(1,1,1,35); while f1(s)=f2(s); s=randint(1,1,1,35);end; for p=1:34; D(p)=0; end; z=0;j=1;D(j)=s;j=j+1; for i=1:35; if f1(i)=f2(s)&z=0 ; D(j)=i;j=j+1;z=1; end; end; if f2(D(j-1)=f1(s); return; end; for m=1:34; z=0; for i=1:35; if f1(i)=f2(D(j-1) & z=0 ; w=0; for t=3:j; if (i-D(t-1)0|(i-D(t-1)0; g1(D(i)=f1(D(i);g2(D(i)=f2(D(i); end;end;f3=g1;f4=g2;c=randint(1,1,1,100);if c=1 ; d1=randint(1,1,1,35); d2=randint(1,1,1,35); while d1=d2; d2=randint(1,1,1,35); end; m=f3(d1);f3(d1)=f3(d2);f3(d2)=m;elseif c=2; d1=randint(1,1,1,35); d2=randint(1,1,1,35); while d1=d2; d2=randint(1,1,1,35); end; m=f4(d1);f4(d1)=f4(d2);f4(d2)=m; end; 子程序四：（四者中选用最优二个体）function f1,f2=xuanze(f1,f2,f3,f4) % 对父代f1,f2和子代f3,f4进行解码，得出2个较优个体，成为下一代的父代min1=0;min2=0;min3=0;min4=0;h=0;g=0;min1=tongbujinzhan(f1);min2=tongbujinzhan(f2);min3=tongbujinzhan(f3);min4=tongbujinzhan(f4);if min1=min2&min1=min3&min1=min4 ; h=f1 ; if min2=min3&min2=min4; g=f2; elseif min3=min2&min3=min4; g=f3; elseif min4=min2&min4=min3; g=f4; end;elseif min2=min1&min2=min3&min2=min4 ; h=f2; if min1=min3&min1=min4 ; g=f1; elseif min3=min1&min3=min4 ; g=f3; elseif min4=min1&min4=min3 ; g=f4; end;elseif min3=min1&min3=min2&min3=min4 ; h=f3; if min1=min2&min1=min4 ; g=f1; elseif min2=min1&min2=min4 ; g=f2; elseif min4=min1&min4=min2 ; g=f4; end;elseif min4=min1&min4=min2&min4=min3 ; h=f4; if min1=min2&min1=min3 ; g=f1; elseif min2=min1&min2=min3 ; g=f2; elseif min3=min1&min3=min2 ; g=f3; end; end;end; f1=h;f2=g;while f1=f2; minminmax3,s1=chushijie(30); f2=s1;end;子程序五：（循环之中，同步求解）function minmaxf1,a1,b1=tongbujinzhan(f1) % 求该时刻个体f1的最优时间Jm=3 1 2 3 4 0 0 0 ;1 4 2 3 0 0 0 0 ;3 4 1 2 1 0 0 0 ;2 3 4 1 4 3 0 0 ;4 2 3 4 1 3 4 0 ;1 2 1 3 4 1 3 1 ;T=8 2 4 24 6 0 0 0;4 5 3 4 0 0 0 0;3 7 15 20 8 0 0 0;7 6 21 1 16 3 0 0;10 4 8 4 12 6 1 0;1 4 7 3 5 2 5 8 ; s=f1 ; % 解码程序：活动化解码算法 for i=1:6; k(i)=1; end ; for q=1:4; for x=1:9; a(q,x)=0;b(q,x)=0;flag_(q)=0; end; end; for p=1:6; flag(p)=0; end;for i=1:35; q=Jm(s(i),k(s(i); t=T(s(i),k(s(i); z=0; v=0; for x=1:9; if max(flag(s(i),a(q,x)+t=b(q,x)&z=0 ; if flag(s(i)=a(q,x)&a(q,x)+t=b(q,x); flag(s(i)=b(q,x); for y=x:8; a(q,y)=a(q,y+1);b(q,y)=b(q,y+1); end; z=1 ; elseif flag(s(i)=a(q,x)&a(q,x)+ta(q,x)&a(q,x)+t=b(q,x) ; flag(s(i)=b(q,x);b(q,x)=b(q,x)-t;z=1 ; elseif flag(s(i)a(q,x)&a(q,x)+tb(q,x); for y=8:x+2; a(q,y)=a(q,y-1);b(q,y)=b(q,y-1); end;b(q,x+1)=b(q,x);b(q,x)=flag(s(i);a(q,x+1)=flag(s(i)+t; flag(s(i)=a(q,x+1);z=1; end; end;end;if z=0; if flag(s(i)flag_(q); for x=1:9; if a(q,x)=0&v=0; a(q,x)=flag_(q);b(q,x)=flag(s(i);v=1; end; end;flag(s(i)=flag(s(i)+t;flag_(q)=flag(s(i); end;end;k(s(i)=k(s(i)+1; end;minmaxf1=0; for q=1:4; if minmaxf1flag_(q); minmaxf1=flag_(q); end;end; a1=a; b1=b;