加工调度问题的计算机仿真模型.doc

编号：

第六届计算机仿真大赛
参赛作品

题号: 4
组别： 高年级
作者： XXX
学院： XXX
联系电话： XXX

有关加工调度问题的计算机仿真模型

摘要
本文讨论在工业生产中，利用建立模型，优化多个零件在多台机器上进行加工的顺序安排，以提高设备利用率和生产效率的调度问题。主要建立的模型如下：
流水线调度优化模型：通过利用约翰逊贝尔曼法则找出最优结果排序。首先写出约翰逊贝尔曼法则在多个机器（m>2）的算法，根据算法利用Matlab软件进行计算机仿真，得出最优加工顺序的结果（见正文第9页）。为了形象描述问题并得到本系统的流程图和核心程序的流程图，利用甘特图模型进行仿真，最终形象的表示机器设备的生产进度。

关键字：加工顺序最优 Matlab 甘特图 约翰逊贝尔曼算法

目录

一、问题重述与分析 2
1.1问题的重述 2
1.2问题的分析 2
二、符号说明 2
三、调度问题模型的建立 3
3.1 两个工作条件的给出 3
3.3算法的描述 4
3.4问题的求解和结果 5
四、参考文献 9
五、附录 9

一、 问题重述与分析
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-Bellman rule，一下简称 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问题的求解和结果
工作流程
否
子
程

序
I
开始
D1>m-1 ?
第D1种分组方式下2个虚拟机器，对应加工时间t2
对加工零件时间排序：t2(:,1)—A(:,D1) 下标—index1
t2(:,2)—B(:,D1) 下标—index2
2台机器下确定零件加工顺序—newsort(:,D1)
按上加工顺序的
时间矩阵—T1(:,:,D1)
按约定算法生成按上加工顺序的
完工时间矩阵-- T1(:,:,D1)
将该分组方式下产生的最短工期放入矩阵—T
D1=D1+1
输入原始数据t

是
对T进行排序，
sort(T)—tmin
T下标—index0
最优解：
最优零件排序 --No_sort
最优完工时间矩阵—Tmin
最优加工时间矩阵—t1

限制坐标范围
画出甘特图
结束
输出结果：（包含加工编号，零件编号，最优加工时间绝阵t1,最短工期）--result
子
程
序
II
算法流程图如下：

i >n?
初始线索index1/2下标i1=1; i2=1
是
否
最小值下标
Index1(i1,D1)=0?
i1=i1+1
否
是
最小值下标
Index2(i2,D1)=0?
I2=i2+1
得到没有排位的零件index1/2下标i1,i2
是
A(i1,D1)<=B(i2,D1) ?
说明遍历t2,最小值在第一列
零件index1(i1,D1)应靠前加工
Newsort(i)=index1(i1,D1)
遍历index2(:,D1),在index2(:,D1)找到零件index1(i1,D1)并致零，index1(i1,D1)也=0
说明遍历t2,最小值在第一列
零件index2(i2,D1)应靠后加工
Newsort(n-i+1)=index2(i2,D1)
遍历index2(:,D1),在index2(:,D1)找到零件index1(i1,D1)并致零，index1(i1,D1)也=0
否
i=i+1
子程序I
是
否

子程序II/甘特图画法
(过程1包含一个条件若j为偶数，线条加粗，为简化流程图，此处未列出)

求出加工零件在机器j上加工时间x0=
Tmin(i,j)-max
(Tmin(i-1,j),Tmin(I,j-1))
是
否
是
否
j>n ?
j=j+11
i=i+11
j=j+1
i=i+1
第i个加工零件在第一个机器上加工，开始时间为Tmin(i,1)-x0，结束时间为Tmin(i,1)，高度为i,画出这一段时间内的加工图
过程1

第i个加工零件在第j个机器上加工，开始时间为Tmin(i,j)-x0，结束时间为Tmin(i,j). 高度为i,画出这一段时间内的加工图
过程1

标出机器号j
标出机器号j
求出加工零件在机器j上加工时间x0 =Tmin(I,1)-Tmin(I-1,1)
是
否
j=1 ?
i>n ?
标出第i个生产的零件编号—No_sort(i)
是
i =1 ?
否
是
否
j=1 ?
第一个加工零件在第一个机器上加工，开始时间为0，结束时间为Tmin(1,1)，高度为i,画出这一段时间内的加工图
过程1
第一个加工零件在第j个机器上加工，开始时间为Tmin(1,j-1)，结束时间为Tmin(1,1). 高度为i,画出这一段时间内的加工图
过程1

标出机器号j
标出机器号j

根据上述利用软件进行仿真，最终运行结果为：
>>请输入加工时间矩阵
t(i,j)表示第i个零件在机器j上的加工时间:
[1 4 8 7;2 5 4 4;6 5 6 3;7 4 3 1 ;1 4 6 8]
result =
1 5 1 5 11 19
2 1 2 9 19 26
3 2 4 14 23 30
4 3 10 19 29 33
5 4 17 23 32 34
输出结果说明第一列元素表示加工顺序，
第二列表示加工零件编号，第三列到以后为：
每个零件在不同机器上的完工时间矩阵

甘特图是一种用来形象的表示机器生产进度（加工顺序的）图形。此问题中求解出的甘特图如下：

四、 参考文献
[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');
[n m]=size(t); % n 表示加工零件数，m 表示机器数
t2=zeros(n,2); % t2 用来存放两台虚拟机器的时间
A=zeros(n,m-1); % A B分别存放两台虚拟机器的时间排序后的时间, m-1为根据约翰逊贝尔曼法则（Johnson-Bellman rule，一下简称 J&B）,当 m>2,可以分为 m-1中情况
B=zeros(n,m-1); % A(:,i) 表示 第i中分法下的排序方法
index1=zeros(n,m-1);
index2=zeros(n,m-1); % index1 index2 分别存放两台虚拟机器的时间排序后对应的零件序号
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中分法下的最后的最优解
for i=1:n % 编号
No(i,1)=i;
end

% J&B法则模拟两个虚拟机器
for D1=1:m-1
for i=1:D1
t2(:,1)=t2(:,1)+t(:,i); %机器1
end
for i=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

for D1=1:m-1

% 求m-1中两个虚拟机的排序情况
% 根据 J&B 法则第 D1 中分法下的加工顺序
j0=1;
j1=1;
for i=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; % 每次均从第一个最小值开始判定
while index1(i1,D1)==0 % 如果最小值下标为零，已经排位，不在比较，i1++;i2++,向下一位走
i1=i1+1;
end
while index2(i2,D1)==0
i2=i2+1;

end
if A(i1,D1)<=B(i2,D1) % 如果最小值产生在A(：,D1),即机器1，则先加工
newsort(j0,D1)=index1(i1,D1);
j0=j0+1; %说明靠前位置下移
for j=1:n
if index2(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;
for j=1:n
if index1(j,D1)==index2(i2,D1) %遍历 index1，=0说明该工件已经加入排序中
index1(j,D1)=0;
index2(i2,D1)=0; %加入排位后，将下标致零
end
end
end
end
end

for D1=1:m-1
for i=1:n
T1(i,:,D1)=t(newsort(i,D1),:); % 排序后的时间矩阵
end
for i=1:n %为T2第一列赋值
for j=1:i
T2(i,1,D1)=T2(i,1,D1)+T1(j,1,D1);
end
end

for i=2:m %为T2第一行赋值
for j=1:i
T2(1,i,D1)=T2(1,i,D1)+T1(1,j,D1);
end
end

for i=2:n %为i>1,j>1赋值
for j=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每行对应的的零件
for i=1:n
t1(i,:)=t(No_sort(i),:); % 对应最优排序后的加工时间矩阵
end
result=[No,No_sort,Tmin]
fprintf('输出结果说明第一列元素表示加工顺序，\n第二列表示加工零件编号，第三列到以后为：\n每个零件在不同机器上的完工时间矩阵');
% 画出加工零件的甘特图
% 变量说明以及输出说明
% 每一行表示一个零件加工过程
% 在线条上的数字表示第几个机器
% 图片开始的数字为零件的编号
% line();画出i零件在j机器上的加工情况
% text();标出机器代号
grid on;
axis([-4 Tmin(n,m)+2 0 n+1]); % 限制坐标范围
for i=1:n
k=No_sort(i);
text(-2,i,int2str(k));
for j=1:m
% 画出零件编号
if i==1 %第一个加工零件
if j==1 %第一个机器加工情况
line([0,Tmin(i,j)],[i i]);
text(Tmin(i,j)/2,i,int2str(j));
else
if mod(j,2)==0 % 使同一个零件在连续两台机器上加工的情况显示结果不同，便于观察
line([Tmin(i,j-1),Tmin(i,j)],[i i],'LineWidth',3);
text((Tmin(i,j)+Tmin(i,j-1))/2,i,int2str(j));
else
line([Tmin(i,j-1),Tmin(i,j)],[i i]);
text((Tmin(i,j)+Tmin(i,j-1))/2,i,int2str(j));
end
end
else
if j==1
x0=Tmin(i,j)-Tmin(i-1,j); % i零件在 j机器上的加工时间
line([Tmin(i,j)-x0,Tmin(i,j)],[i i]);
text((Tmin(i,j)*2-x0)/2,i,int2str(j));
else
if mod(j,2)==0
x0=Tmin(i,j)-max(Tmin(i-1,j),Tmin(i,j-1));
line([Tmin(i,j)-x0,Tmin(i,j)],[i i],'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)],[i i]);
text((Tmin(i,j)*2-x0)/2,i,int2str(j));
end
end
end
end
end

13