《数学建模与计算》
生产调度问题—遗传算法
背景及摘要
这是一个典型的Job-Shop动态排序问题。目前调度问题的理论研究成果主要集中在以Job-Shop问题为代表的基于最小化完工时间的调度问题上。一个复杂的制造系统不仅可能涉及到成千上万道车间调度工序,而且工序的变更又可能导致相当大的调度规模。解空间容量巨大,N个工件、M台机器的问题包含种排列。由于问题的连环嵌套性,使得用图解方法也变得不切实际。传统的运筹学方法,即便在单目标优化的静态调度问题中也难以有效应用。
本文给出三个模型。首先通过贪婪法手工求得本问题最优解,既而通过编解码程序随机模拟优化方案得出最优解。最后采用现代进化算法中有代表性发展优势的遗传算法。文章有针对性地选取遗传算法关键环节的适宜方法,采用MATLAB软件实现算法模拟,得出优化方案,并与计算机随机模拟结果加以比较显示出遗传算法之优化效果。 对车间调度系列问题的有效解决具有一定参考和借鉴价值。
一.问题重述
某重型机械厂产品都是单件性的,其中有一车间共有A,B,C,D四种不同设备,现接受6件产品的加工任务,每件产品接受的程序在指定的设备上加工,其工序与加工周期如下表:(S-设备号、T-周期)
工序 产品 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | ||||||||
S | T | S | T | S | T | S | T | S | T | S | T | S | T | S | T | |
1 | C | 8 | A | 2 | B | 4 | C | 24 | D | 6 | ||||||
2 | A | 4 | D | 5 | B | 3 | C | 4 | ||||||||
3 | C | 3 | D | 7 | A | 15 | B | 20 | A | 8 | ||||||
4 | B | 7 | C | 6 | D | 21 | A | 1 | D | 16 | C | 3 | ||||
5 | D | 10 | B | 4 | C | 8 | D | 4 | A | 12 | C | 6 | D | 1 | ||
6 | A | 1 | B | 4 | A | 7 | C | 3 | D | 5 | A | 2 | C | 5 | A | 8 |
( 表一 )
条件: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=1…6)
- 机器顺序阵 表示i工件的第 j个操作的机器号
- 第j台机器 (j=1…4)
- 工件排列阵 表示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): | 1 | 2 | 3 | 4 | 5 | 6 | 总计 |
总净加工时间(周期) | 44 | 16 | 53 | 54 | 45 | 35 | 247 |
加工工序总数(个) | 5 | 4 | 5 | 6 | 7 | 8 | 35 |
关于机器的加工时间表:(表三)
机器/设备(j): | A | B | C | D | 总计 |
总净加工时间 | 60 | 42 | 70 | 75 | 247 |
加工操作次数 | 10 | 6 | 10 | 9 | 35 |
分析:
由于各产品总净加工时间和各机器总净加工时间之中最大值为 75,而总计为247,那么 总时间 C 介于[75,247]。同时各工件加工繁杂程度不一,各机器的任务量也有轻重之别。合理的调度排序是对于节省时间和资源是必要的。
希望最优化答案是75,这样达到最小值,如果答案是75,那么意味着机器D不间断工作,直至全部加工任务完成。
六.遗传算法模型建立和步骤解法
遗传算法(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.编码
随机产生生产的工序操作优先顺序,进行编码,如: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操作其第二步工序,依次进行。如果前后互相不冲突,则可同时在不同机器上操作。
通过排列组合得出,总共有类似K的排列序列 2多种!
当然,这其中只对应解 [75,247],意味着有大量排列序列对应同一加工方案,而大量加工方案又对应同一时间解。
2.解码
即对编码进行翻译,产生具体可操作工序安排方案,这里采用活动化解码算法。例如工件2第i步操作(记为(2,i),且在机器A上进行)被安排在工件3第j步操作(记为JM(3,j))后面进行,那么如果安排好
(3,j)后,只要(2,i)在工件2已经排序好的操作之后进行,那么操
作(2,i)可插入到机器A处最前可安置的时间段进行。
在这里,一个编码序列对应一个加工方案,而一个加工方案可对应一个或多个编码序列,这就是二者之关系。
3.交叉变换(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],实现交叉变换。
4.变异选择(mutation)
采用互换操作(SWAP),,即随机交换染色体中两不同基因的位置。如上面的染色体为:: [3 2 5 4 1 6 7 8 9] 。随机产生变换位置号,如产生随机数3和5,那么交换数字后得到染色体: [3 2 1 4 5 6 7 8 9], 变异概率取0.1 。
5.选择操作(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_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-98 | 98-105-93 | 92-93-92 | 100-132-95 | 86-86-84 | / |
1 | 1 | 10 | 106-97-86 | 108-100-89 | 102-87-87 | 99-90-90 | 88-104-84 | / |
1 | 1 | 100 | 94-81-81 | 81-102-78 | 91-105-91 | 101-84-80 | 90-101-90 | / |
1 | 1 | 1000 | 107-100-78 | 92-101-76 | 101-100-82 | 88-97-86 | 91-93-87 | 8.5(s) |
1 | 1 | 10000 | 88-105-77 | 103-81-77 | 89-99-84 | 107-104-78 | 93-105-78 | 80(s) |
10 | 10 | 10 | 90-108-90 | 104-91-83 | 104-100-93 | 95-98-87 | 105-106-87 | / |
10 | 10 | 100 | 98-96-96 | 93-99-90 | 88-90-80 | 105-92-80 | 91-95-85 | / |
10 | 10 | 1000 | 101-96-78 | 91-89-80 | 96-104-87 | 105-105-84 | 88-99-78 | 9.5(s) |
10 | 10 | 10000 | 99-92-77 | 97-95-75 | 96-104-76 | 89-99-76 | 91-101-75 | 90(s) |
100 | 100 | 100 | 95-100-86 | 98-90-80 | 104-99-78 | 93-88-81 | 92-99-80 | / |
100 | 100 | 1000 | 109-98-85 | 91-100-82 | 100-99-77 | 114-101-84 | 96-110-76 | 11(s) |
100 | 100 | 10000 | 96-101-78 | 101-86-76 | 101-97-80 | 99-110-76 | 99-111-77 | 100(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) |
(表六)
由上表看来,虽然在均值方面相差不显著,但是时间上采用遗传算法之后节约了约三分之二的运行时间,效率显而易见。
[参考文献]:
1. 车间调度与遗传算法 王凌 清华大学出版社
2.数值计算的算法与分析 张可村 赵英良 科学出版社
3.Permutation Based GAs and Ordered Greed Peter G. Anderson,
4.MATLAB6.0 与科学计算 王沫然 电子工业出版社
5.C程序设计(第二版) 潭浩强 清华大学出版社
附录:
子程序一:(种群初始化,得较优个体)
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
elseif flag(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;
elseif flag(s(i))>a(q,x)&&a(q,x)+t
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;
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;
minmax=0;
for q=1:4;
if minmax
minmax=flag_(q);
end;
end;
if minminmax>minmax ; % 得出初始最优解
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;
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
elseif flag(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 ;
elseif flag(s(i))>a(q,x)&&a(q,x)+t
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;
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;
¥29.8
¥9.9
¥59.8