加工调度问题计算机仿真模型.docx
《加工调度问题计算机仿真模型.docx》由会员分享,可在线阅读,更多相关《加工调度问题计算机仿真模型.docx(13页珍藏版)》请在冰点文库上搜索。
加工调度问题计算机仿真模型
编号:
第六届计算机仿真大赛
参赛作品
题号:
4
组别:
高年级
作者:
XXX
学院:
XXX
联系电话:
XXX
有关加工调度问题的计算机仿真模型
摘要
本文讨论在工业生产中,利用建立模型,优化多个零件在多台机器上进行加工的顺序安排,以提高设备利用率和生产效率的调度问题。
主要建立的模型如下:
流水线调度优化模型:
通过利用约翰逊贝尔曼法则找出最优结果排序。
首先写出约翰逊贝尔曼法则在多个机器(m>2)的算法,根据算法利用Matlab软件进行计算机仿真,得出最优加工顺序的结果(见正文第9页)。
为了形象描述问题并得到本系统的流程图和核心程序的流程图,利用甘特图模型进行仿真,最终形象的表示机器设备的生产进度。
关键字:
加工顺序最优Matlab甘特图约翰逊贝尔曼算法
一、问题重述与分析
1.1问题的重述
工厂中,有n个不同的配件需要生产,每个配件都必须由m台不同的机器进行顺序加工处理,配件i在机器j上所需的处理时间为t(i,j)。
现约定未完工前不允许中断处理,配件不能拆分成更小配件。
要求给出一种配件调度方案,使所给的n个配件在尽可能短的时间内处理完成。
1.2问题的分析
此问题的求解主要依靠运用运筹学相关理论学科,解决加工顺序的最优安排以达到零件生产效率提高的工业要求,可以利用约翰逊贝尔曼法则找出最优结果排序,利用matlab软件进行计算机仿真,并画出形象表达生产进度的甘特图。
二、符号说明
变量
含义
D1
表示第D1种分组
No(n,1)
表示编号
t2(n,2)
t2用来存放2台虚拟机器存放的时间t2(:
1)表示第一台
A(n,m-1)
用来存放m-1种分组方式下,按大小排序后的t2(:
1)
B(n,m-1)
用来存放m-1种分组方式下,按大小排序后的t2(:
2)
index1(n,m-1)
用来存放m-1种分组方式下,按大小排序后的t2(:
1)零件序号
index2(n,m-1)
用来存放m-1种分组方式下,按大小排序后的t2(:
2)零件序号
newsort(n,m-1)
用来存放m-1种分组方式下,按大小排序后的零件序号,即加工顺序
T1(n,m,m-1)
T1(:
:
i)表示根据J&B法则第i中分法下的加工顺序后的加工时间表
T1(n,m,m-1)
T2(:
:
i)表示根据J&B法则第i中分法下的加工顺序后的完工时间表
T(1,m-1)
表示m-1种分组方式下的最短工期数组
No_sort(1,n)
m-1中分法下的T中元素最小最优解加工零件的排序
Tmin(n,m)
m-1中分法下的T中元素最小最优解加工顺序后的完工时间表
t1(n,m)
对应最优排序后的加工时间矩阵
j0
表示靠前加工零件的个数
j1
表示靠后加工零件的个数
i1
i1,i2分别表示每轮最小值A(:
D1)、B(:
D1)下标(共n次,确定newsort(:
D1)的零件排序)
i2
result
result=[No,No_sort,Tmin]
输出结果说明第一列元素表示加工顺序,第二列表示加工零件编号,第三列到以后为:
每个零件在不同机器上的完工时间矩阵
三、调度问题模型的建立
3.1两个工作条件的给出:
n个工件在m台机器上的加工顺序相同。
工件在机器上的加工时间是给定的(时间矩阵t(n,m),t(i,j)表示i零件在机器j上加工时间)。
问题的目标是求n个工件在每合机器上的最大完工时间等于最大流程时间。
这种流水线调度问题要在满足以下两个约束条件的前提下,使得加工完所有的工件所花的时间尽可能地少:
1、工件约束
每个工件在每台机器上恰好加工一次,每个工件在各机器上加工顺序相同。
不失一般性,假设各工件按机器1至m的顺序进行加工。
各工件在各机器上的加工时间已知。
2、机器约束
每台机器在任何时刻至多加工一个工件,每台机器加工的各工件的顺序相同。
3.2工件加工顺序的原则:
置换流水线调度问题实质是如何调整加工工件的序列,提高机器的利用率的问题,即在同一时刻正在加工的机器数越多,机器利用率越大口根据该原则,我们根据下面规则安排:
1、在前面机器加工时间较短、后面机器加工时间较长的工件,安排在序列前。
这样可以使得后面的机器尽快参加工作,并且后面的机器不需要作空等待,
2、机器加工时间较为平均且加工时间较长的工件,安排在序列的中部。
这样可以使得各个机器在中期的时候都能得到运作。
3、前面加工时间较长,后面加工时间较短的工件按排在序列尾部。
这样使得前面的机器能“延迟”完工,后面的机器尽快完工。
3.3算法的描述【1】【2】:
我们采用约翰逊-贝尔曼法则(Johnson-Bellmanrule,一下简称J&B)
1、N种零件在两台机器上加工(M1,M2),根据J&B法则,最短工期加工顺序,方法如下:
(1)检索t(:
1),t(:
2)(表示各零件分别在M1,M2上加工时间)的各种数据,找出其中最小值
(2)上述最小值如果属于第一列,则该零件应靠前加工,相反,若在第二列则靠后加工
2、将J&B法则推广到m台机器情况,把m台机器分成第1、第2两组,每组看成一个机器,分法如下(该步为2台虚拟机器假设过程)
组号(D1)
第一组(加工时间t2(:
1))
第二组(加工时间t2(:
2))
1
M1
M2+M3+…+Mm
2
M1+M2
M3+M4+…+Mm
…
…
…
…
…
…
m-1
M1+M2+…+Mm-1
Mm
m台机器共有m-1种分法,每种分法均按照J&B法则找出最短加工期的加工顺序。
Newsort(:
D1)表示第D1种分组方式下的零件序号排序(此部分用子程序I完成)
3、在D1中分组方式下生成的加工时间矩阵T1(:
:
D1)和完工时间矩阵T2(:
:
D1)
T2(i,:
D1),T1(i,:
D1)中i等于newsort(i,D1)
T2(n,m,D1)表示第D1种分组方式下的最短工期
T表示第m-1种分组方式下的最短工期数组
4、算出T2后,就可以找出m-1种分组方式下的最优解了。
3.4问题的求解和结果
算法流程图如下:
根据上述利用软件进行仿真,最终运行结果为:
>>请输入加工时间矩阵
t(i,j)表示第i个零件在机器j上的加工时间:
[1487;2544;6563;7431;1468]
result=
15151119
21291926
324142330
4310192933
5417233234
输出结果说明第一列元素表示加工顺序,
第二列表示加工零件编号,第三列到以后为:
每个零件在不同机器上的完工时间矩阵
甘特图是一种用来形象的表示机器生产进度(加工顺序的)图形。
此问题中求解出的甘特图如下:
四、参考文献
[1]朱德通著,《最优化模型与实验》[M],同济大学出版社,2003.6
[2]宋存利著,《求解多工艺路线车间调度问题的禁忌-遗传算法》[J],大连交通大学出版社,2008.4
[3]陈国良著,《遗传算法及其应用》[M],人民邮电出版社,2000.4
[4]董立华高秀莲著,《数学建模与数学实验》[M],天津教育出版社,2009.5
五、附录
有关工件加工顺序的程序:
clear;
clf;
t=input('请输入加工时间矩阵\nt(i,j)表示第i个零件在机器j上的加工时间:
\n');
[nm]=size(t);%n表示加工零件数,m表示机器数
t2=zeros(n,2);%t2用来存放两台虚拟机器的时间
A=zeros(n,m-1);%AB分别存放两台虚拟机器的时间排序后的时间,m-1为根据约翰逊贝尔曼法则(Johnson-Bellmanrule,一下简称J&B),当m>2,可以分为m-1中情况
B=zeros(n,m-1);%A(:
i)表示第i中分法下的排序方法
index1=zeros(n,m-1);
index2=zeros(n,m-1);%index1index2分别存放两台虚拟机器的时间排序后对应的零件序号
newsort=zeros(n,m-1);%newsort(:
i)表示根据J&B法则第i中分法下的加工顺序
T1=zeros(n,m,m-1);%T1(:
:
i)表示根据J&B法则第i中分法下的加工顺序后的时间表
T2=zeros(n,m,m-1);%T2(:
:
i)表示根据J&B法则第i中分法下的加工顺序后的最短工期表
T=zeros(1,m-1);
%Tmin(n,m)加工完成时间矩阵,表示i零件在j机器上完成后的总时间
No_sort=zeros(1,n);%No_sort为最后根据m-1中分法下的最后的最优解
fori=1:
n%编号
No(i,1)=i;
end
%J&B法则模拟两个虚拟机器
forD1=1:
m-1
fori=1:
D1
t2(:
1)=t2(:
1)+t(:
i);%机器1
end
fori=D1:
m
t2(:
2)=t2(:
2)+t(:
i);%机器2
end
[A(:
D1),index1(:
D1)]=sort(t2(:
1));%A(:
D1)中保存第D1分法中机器1中按从小到大的排序值,index1(:
D1)对应的零件下标
[B(:
D1),index2(:
D1)]=sort(t2(:
2));%B(:
D1)中保存第D1分法中机器2中按从小到大的排序值,index2(:
D1)对应的零件下标
end
forD1=1:
m-1
%求m-1中两个虚拟机的排序情况
%根据J&B法则第D1中分法下的加工顺序
j0=1;
j1=1;
fori=1:
n
%思想为:
一组中有n个零件排序,t2(:
1)(机器1中时间值),t2(:
2)(机器1中时间值)
%A(:
D1)B(:
D1)分别将机器1中时间值、机器2中时间值按从小到大排序
%判定t2中最小值属于机器(1,2),每次从A(:
D1)最小与B(:
D1)最小判定
%若newsort(:
D1)对应下标确定,则将inde1(:
D1),index2(:
D1)对应下标致零,确保下次不参与最小
%值比较
i1=1;%i1,i2分别表示每轮最小值A(:
D1)、B(:
D1)下标(共n次,确定newsort(:
D1)的零件排序)
i2=1;%每次均从第一个最小值开始判定
whileindex1(i1,D1)==0%如果最小值下标为零,已经排位,不在比较,i1++;i2++,向下一位走
i1=i1+1;
end
whileindex2(i2,D1)==0
i2=i2+1;
end
ifA(i1,D1)<=B(i2,D1)%如果最小值产生在A(:
D1),即机器1,则先加工
newsort(j0,D1)=index1(i1,D1);
j0=j0+1;%说明靠前位置下移
forj=1:
n
ifindex2(j,D1)==index1(i1,D1)%遍历index2,=0说明该工件已经加入排序中
index2(j,D1)=0;
index1(i1,D1)=0;%加入排位后,将下标致零
end
end
else%如果最小值产生在B(:
D1),即机器2,则最后加工
newsort(n-j1+1,D1)=index2(i2,D1);
j1=j1+1;
forj=1:
n
ifindex1(j,D1)==index2(i2,D1)%遍历index1,=0说明该工件已经加入排序中
index1(j,D1)=0;
index2(i2,D1)=0;%加入排位后,将下标致零
end
end
end
end
end
forD1=1:
m-1
fori=1:
n
T1(i,:
D1)=t(newsort(i,D1),:
);%排序后的时间矩阵
end
fori=1:
n%为T2第一列赋值
forj=1:
i
T2(i,1,D1)=T2(i,1,D1)+T1(j,1,D1);
end
end
fori=2:
m%为T2第一行赋值
forj=1:
i
T2(1,i,D1)=T2(1,i,D1)+T1(1,j,D1);
end
end
fori=2:
n%为i>1,j>1赋值
forj=2:
m
T2(i,j,D1)=T1(i,j,D1)+max(T2(i-1,j,D1),T2(i,j-1,D1));
%实际含义是:
零件i在机器j上完成的时间为零件i在机器j的加工时间+
%零件i在j-1机器(满足要求:
顺序加工)和上一个零件加工完成中的最大一个(每个机器一次只能加工一个零件)
end
end
T(D1)=T2(n,m,D1);%将m-1种结果产生的最小时间赋值给T
end
%对T排序,得到m-1中结果中的最优解
[tmin,index0]=sort(T);
Tmin=T2(:
:
index0
(1));%最优解中加工完成时间矩阵(排序后的,不同与t中零件排序)
No_sort=newsort(:
index0
(1));%Tmin每行对应的的零件
fori=1:
n
t1(i,:
)=t(No_sort(i),:
);%对应最优排序后的加工时间矩阵
end
result=[No,No_sort,Tmin]
fprintf('输出结果说明第一列元素表示加工顺序,\n第二列表示加工零件编号,第三列到以后为:
\n每个零件在不同机器上的完工时间矩阵');
%画出加工零件的甘特图
%变量说明以及输出说明
%每一行表示一个零件加工过程
%在线条上的数字表示第几个机器
%图片开始的数字为零件的编号
%line();画出i零件在j机器上的加工情况
%text();标出机器代号
gridon;
axis([-4Tmin(n,m)+20n+1]);%限制坐标范围
fori=1:
n
k=No_sort(i);
text(-2,i,int2str(k));
forj=1:
m
%画出零件编号
ifi==1%第一个加工零件
ifj==1%第一个机器加工情况
line([0,Tmin(i,j)],[ii]);
text(Tmin(i,j)/2,i,int2str(j));
else
ifmod(j,2)==0%使同一个零件在连续两台机器上加工的情况显示结果不同,便于观察
line([Tmin(i,j-1),Tmin(i,j)],[ii],'LineWidth',3);
text((Tmin(i,j)+Tmin(i,j-1))/2,i,int2str(j));
else
line([Tmin(i,j-1),Tmin(i,j)],[ii]);
text((Tmin(i,j)+Tmin(i,j-1))/2,i,int2str(j));
end
end
else
ifj==1
x0=Tmin(i,j)-Tmin(i-1,j);%i零件在j机器上的加工时间
line([Tmin(i,j)-x0,Tmin(i,j)],[ii]);
text((Tmin(i,j)*2-x0)/2,i,int2str(j));
else
ifmod(j,2)==0
x0=Tmin(i,j)-max(Tmin(i-1,j),Tmin(i,j-1));
line([Tmin(i,j)-x0,Tmin(i,j)],[ii],'LineWidth',3);
text((Tmin(i,j)*2-x0)/2,i,int2str(j));
else
x0=Tmin(i,j)-max(Tmin(i-1,j),Tmin(i,j-1));
line([Tmin(i,j)-x0,Tmin(i,j)],[ii]);
text((Tmin(i,j)*2-x0)/2,i,int2str(j));
end
end
end
end
end