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

1、matlab生产调度问题及其优化 算法生产调度问题及其优化算法（ 采 用 遗 传 算 法 与 MATLAB 编 程 ）信 息 014 孙 卓 明二零零三年八月十四日生产调度问题及其优化算法背景及摘要这是一个典型的Job-Shop动态排序问题。目前调度问题的理论研究成果主 要集中在以Job-Shop问题为代表的基于最小化完工时间的调度问题上。一个复 杂的制造系统不仅可能涉及到成千上万道车间调度工序，而且工序的变更又可 能导致相当大的调度规模。解空间容量巨大，N个工件、M台机器的问题包含（N!）M种排列。由于问题的连环嵌套性，使得用图解方法也变得不切实际。传统 的运筹学方法，即便在单目标优化的静态

2、调度问题中也难以有效应用。本文给出三个模型。首先通过贪婪法手工求得本问题最优解，既而通过编 解码程序随机模拟优化方案得出最优解。最后采用现代进化算法中有代表性发 展优势的遗传算法。文章有针对性地选取遗传算法关键环节的适宜方法，采用 MATLAB件实现算法模拟，得出优化方案，并与计算机随机模拟结果加以比较 显示出遗传算法之优化效果。对车间调度系列冋题的有效解决具有一定参考和借鉴价值。问题重述某重型机械厂产品都是单件性的，其中有一车间共有A，B，C，D四种不同设备，现接受6件产品的加工任务，每件产品接受的程序在指定的设备上加 工，其工序与加工周期如下表：（S-设备号、T-周期）1 品1234567

3、8STSTSTSTSTSTSTST1C8A2B4C24D62A4D5B3C 143C3D7A15B20A84B7C6D21A1D16c :35D10B4C8D I4I A I121 C 16D16A1B4A7C3D5A2C5A8（表一）条件：1、每件产品必须按规定的工序加工，不得颠倒；2、每台设备在同一时间只能担任一项任务。（每件产品的每个工序为一个任务）-18 -问题：做出生产安排，希望在尽可能短的时间里，完成所接受的全部任务 要求：给出每台设备承担任务的时间表。注：在上面，机器A，B, C D即为机器1，2,3, 4,程序中以数字1, 2，3, 4表示, 说明时则用A, B, C D模型假

4、设i 每一时刻，每台机器只能加工一个工件，且每个工件只能被一台机器所加 工，同时加工过程为不间断；2所有机器均同时开工，且工件从机器I到机器J的转移过程时间损耗不计;3 各工件必须按工艺路线以指定的次序在机器上加工多次；4 操作允许等待，即前一操作未完成，则后面的操作需要等待，可用资源有 限。三符号说明及初始数据表达分析Ji -第i个工件 （i=16）Jm -机器顺序阵M（i, j）表示i工件的第j个操作的机M j-第j台机器 Mj-工件排列阵（j=1 4）Mj（i,j）表示i机器上第j次加工的工件T -加工时间阵 T（i, j）为i工件的第j个操作的时间周期C -整个任务完成时间整理数据后得

5、到:JM = C A B C D 0 0 0 A D B C 0 0 0 0 C D A B A 0 0 0 B C D A D C 0 0 D B C D A C D 0 A B A C D A C A 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 010 4 8 4 12 6 1 01 4 7 3 5 2 5 8 上述二阵直接从题目得岀，而M j则是我们要求的。关于工件的加工时间表：（表二）产品/工件（i ）:123456总计一Ji总净加期工时间441653544535247Ji加工个序总数54

6、567835关于机器的加工时间表：（表三）机器/设备（j）：ABCD总计Mj总净加工 时间60427075247Mj加工操作 次数10610935分析：由于各产品总净加工时间和各机器总净加工时间之中最大值为75,而总计为247,那 么总时间C介于175，247。同时各工件加 工繁杂程度、不一，各机器的任务量也有轻重之 另I。合理的调度排序是对于节省时间和资源是 必要的。希望最优化答案是75,这样达到最小值， 如果答案是75,那么意味着机器不间断工作, 直至全部加工任务完成。四贪婪法快速求解如果按照一定规则排序，当多个工件出现“抢占”同一机器的局面的时候 我们可以制定如下的工序安排规则：1. 优

7、先选择总剩余时间或总剩余操作较多的工件。（如果出现总剩余加工时间多者总剩余操作数反而较少的情况时，按照程度具体情况具体分析）。2. 机器方面来说，尽量避免等待空闲时间，优先考虑剩余净加工时间或者剩余加工总次数较多的机器，尤其是机器D,即倘若能够使机器不间断工作且其 他机器完工时间均不多余75时，那么就可以得到最优解。首先按照最优化时间为75的设想避免D出现等待，排序后得到升以下具体 排列顺序。各机器承担任务表为（其中粗体字为对应工件产品号，括号内为对应时间周期段）:操作1操作2操作3操作4操作5操作6操作7操作8操作9操作10A6216345636(2(12(14(21(43(55(57(66

8、1)-5)-13-20-3536)-54-56-64-73)|)B465132(8(12(16(36(561-7-11-15-19-55-58)C3145615624(4(12(18(26(29(55(61(66(701-3-11-17-25-28-52-60-65-69-72)D534562415(1(11(18(39(43(48(53(69(7-10-17-38-42-47-52-68-745)（表四）146271516122881741441620338683242654 3107214551661机器机器机器机器1020304050607080（图一）上图为加工周期图（甘特图），标注数

9、字为相应操作的周期，完工时间为第 75周期。五计算机随机模拟（编程）1 .编码：随机产生生产的工序操作优先顺序，进行编码，如：K= 4 3 5 6 62 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 1023多种！ 当然，这其中只对应解75，247，意味着有大量排列序列对应同一加

10、工方案，而大量加工方案又对应同一时间解。2. 解码：即对编码进行翻译，产生具体可操作工序安排方案， 这里采 用活动化解码算法。例如工件 2第i步操作（记为Jm （2, i），且在机 器A上进行）被安排在工件3第j步操作（记为JM （3,j）后面进行， 那么如果安排好Jm（3,j）后，只要Jm （2，i）在工件2已经排序好的操作之后进行，那 么操 作Jm （2，i）可插入到机器A处最前可安置的时间段进行。在这里，一个编码序列对应一个加工方案， 而一个加工方案可对应 一个或多个编码序列，这就是二者之关系。3. 编程：通过一组随机编码产生一生产加工优先序列，通过解码过程产生相 应加工方案及其总耗费时

11、间 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 平均

12、值 76.3,每回耗时 4 分钟d.模拟1000000次得到的解C的概率密度分布情况为：（如图二所示）75处为 17次（概率为75处为 17次（概率为17/1000000=1/58823), 76 处为 40 次，77 处 16717/1000000=1/58823)，76 处为 40 次，77 处 167次)结论：如果想将2 1023中排序序列以平均出现一次的可能性进行模拟，即运行2 1023次，计算机需运行将近150万亿年！当然，我们没有 这个必要，因为我们只需要运行数万次，就很可能得到最优解 75 （在随机模拟1000000次后出现17次75,那么意味着概率大约17/1000000=1/

13、58823,另外 76 处为 40 次，77 处 167次）。结论：如果想将2 1023中排序序列以平均出现一次的可能性进行模拟,即运行2 1023次，计算机需运行将近150万亿年！当然，我们没有这个必要，因为我们只需要运行数万次，就很可能得到最优解75（在随机模拟1000000次后出现17次75,那么意味着概率大约17/1000000=1/58823,另外 76 处为 40 次，77 处 167 次)六遗传算法模型建立和步骤解法遗传算法（Genetic Algorithm ）作为一种优化算法特别适合于对象模型难 于建立、搜索空间非常庞大的复杂问题的优化求解。它和模糊控制技术一样， 虽然在理论

14、上还没有完善，但是在实践中已经得到了广泛的应用。遗传算法的 基本思想是：模仿生物系统“适者生成"的原理，通过选择、复制、交叉、变异 等简单操作的多次重复来达到去劣存优的目的，从而获得问题的优化结果。遗 传算法的实现由两个部分组成，一是编码与解码，二是遗传操作。其中遗传操 作又包括选择、复制、交叉、变异等步骤。本文根据实际情况采取了 1-6整数编码。数字1 , 2, 3, 4, 5, 6分别代表 6件待加工产品六遗传算法模型建立和步骤解法遗传算法（Genetic Algorithm ）作为一种优化算法特别适合于对象模型难于建立、搜索空间非常庞大的复杂问题的优化求解。它和模糊控制技术一样

15、,虽然在理论上还没有完善，但是在实践中已经得到了广泛的应用。遗传算法的基本思想是：模仿生物系统“适者生成II的原理，通过选择、复制、交叉、变异等简单操作的多次重复来达到去劣存优的目的，从而获得问题的优化结果。遗传算法的实现由两个部分组成,编码与解码，二是遗传操作。其中遗传操作又包括选择、复制、交叉、变异等步骤。本文根据实际情况采取了 1-6整数编码。数字1 , 2, 3, 4, 5, 6分别代表6件待加工产品本文遗传算法基本流程：通过编码，解码程序随机产生 N个（有一定数 量,如50或100）个体构成初始种群a）从初始中群中选取2个具有最优染色体（最有 排序方案）的个体作为临时个体（父代）；b

16、）如果此2个体中有一个个体、通过解码操对么个束优算法滑使最时IL 2染色体d）对对e）重C）作）代周作结束此算法，宀、个临时个体以一定方式（小概率:互换子代换和变 个个体,做操 执行最优解作为仍1 .编码和解码（同上）5,那么 案。2 .交叉变换（crossoverJ临时个体进行染色体交叉变 :叉方法（Cycle crossover£色体为： X: 9 2 6 4 7 3 5i交叉1为那么】X的，如对应随的实现交叉变换。Y置,最后騁5 2 1 3 2 53 .变异选择（卫utation ）染色体用互不同体为：X s小操基LSWAP，如上随机交扌因的位9;、"变异概率的染随那

17、3 2 1 4 5 6 7 8。置号，5如产生随8机数3和。5,后得到染色体:4.选择操作（selection ） 权仃对父代牛2个体、 优解的进个个体，成编一作子定具有最体七.遗传算法模拟（采用MATLAB：具编程）主程序如下：(子程序见略)%本程序为主程序，调用以下各分支程序task= 'Welcome! Wait a moment please! - Writer: f仁 zeros(1,35);f2=zeros(1,35);while f1=f2;%minminmax1,s1=chushijie(N) ；%f1=s1 ; minminmaxl,%minminmax2,s2=ch

18、ushijie(N) ；%f2=s2 ; minminmax2,%end;for e=1: M% e=1:MD=jiaocha(f1,f2);%f1; f2;f3,f4=jiaocha_bianyi(f1,f2,D); % f3; f4;f1,f2=xuanze(f1,f2,f3,f4);%f1; f2;minmaxf1,a1,b1=tongbujinzhan(f1); % if minmaxf1=75;孙卓明，信息014',此步避免初始染色体f1,f2相同，导致以下死循环种群初始化；基于操作的编码策略；活动化解码算法;chushijie（N） 参数N为初始种群数选取的第一个初始个体再

19、次种群初始化选取的第二个初始个体进行M次遗传操作（交叉-变异-选择）交叉变化（循环交叉操作，cycle crossover CX ）,选取“染色体”无需变动部分基因生成交叉后的“染色体”，并进行变异选择选择：对父代f1,f2和子代f3,f4进行解码，得出2个 较优个体，成为下一代的父代求该时刻个体f1的最优时间（因为f1优于f2）f1,a1,b1,minminmax1,minminmax2,minminmax_last=minmaxf1.task='Finish! Successful! Best answer! Congratulation! ' , return ;end;

20、 end;f1,a1,b1,minminmax1,minminmax2,minminmax_last=minmaxf1,if minminmax_last>=90; task='Finish! Action again please!',end;if minminmax_last>=80&&minminmax_last<90; task='Finish!' , end;if minminmax_last<80; task='Finish! Successful!', end;八遗传算法模拟结果首先给出最优方

21、案：在进行某次n=100,m=200的操作后得到模拟最优结果 75周期时间：mi nminm ax1 =83 mi nmi nm ax2 =78（二个初始较优个体解）fl =4 5 6 6 3 1 3 6 4 5 6 1 3 2 5 4 5 31 5 2 6 4 5 6 4 6 6 4 3 2 2 5 1 1（f1为各工件优先选择顺序排列，即“染色体”）a1 = 5 35 39 6400000（ a1,b1为四台机器空闲周期段）15240000000175365000000000000000b1 =11 :38426500 0002035000000018546800000000000000

22、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-198-1092-9100-186-86/14-985-933-9232-95-841110106-9108-1102-899-9088-10/7-8600-897-87-904-841110094

23、-881-1091-10101-890-10/1-812-785-914-801-9011100107-192-10101-188-991-938.5(s)000-781-7600-827-86-871110088-10103-889-9107-193-1080(s)005-771-779-8404-785-78111090-10104-9104-195-9105-1/00 ,8-901-8300-938-8706-871110098-9693-988-90105-991-95/00-969-90-802-80-8511100101-991-896-10105-188-999.5(s)0006

24、-789-804-8705-84-781110099-997-996-1089-991-1090(s)00002-775-754-769-761-751110095-1098-9104-993-892-9/000-860-809-788-819-800011100109-991-10100-9114-196-1111(s)0008-850-829-7701-840-76001110096-10101-8101-999-1199-11100(s)00001-786-767-800-761-7700说明：以最后一行第一次运行“96-101-78 ”为例,96和101分别为2次N取100时得到的10

25、0*2个随机解中的最优解,78为经过M=10000弋的遗传（交 叉变异选择）后得到的最终最优解。明显地发现：M的增大所产生的优化效果明显好于 N增大产生的优化效果M 从1-10-100-1000-10000的变化使最优解有从 9*-8*-7*的变化规律，N 的1-10-100的变化则不明显。因此相对于随机取解，经过遗传算法优化之后效果是显著的。另外对采用遗传算法前后模拟所得数据进行比较第次第次第次第四次第五次均 值平均 时间N=1000 ,M=0787981807979 . 425(S)N=1,N=1,M=1000807577768278.08.5(S)（表六）由上表看来，虽然在均值方面相差不

26、显著，但是时间上采用遗传算法之 后节约了约三分之二的运行时间，效率显而易见。九模型优缺点及改进模型优点，采用遗传算法可对一个理论上无法求尽的NP问题以较有效方法在较短时间内得到较精确解。缺点，采用遗传算法还不全面，只是一个简单模型，未考虑收敛性，适配值等，对参数设置与最优解关系研究还不够深入。在此就不再深入给出模型及分析了。模型本身还具有漏动，仍需改进，较好设想为采用和模拟退火算法的混 合遗传算法，由于时间紧迫，参考文献:1.车间调度与遗传算法2 数值计算的算法与分析3. Permutation Based GAs and Ordered Greed Peter G. Anderson,4.

27、MATLAB6.0与科学计算5. C程序设计（第二版）王凌张可村赵英良王沫然潭浩强2003清华大学出版社 科学出版社电子工业出版社 清华大学出版社信息014孙卓明年8月14日本文网上下载地址（个人主页）:附录:子程序一：（种群初始化，得较优个体）function2 1 3 4 1 3 1 ; minminmax=200;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 21 0 0 0 ;2 3 4 1 4 3 0 0 ;4 2 3 4 1 3 4

28、0 ;1for d=1:n;s=0;% 编码程序：基于操作的编码策略k=1;for t=1:35 ;elseifl=randint(1,1,1,6); while Jm(l,1)=0;l=randint(1,1,1,6); end;s(k)=l;flag(s(i)<=a(q,x)&&a(q,x)+t<b(q,x) a(q,x)=a(q,x)+t;flag(s(i)=a(q,x);z=1 ;elseifflag(s(i)>a(q,x )&&a(q,x)+t=b(q,x) flag(s(i)=b(q,x);b(q,x)=b(q,x)-t;z=1;e

29、lseifflag(s(i)>a(q,x )&&a(q,x)+t<b(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); flag(s(i)=flag_(q)+t;5flag_(q)=flag_(q)+t;elseif flag(s(i)>flag_(q);fo

30、r 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 minmax<flag_(q); minmax=flag_(q);end;end;ifminminmax>minmax ;%得出初始最优解minminmax=minmax ;ss=s ;end ;end;k=k+1;x=1;while x<

31、=7;Jm(l,x)=Jm(l,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 21 0 0 0 ;2 3 4 1 4 3 0 0 ;4 2 3 4 1 3 4 0 ;12 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 208 0 0 0;7 6 21 1 16 3 0 0;10 4 8 4 12 6 1 0;1473528%解码程序：活动化解码算法for i=1:6;k(i)=1;end ;for q=1:4;for x=1:9;a(

32、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;ifmax(flag(s(i),a(q,x)+t<=b(q,x)&&z=0 ;ifflag(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 ;19子程序三：（变异选

33、择，形成子代）function22子程序二：（父代交叉变换）function D=jiaocha（f1,f2） %交叉变 化（循环交叉操作，CX）,选取“染色体”无需变f3,f4=jiaocha_bianyi(f1,f2,D)%生成交叉后的“染色体”，并进行变异选择 g2=f1;g1=f2;for i=1:34;子程序四：(四者中选取最优二个体)functionf1,f2=xuanze(f1,f2,f3,f4)c对父代f1,f2和子代f3,f4进行解码，得出2个较 优个体，成为下一代的父代min1=0;min2=0;min3=0;min4=0;h=0;g=0;min1=tongbujinzha

34、n(f1);min2=tongbujinzhan(f2);min3=tongbujinzhan(f3);动部分基因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

35、) && z=0 ; w=0; for t=3:j;if (i-D(t-1)>0|(i-D(t-1)<0;w=w+1; end;end;if w=j-2;D(j)=i; j=j+1;z=1;end ;end ;end;if f2(D(j-1)=f1(s)&&z=1;return;if D(i)>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);w

36、hile d仁=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 d仁=d2;d2=randint(1,1,1,35);end; m=f4(d1);f4(d1)=f4(d2);f4(d2)=m;end;end;end;if min1<=min2&&m in1<=min3&&m in1<=min4h=f1 ; if min2<=min3&&am

37、p;m in2<=min4; g=f2;elseif min3<=min2&&m in3<=min4; g=f3;elseif min4<=min2&&m in4<=min3; g=f4; end;elseifmin2<=min1 &&m in2<=min3&&m in2<=min4h=f2; if min1<=min3&&m in1<=min4 ; g=f1; elseif min3<=min1 &&m in3<=min4 ;

38、 g=f3; elseif min4<=min1 &&min4<=min3 ; g=f4;end;elseifmin3<=min1 &&m in3<=min2&&m in3<=min4 ; h=f3; if min1<=min2&&m in1<=min4 ; g=f1;elseif min2<=min1 &&m in2<=min4 ; g=f2; elseif min4<=min1 &&min4<=min2 ; g=f4;end;el

39、seifmin4<=min1 &&m in4<=min2&&m in4<=min3h=f4; if min1<=min2&&m in1<=min3 ; g=f1; elseif min2<=min1 &&m in2<=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;子程序五：(循环之中，同步求解)functionminmaxf1,a1,b