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

编号：第六届计算机仿真大赛参赛作品题号: 4 组别： 高年级 作者： XXX 学院： XXX 联系电话： XXX 有关加工调度问题的计算机仿真模型摘要本文讨论在工业生产中，利用建立模型，优化多个零件在多台机器上进行加工的顺序安排，以提高设备利用率和生产效率的调度问题。主要建立的模型如下：流水线调度优化模型：通过利用约翰逊贝尔曼法则找出最优结果排序。首先写出约翰逊贝尔曼法则在多个机器（m2）的算法，根据算法利用Matlab软件进行计算机仿真，得出最优加工顺序的结果（见正文第9页）。为了形象描述问题并得到本系统的流程图和核心程序的流程图，利用甘特图模型进行仿真，最终形象的表示机器设备的生产进度。关键字：加工顺序最优 Matlab 甘特图 约翰逊贝尔曼算法目录一、问题重述与分析21.1问题的重述21.2问题的分析2二、符号说明2三、调度问题模型的建立33.1 两个工作条件的给出33.3算法的描述43.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表示靠后加工零件的个数i1i1,i2分别表示每轮最小值A(:,D1)、B(:D1)下标（共n次，确定newsort(:,D1)的零件排序）i2resultresult=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)）1M1M2+M3+ +Mm2M1+M2M3+M4+ +Mmm-1M1+M2+ +Mm-1Mmm台机器共有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开始D1m-1 ?第D1种分组方式下2个虚拟机器，对应加工时间t2对加工零件时间排序：t2(:,1)A(:,D1) 下标index1t2(:,2)B(:,D1) 下标index22台机器下确定零件加工顺序newsort(:,D1)按上加工顺序的时间矩阵T1(:,:,D1)按约定算法生成按上加工顺序的完工时间矩阵- T1(:,:,D1)将该分组方式下产生的最短工期放入矩阵TD1=D1+1输入原始数据t是对T进行排序，sort(T)tminT下标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)n ?j=j+11i=i+11j=j+1i=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 ? in ?标出第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 8result = 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.62 宋存利著，求解多工艺路线车间调度问题的禁忌-遗传算法J,大 连交通大学出版社，2008.4 3陈国良著，遗传算法及其应用M,人民邮电出版社，2000.44董立华 高秀莲著 ，数学建模与数学实验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）,当 m2,可以分为 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)对应的零件下标endfor 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)1,j1赋值 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种结果产生的最小时间赋值给Tend% 对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),:); % 对应最优排序后的加工时间矩阵 endresult=No,No_sort,Tminfprintf(输出结果说明第一列元素表示加工顺序，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 endend13