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

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

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

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

4、工过程为不间断；2所有机器均同时开工，且工件从机器I到机器J的转移过程时间损耗不 计；3 各工件必须按工艺路线以指定的次序在机器上加工多次；4 操作允许等待，即前一操作未完成，则后面的操作需要等待，可用资源有 限。三符号说明及初始数据表达分析凶-S- IrJ- 匡-第i个工件i=16）机器顺序阵 二一表示i工件的第j个操作的机器号第j台机器j=14）工件排列阵上| 表示i机器上第j次加工的工件号加工时间阵I为i工件的第j个操作的时间周期-整个任务完成时间整理数据后得到:工=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

5、 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 上述二阵直接从题目得岀，而丨则是我们要求的关于工件的加工时间表：（表二产品/工件i ）:123456总计-总净加工时间 周期）441653544535247凶加工工序总数 个）54567835关于机器的加工时间表：（表三机器/设备（j：ABCD总计因总净加工时间60427075247M加工操作次数10610935分析:

6、因为各产品总净加工时间和各机器总净加工时间之中最大值为75，而总计为247，那么总时间C介于75，247。同时各工件加工繁杂程度不一，各机器的任务量也有 轻重之别。合理的调度排序是对于节省时间和资源是必要的。希望最优化答案是75,这样达到最小值，如果答案是75，那么意味着机器 D不间断工作,直至全部加工任务完成。四贪婪法快速求解如果按照一定规则排序，当多个工件出现“抢占”同一机器的局面的时候 我们可以制定如下的工序安排规则：1. 优先选择总剩余时间或总剩余操作较多的工件。如果出现总剩余加工时间多者总剩余操作数反而较少的情况时，按照程度具体情况具体分析）。2. 机器方面来说，尽量避免等待空闲时间

7、，优先考虑剩余净加工时间或者剩余加工总次数较多的机器，尤其是机器D,即倘若能够使机器不间断工作且其 他机器完工时间均不多余75时，那么就可以得到最优解。首先按照最优化时间为75的设想避免D出现等待，排序后得到升以下具体 排列顺序。各机器承担任务表为（其中粗体字为对应工件产品号，括号内为对应时间周期 段:操作1操作2操作3操作4操作5操作6操作7操作8操作9操作10A6216345636 丁(1>(2-5>(12-13>(14-20>(21-35>(36>(43-54>(55-56>(57-64>(66-73>B465132 (1-7&

8、gt;(8-11>(12-15>(16-19>(36-55>(56-58> JC314561 :56 :2 :4:(1-3>(4-11>(12-17>(18-25>(26-28>(29-52>(55-60>(61-65>(66-69>(70-72>D534562415(1-10>(11-17>(18-38>(39-42>(43-47>(48-52>(53-68>(69-74>(75>（表四（图一 上图为加工周期图 甘特图），标注数字为相应操作的周期，完

9、工时间为第 75周期五计算机随机模拟 编程）1 .编码:随机产生生产的工序操作优先顺序，进行编码，如：K= 4 35 6 6 2 31 41 6 3 5 4 53 6 6 4 1 5 5 1 3 2 6 2 2 4 4 1 5 6 65注：同时作为下文的染色体之用）意思为：工件 4优先被考虑进行第一 次操作，然后3进行其第一步操作，然后5操作，6操作，再6操作其第二步 工序，依次进行。如果前后互相不冲突，则可同时在不同机器上操作。通过排列组合得出，总共有类似K的排列序列2厂I多种！当然，这其中只对应解75，247,意味着有大量排列序列对应同一加工 方案，而大量加工方案又对应同一时间解。2. 解

10、码：即对编码进行翻译，产生具体可操作工序安排方案，这里采用活动化解码算法。例如工件2第i步操作记为而2，i），且在机器A上进行）被安排 在工件3第j步操作 记为JM3,j）后面进行，那么如果安排好 回 3,j）后，只要回2, i）在工件2已经排序好的操作之后进行，那么操 作因2, i）可插入到机器A处最前可安置的时间段进行。在这里，一个编码序列对应一个加工方案，而一个加工方案可对应一 个或多个编码序列，这就是二者之关系。3. 编程：通过一组随机编码产生一生产加工优先序列，通过解码过程产生相应加工 方案及其总耗费时间C .N次模拟后即可得出解C的概率密度分布情况以及相对最优解N个C的最 小值，如

11、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处为 1

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

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

14、父代）；b）如果此2个体中有一个个体通过解码操作能够实现最优排序即使总时间为75周期），那么结束此算法，得到最优解；c）对2个临时个体以一定方式（循环交叉 执行染色体交叉变换和变异选择小概率，互换操作），产生2个新的个体；d）对父代和子代共4个个体进行选择，从中选出最佳的2个个体，做为下一代的父代；e）重复执行第二步（b操作；f）如果执行完M步后仍然未得出答案 75,那么将目前的最优解作为本算法的最优解答 案。1 .编码和解码 同上）2 .交叉变换（crossover对2个父代临时个体进行染色体交叉变换，采用循环交叉方法vCycle crossoverCX，如父代染色体为：X： 9 2 6 4

15、 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，这样就确定了以上为不变的染色体，其余位置的染色体互换位置，最后得到-J :3 2 5 4 1 6 7 8 9,:9 4 6 8 7 3 5 2 1,实现交叉变换。3 .变异选择vmutation ）采用互换操作SWAp,，即随机交换染色体中两不同基因的位置。如上面的染色体为：I I :3 2 5 4 1 6 7 8 9。随机产生变换位置号，如产生随机数3和5,那么交换数字后得到染色体：3 2 1 4 5 6 7 8 9,变异概率取0.1。

16、4 .选择操作 selection :对父代2个体f1,f2和子代2个体f3,f4 进行选择，通过编码操作确定具有最优解的2个个体，成为新一代f1和f2 。如此，通过多次编码和解码随机产生一定数量的个体，选取2个最佳个体进行交叉变换操作，产生2个新个体，然后对 4个个体进行选择，产生下一代，如果某时刻通过解码 操作得出最优解 所有解的下限，这里是75周期），那么算法结束，否则循环进行，直至预先给定的循环次数达到为止，以最后得到的最优解作为最终最优解。七.遗传算法模拟 采用MATLA工具编程）主程序如下： 子程序见略）% 本程序为主程序，调用以下各分支程序task= 'Welcome!

17、Wait a momentplease!-Writer:f1=zeros(1,35>。f2=zeros(1,35> 。while f1=f2。%minminmax1,s1=chushijie(N>。%f1=s1。 minminmax1,%minminmax2,s2=chushijie(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,f

18、3,f4>。%f1。f2。孙卓明，信息014',此步避免初始染色体f1,f2相同，导致以下死循环种群初始化；基于操作的编码策略；活动化解码算法。chushijie（N 参数N为初始种群数选取的第一个初始个体再次种群初始化选取的第二个初始个体进行M次遗传操作 交叉-变异-选择交叉变化 循环交叉操作，cycle crossover CX ）,选取生成交叉后的“染色体”，并进行变异选择选择：对父代f1,f2和子代f3,f4进行解码，得出2个 较优个体，成为下一代的父代minmaxf1,a1,b1=tongbujinzhan(f1> 。% 求该时刻个体 f1的最优时间(因为f1优于

19、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 minmin

20、max_last>=80&&minminmax_last<90。 task='Finish!' , end。if minminmax_last<80 。 task='Finish! Successful!', end。八遗传算法模拟结果首先给出最优方案：在进行某次n=100,m=200的操作后得到模拟最优结果75周期时间:mi nminm ax1 =83mi nminm ax2 =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

21、3 2 2 5 1 1<f1为各工件优先选择顺序排列，即“染色体”)a1 = 5 35 :396400000<a1,b1为四台机器空闲周期段）15 24000000017 53 650000000 0 0 000000b1 =11 3842650000020 35000000018 54 680000000 0 0 000000min mi nmax=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值情况下数据优化

22、过程以及时间上的比较：（表五NNM第次运仃第二次运行第三次运行第四次运行第五次运行平均运行时间11 :1104-114- 98P 98-105- 9392-93- 92：100-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- 7710

23、3-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-

24、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的增大所产生的优化效果

25、明显好于 N增大产生的优化效果M 从1-10-100-1000-10000 的变化使最优解有从 9*-8*-7*的变化规律,N的1-10-100的变化则不明显。因此相对于随机取解，经过遗传算法优化之后效果是显著的 另外对采用遗传算法前后模拟所得数据进行比较：第一次第二次第三次第四次第五次均值平均时间N=1000 ,M=0787981807925(S>79. 4N=1,N=1,M=1000807577768278.0P 8.5(S> :（表六由上表看来，虽然在均值方面相差不显著，但是时间上采用遗传算法之后 节约了约三分之二的运行时间，效率显而易见。九模型优缺点及改进模型优点，采用遗传

26、算法可对一个理论上无法求尽的NP问题以较有效方法在较短时间内得到较精确解。缺点，采用遗传算法还不全面，只是一个简单模型，未考虑收敛性，适配值等，对参数设置与最优解关系研究还不够深入。模型本身还具有漏动，仍需改进，较好设想为采用和模拟退火算法的混 合遗传算法，因为时间紧迫，在此就不再深入给出模型及分析了。参考文献:1 车间调度与遗传算法王凌清华大学出版社2 数值计算的算法与分析 张可村 赵英良 科学出版社3. Permutation Based GAs and Ordered GreedPeter G. Anderson,4. MATLAB6.0与科学计算王沫然电子工业出版社5. C程序设计 第

27、二版）潭浩强清华大学出版社信息014孙卓明2003年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 41 2 1 0 0 0。2 3 4 1 4 3 0 0。4 2 3 4 1 34 0。1 2 1 3 4 1 3 1 。minminmax=200。for d=1:n。s=0。% 编码程序：基于操作的编码策略k=1。for t=1:35。I=randin

28、t(1,1,1,6>。while Jm(I,1>=0。I=randint(1,1,1,6>。end 。s(k>=l ok=k+1oX=1owhile x<=7。Jm(l,x>=Jm(l,x+1>ox=x+1oend oJm(I,8>=0oend oJm=3 1 2 3 4 0 0 0 o 1 4 2 3 0 0 0 0 o 3 41 2 1 0 0 0 o 2 3 4 1 4 3 0 0 o 4 2 3 4 1 34 0 o 1 2 1 3 4 1 3 1 oT=8 2 4 24 6 0 0 0 o 4 5 3 4 0 0 0 0 o 3 715

29、 20 8 0 0 0 o 7 6 21 1 16 3 0 0 o 10 4 8 412610o 1473525% 解码程序：活动化解码算法 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(f

30、lag(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>。y=x:8 。a(q,y>=a(q,y+1>b(q,y>=b(q,y+1> 。endz=1 。elseifflag(s(i>><=a(q,x>&&a(q,x>+t<b(q,x> a(q,x>=a(q,x>+

31、t。 flag(s(i>>=a(q,x> 。 z=1elseifflag(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。elseifflag(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>

32、=b(q,x>。 b(q,x>=flag(s(i>>a(q,x+1>=flag(s(i>>+tflag(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。flag_(q>=flag_(q>+t。elseif flag(s(i>>>flag_(q>。for x=1:9。if a(q,x>=0&&v=0。a(q,x&

33、gt;=flag_(q>b(q,x>=flag(s(i>> 。 v=1。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。for ifminminmax>minmax% 得出初始最优解 minminmax=minmax 。 ss=s

34、。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 。e

35、nd 。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 。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>&&

36、z=1 。return 。end 。end 。end。子程序三： <变异选择，形成子代)functionf3,f4=jiaocha_bianyi(f1,f2,D> % 生成交叉后的“染色体” , 并进行变异选择 g2=f1 。 g1=f2 。for i=1:34 。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>。d

37、2=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。子程序四：<四者中选取最优二个 体)functionf1,f2

38、=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

39、&&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 。elseifmin3<=min1&&min3<=

40、min4。g=f3 。elseifmin4<=min1&&min4<=min3。g=f4 。end 。elseif min3<=min1&&min3<=min2&&min3<=min4 。h=f3 。 if min1<=min2&&min1<=min4 。 g=f1 。elseifg=f2 。elseifg=f4 。endelseif min4<=min1&&min4<=min2&&min4<=min3 。h=f4 。 if min1<

41、;=min2&&min1<=min3g=f1 。elseifmin2<=min1&&min2<=min3min2<=min1&&min2<=min4min4<=min1&&min4<=min2elseifmin3<=min1&&min3<=min2g=f2 。g=f3elseifend 。end 。end。f1=h 。 f2=g 。while f1=f2 。minminmax3,s1=chushijie(30> 。f2=s1 。end。子程序五： <

42、循环之中，同步求解)functionminmaxf1,a1,b1=tongbujinzhan(f1>% 求该时刻个体 f1 的最优时间Jm=3 1 2 3 4 0 0 0。1 4 2 3 0 0 0 0。3 41 2 1 0 0 0。2 3 4 1 4 3 0 0。4 2 3 4 1 34 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 715 20 8 0 0 0 。 7 6 21 1 16 3 0 0 。 10 4 8 412 6 1 0 。 1 4 7 3 5 2 5 8 。s=f1。% 解码程序：活动化解码算法for i=