编号：
第六届计算机仿真大赛
参赛作品
题号:加工调度问题
组别：高年级组
作者：厚玉伟
学院：光电工程
联系电话：187********
计算机仿真大赛组委会
2012年 05月 01日
生产调度问题及其优化算法
背景及摘要
这是一个典型的Job-Shop动态排序问题。目前调度问题的理论研究成果主要集中在以Job-Shop问题为代表的基于最小化完工时间的调度问题上。一个复杂的制造系统不仅可能涉及到成千上万道车间调度工序，而且工序的变更又可能
导致相当大的调度规模。解空间容量巨大，N个工件、M台机器的问题包含M
(
N)!
种排列。由于问题的连环嵌套性，使得用图解方法也变得不切实际。传统的运筹学方法，即便在单目标优化的静态调度问题中也难以有效应用。
本文给出三个模型。首先通过贪婪法手工求得本问题最优解，既而通过编解码程序随机模拟优化方案得出最优解。最后采用现代进化算法中有代表性发展优势的遗传算法。文章有针对性地选取遗传算法关键环节的适宜方法，采用MATLAB 软件实现算法模拟，得出优化方案，并与计算机随机模拟结果加以比较显示出遗传算法之优化效果。对车间调度系列问题的有效解决具有一定参考和借鉴价值。
二．模型假设
1．每一时刻，每台机器只能加工一个工件，且每个工件只能被一台机器所加工 ，同时加工过程为不间断；
2．所有机器均同时开工，且工件从机器I 到机器J 的转移过程时间损耗不计； 3．各工件必须按工艺路线以指定的次序在机器上加工多次； 4．操作允许等待，即前一操作未完成，则后面的操作需要等待，可用资源有限。
三．符号说明及初始数据表达分析
i J - 第i 个工件 （i=1…6）
M J - 机器顺序阵 ）（j i J M
,表示i 工件的第 j 个操作的机器号
j M - 第j 台机器 （j=1…4）
J M - 工件排列阵 ),(j i M J 表
i 机器上第j 次加工的工件号
T - 加工时间阵 ),(j i T 为i 工件的第 j 个操作的时间周期
C - 整个任务完成时间 整理数据后得到：
M J =[ C A B C D 0 0 0 ] T = [ 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 ] 上述二阵直接从题目得出，而J M 则是我们要求的。
关于工件的加工时间表：(表二)
产品/工件（i ）:
1 2 3 4 5 6 总计 i J 总净加工时间（周期） 44 16 53 54 45 35 247 i J 加工工序总数（个）
5
4
5
6
7
8
35
关于机器的加工时间表：(表三)
机器/设备(j):
A B C D 总计 j M 总净加工时间 60 42 70 75 247 j M 加工操作次数
10
6
10
9
35
分析：
由于各产品总净加工时间和各机器总净加工时间之中最大值为 75，而总
计为247，那么 总时间 C 介于[75，247]。同时各工件加工繁杂程度不一，各机器的任务量也有轻重之别。合理的调度排序是对于节省时间和资源是必要的。
希望最优化答案是75，这样达到最小值，如果答案是75，那么意味着机器D 不间断工作,直至全部加工任务完成。
四．贪婪法快速求解
如果按照一定规则排序，当多个工件出现“抢占”同一机器的局面的时候,我们可以制定如下的工序安排规则:
1. 优先选择总剩余时间或总剩余操作较多的工件。（如果出现总剩余加工时间多者总剩余操作数反而较少的情况时,按照程度具体情况具体分析）。
2. 机器方面来说,尽量避免等待空闲时间，优先考虑剩余净加工时间或者剩余加工总次数较多的机器,尤其是机器 D ,即倘若能够使机器D 不间断工作且其他机器完工时间均不多余75时,那么就可以得到最优解 。
首先按照最优化时间为75的设想避免D 出现等待，排序后得到升以下具体排列顺序。
各机器承担任务表为(其中粗体字为对应工件产品号，括号内为对应时间周期段)：
操作1 操作2 操作3 操作4 操作5 操作6 操作7 操作8 操作9 操作10 A 6 (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) B 4
(1-7)
6 (8-11) 5 (12-15) 1 (16-19) 3 (36-55) 2 (56-58)
C 3
(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)
D
5
(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)
(表四)
10
37
17
84421
644
8
4
25
375242015163166
1
5
124
2^^^
^
38
8
010203040
50
60
70
80
D 机器
C 机器B 机器A 机器^
(图一)
上图为加工周期图（甘特图），标注数字为相应操作的周期，完工时间为第75周期。
五．计算机随机模拟（编程）
1．编码：
随机产生生产的工序操作优先顺序，进行编码，如：K=[ 4 3 5 6 6 2
3 1 4
1 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操作其第二步工序，依次
进行。如果前后互相不冲突，则可同时在不同机器上操作。
10
多种！
通过排列组合得出，总共有类似K的排列序列 223
当然，这其中只对应解 [75，247]，意味着有大量排列序列对应同一加工
方案，而大量加工方案又对应同一时间解。
2．解码：
即对编码进行翻译，产生具体可操作工序安排方案，这里采用活动化
J（2，i），且在机器A上进行）解码算法。例如工件2第i步操作（记为
M
J 被安排在工件3第j步操作（记为JM（3,j））后面进行，那么如果安排好
M
J（2，i）在工件2已经排序好的操作之后进行，那么操（3,j）后，只要
M
J（2，i）可插入到机器A处最前可安置的时间段进行。
作
M
在这里，一个编码序列对应一个加工方案，而一个加工方案可对应一个或多个编码序列，这就是二者之关系。
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次）
结论：如果想将22310?中排序序列以平均出现一次的可能性进行模拟，
即运行22310?次，计算机需运行将近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，这样就确定了以上为不变的染色体，其余位置的染色体互换位置，最后得到X': [3 2 5 4 1 6 7 8 9], Y': [9 4 6 8
7 3 5 2 1],实现交叉变换。
3．变异选择（mutation）
采用互换操作（SWAP），，即随机交换染色体中两不同基因的位置。如上面的染色体为：X': [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! ',
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_last<90; task='Finish!' , end;
if minminmax_last<80; 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 0
b1 =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 0
minminmax = 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值情况下数据优化过程以及时间上的比较: ( 表五 )
N N M 第一次运行第二次运行第三次运行第四次运行第五次运行平均运行时间1 1 1 104-114-9898-105-9392-93-92100-132-9586-86-84/ 1 1 10 106-97-86108-100-89102-87-8799-90-9088-104-84/ 1 1 100 94-81-8181-102-7891-105-91101-84-8090-101-90/ 1 1 1000 107-100-7892-101-76101-100-8288-97-8691-93-878.5(s) 1 1 10000 88-105-77103-81-7789-99-84107-104-7893-105-7880(s) 10 10 10 90-108-90104-91-83104-100-9395-98-87105-106-87/ 10 10 100 98-96-9693-99-9088-90-80105-92-8091-95-85/ 10 10 1000 101-96-7891-89-8096-104-87105-105-8488-99-789.5(s) 10 10 10000 99-92-7797-95-7596-104-7689-99-7691-101-7590(s) 100 100 100 95-100-8698-90-80104-99-7893-88-8192-99-80/ 100 100 1000 109-98-8591-100-82100-99-77114-101-8496-110-7611(s) 100 100 10000 96-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 81 80 79 79．4 25(S)
N=1,N=1,M=1000 80 75 77 76 82 78.0 8.5(S) (表六)
由上表看来,虽然在均值方面相差不显著,但是时间上采用遗传算法之后节约了约三分之二的运行时间,效率显而易见。
九．模型优缺点及改进
模型优点，采用遗传算法可对一个理论上无法求尽的NP问题以较有效方法在较短时间内得到较精确解。
缺点，采用遗传算法还不全面，只是一个简单模型，未考虑收敛性,适配值等，对参数设置与最优解关系研究还不够深入。 模型本身还具有漏动，仍需改进，较好设想为采用和模拟退火算法的混合遗传算法，由于时间紧迫，在此就不再深入给出模型及分析了。
[参考文献]：
1．车间调度与遗传算法 王凌 清华大学出版社 2．数值计算的算法与分析 张可村 赵英良 科学出版社
3．Permutation Based GAs and Ordered Greed Peter G. Anderson, 4．MATLAB6.0 与科学计算 王沫然 电子工业出版社 5．C 程序设计（第二版） 潭浩强 清华大学出版社
信息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 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)+t
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; 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;
end;
end;
end;
子程序三：（变异选择，形成子代）function
[f3,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]);
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)+t 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)=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 minmaxf1 minmaxf1=flag_(q); end; end; a1=a; b1=b;
相关主题
文本预览