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

1、百度文库第六届计算机仿真大赛参赛作品题号：4组别：高年级作者：XXX学院：XXX联系电话： XXX有关加工调度问题的计算机仿真模型摘要本文讨论在工业生产中，利用建立模型，优化多个零件在多台机器上进行加 工的顺序安排，以提高设备利用率和生产效率的调度问题。 主要建立的模型如下：流水线调度优化模型：通过利用约翰逊贝尔曼法则找出最优结果排序。首先 写出约翰逊贝尔曼法则在多个机器（m2的算法，根据算法利用Matlab软件进 行计算机仿真，得出最优加工顺序的结果（见正文第 9页）。为了形象描述问题 并得到本系统的流程图和核心程序的流程图，利用甘特图模型进行仿真，最终形 象的表示机器设备的生产进度。关键字

2、：加工顺序最优 Matlab甘特图 约翰逊贝尔曼算法17目录一、问题重述与分析3问题的重述3问题的分析3二、符号说明3三、调度问题模型的建立 4两个工作条件的给出： 4算法的描述卬【2】：4问题的求解和结果 5四、参考文献9五、附录9一、问题重述与分析问题的重述工厂中，有n个不同的配件需要生产， 每个配件都必须由 m台不同的机器进行顺序加工 处理，配件i在机器j上所需的处理时间为 t(i,j)。现约定未完工前不允许中断处理，配件不 能拆分成更小配件。 要求给出一种配件调度方案，使所给的n个配件在尽可能短的时间内处理完成。问题的分析此问题的求解主要依靠运用运筹学相关理论学科，解决加工顺序的最优安

3、排 以达到零件生产效率提高的工业要求，可以利用约翰逊贝尔曼法则找出最优结果 排序，利用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)in dex1( n,m-1)用来存放m-1种分组方式下，按大小排序后的t2(:,1)零件序号in dex2( n,m-1)用来存放m-1种分组方式下，按大小排

4、序后的t2(:,2)零件序号n ewsort( 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中分法下的加工顺序后的 完工时间表/IT(1,m-1)表示m-1种分组方式下的最短工期数组No sort(1, n)m-1中分法下的T中元素最小最优解加工零件的排序 /Tmi n(n,m)m-1中分法下的T中元素最小最优解加工顺序后的完工时间表t1( n,m)对应最优排序后的加工时间矩阵j0表示靠前加工零件

5、的个数/j1表示靠后加工零件的个数/1112i1,i2分别表示每轮最小值 A(:,D1)U B(:D1)下标(共n次， 确疋newsort(:,D1)的零件排序) -1resultresult=No,No_sort,Tmi n输出结果说明第一列元素表示加工顺序，第二列表示加工零 件编号，第三列到以后为：每个零件在不同机器上的完工时间矩阵三、调度问题模型的建立两个工作条件的给出：n个工件在m台机器上的加工顺序相同。工件在机器上的加工时间是给定的 (时间矩阵t(n,m),t(i,j)表示i零件在机器j上加工时间)。问题的目标是求n个工件在每合机器上的最大完工时间等于最大流程时间。这种流水线调度问题

6、要在满足以下两个约束条件的前提下，使得加工完所有的工件所花的时间尽可能地 少：1、工件约束每个工件在每台机器上恰好加工一次，每个工件在各机器上加工顺序相同。 不失一般性，假设各工件按机器1至m的顺序进行加工。各工件在各机器上的加 工时间已知。2、机器约束每台机器在任何时刻至多加工一个工件，每台机器加工的各工件的顺序相 同。工件加工顺序的原则：置换流水线调度问题实质是如何调整加工工件的序列，提高机器的利用率的问题，即在同一时刻正在加工的机器数越多，机器利用率越大口根据该原则，我 们根据下面规则安排：1、在前面机器加工时间较短、后面机器加工时间较长的工件，安排在序列 前。这样可以使得后面的机器尽快

7、参加工作，并且后面的机器不需要作空等待，2、机器加工时间较为平均且加工时间较长的工件，安排在序列的中部。这 样可以使得各个机器在中期的时候都能得到运作。3、前面加工时间较长，后面加工时间较短的工件按排在序列尾部。这样使 得前面的机器能“延迟”完工，后面的机器尽快完工。算法的描述11】【2,：我们采用约翰逊-贝尔曼法则(Johnson-Bellman rule ，一下简称J&B)1、 N种零件在两台机器上加工(M1, M2,根据J&B法则，最短工期加工顺序， 方法如下：(1) 检索t(:,1) ，t(:,2)(表示各零件分别在M1, M2上加工时间)的各 种数据，找出其中最小值(2) 上述最小值

8、如果属于第一列，则该零件应靠前加工，相反，若在第 二列则靠后加工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)和完工时间矩阵

9、T2(:,:,D1)T2(i,:,D1),T1(i,:,D1) 中 i 等于 newsort(i,D1)T2(n,m,D1)表示第D1种分组方式下的最短工期T表示第m-1种分组方式下的最短工期数组4、算出T2后，就可以找出m-1种分组方式下的最优解了。 问题的求解和结果算法流程图如下：输入原始数据ti1=i1+1是最小值下标Newsort(i)=i ndex1(i1,D1)i n?否初始线索index1/2下标i1=1;i2=1In dex1(i1,D1)=否I2=i2+1是否最小值下标In dex2(i2,D1)=A(i1,D1)n ?j=j+11否F标出第件编号i个生产的零No_sort(

10、i)r是否否i =1 ?j=1 ?j=1否否求出加工零件在机 器j上加工时间X0=Tmi n(l,1)-Tmi n( 1-1第一个加工零第一个加工零件件在第个机在第j个机器上器上加工，开加工，开始时间始时间为0,为 Tmin(1,j-1),结束时间为结束时间为Tmin(1,1),高Tmin(1,1).高度度为i,画出这为i,画出这一段一段时间内的时间内的加工图加工图过程1过程1是求出加工零件在机 器j上加工时间x0=Tmi n(i,j)-max(Tmi n(i-1,j),Tmi n(l,j标出机器号第i个加工零件在 第一个机器上加 工，开始时间为Tmin(i,1)-x0 ，结束 时间为 Tmi

11、n(i,1)， 高度为i,画出这一 段时间内的加工 图过程1 i=i+1标岀机器号标岀机器号第i个加工零件在第 j个机器上加工，开 始 时 间 为Tmin(i,j)-x0 ，结束时 间为Tmin(i,j).高度 为i,画出这一段时间 内的加工图标岀机器号j子程序II/甘特图画法(过程1包含一个条件若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 =1515111921291926X.32414

12、233043101929335417233234输出结果说明第一列元素表示加工顺序， 第二列表示加工零件编号，第三列到以后为: 每个零件在不同机器上的完工时间矩阵甘特图是一种用来形象的表示机器生产进度(加工顺序的)图形。此问题中 求解出的甘特图如下：01TS世四、参考文献1 朱德通著，最优化模型与实验M,同济大学出版社，2 宋存利著，求解多工艺路线车间调度问题的禁忌-遗传算法J,大连交 通大学出版社，3 陈国良著，遗传算法及其应用M,人民邮电出版社，4 董立华高秀莲著，数学建模与数学实验M,天津教育出版社，五、附录有关工件加工顺序的程序：clear;clf;t=in put(请输入加工时间矩阵

13、间:n);n m=size(t); % n t2=zeros( n, 2);% t2A=zeros( n, m-1);% A Bm-1为根据约翰逊贝尔曼法则 可以分为m-1中情况B=zeros( n,m-1);% A(:,i)in dex1=zeros( n,m-1);in dex2=zeros( n,m-1);%后对应的零件序号n ewsort=zeros( n, m-1); %加工顺序T1=zeros( n,m,m-1);%T1(:,:,i)顺序后的时间表T2=zeros( n,m,m-1);%T2(:,:,i)顺序后的最短工期表T=zeros(1,m-1);% Tmi n(n,m)机器上

14、完成后的总时间No_sort=zeros(1, n);% No_sortfor i=1:n%编号No(i,1)=i;end% J&B法则模拟两个虚拟机器for D1=1:m-1for i=1:D1t2(:,1)=t2(:,1)+t(:,i); %endnt(i,j) 表示第i个零件在机器j上的加工时表示加工零件数，m表示机器数用来存放两台虚拟机器的时间分别存放两台虚拟机器的时间排序后的时间，(Johnson-Bellman rule ，一下简称 J&B),当 m2,表示 第i中分法下的排序方法index1 index2分别存放两台虚拟机器的时间排序newsort(:,i)表示根据J&B法则第i

15、中分法下的表示根据J&B法则第i中分法下的加工表示根据J&B法则第i中分法下的加工加工完成时间矩阵，表示i零件在j为最后根据m-1中分法下的最后的最优解机器1for i=D1:mt2(:,2)=t2(:,2)+t(:,i); %机器 2endA(:,D1), index1(:,D1)=sort(t2(:,1); % A(:,D1)中保存第 D1 分法中机器1中按从小到大的排序值，in dex1(:,D1)对应的零件下标B(:,D1), index2(:,D1)=sort(t2(:,2); % B(:,D1)中保存第 D1 分法中机器2中按从小到大的排序值，index2(:,D1)对应的零件下标

16、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(:

17、,D1)、B(:D1)下标(共n次，确定newsort(:,D1)的零件排序)i2=1; %每次均从第一个最小值开始判定while in dex1(i1,D1)=0 %如果最小值下标为零，已经排位，不在比较，i1+;i2+,向下一位走i1=i1+1;endwhile in dex2(i2,D1)=0i2=i2+1;endif A(i1,D1)v=B(i2,D1) %如果最小值产生在 A(: ,D1),即机器1,则先加工newsort(j0,D1)=i ndex1(i1,D1);j0=j0+1; %说明靠前位置下移for j=1: nif in dex2(j,D1)=i ndex1(i1,D1)

18、 %遍历 in dex2,=0 说明该工件已经加入排序中in dex2(j,D1)=0;in dex1(i1,D1)=0; %加入排位后，将下标致零endendelse %如果最小值产生在newsort( n-j1+1,D1)=i ndex2(i2,D1);j1=j1+1;for j=1: nif index1(j,D1)=index2(i2,D1) %该工件已经加入排序中in dex1(j,D1)=0;in dex2(i2,D1)=0;%endendendendendB(: ,D1),即机器2,则最后加工遍历indexl , =0说明加入排位后，将下标致零for D1=1:m-1for i=

19、1: nT1(i,:,D1)=t (n ewsort(i,D1),:); %排序后的时间矩阵endfor i=1: n%为T2第一列赋值for j=1:iT2(i,1,D1)=T2(i,1,D1)+T1(j,1,D1);endendfor i=2:m% 为T2第一行赋值for j=1:iT2(1,i,D1)=T2(1,i,D1)+T1(1,j,D1);endendfor i=2:n % 为 i1,j1 赋值for j=2:mT2(i,j,D1)=T1(i,j,D1)+max(T2(i-1,j,D1),T2(i,j-1,D1);%实际含义是：零件i在机器j上完成的时间为零件i在机器j的加工时间+

20、%零件i在j-1机器(满足要求：顺序加工)和上一个零件加工完成中的最大 一个(每个机器一次只能加工一个零件)endendT(D1)=T2(n,m,D1); % 将m-1种结果产生的最小时间赋值给 Tend%对T排序，得到m-1中结果中的最优解tmi n,i ndexO=sort(T);Tmin=T2(:,:,indexO(1);%最优解中加工完成时间矩阵(排序后的，不同与t中零件排序)No_sort=newsort(:,i ndex0(1); % Tmi n每行对应的的零件for i=1: nt1(i,:)=t(No_sort(i),:); %对应最优排序后的加工时间矩阵endresult=N

21、o,No_sort,Tmi nfprintf(输出结果说明第一列元素表示加工顺序，n第二列表示加工零件编号，第三列到以后为：n每个零件在不同机器上的完工时间矩阵);%画出加工零件的甘特图%变量说明以及输出说明%每一行表示一个零件加工过程%在线条上的数字表示第几个机器%图片开始的数字为零件的编号% line();画出i零件在j机器上的加工情况% text();标出机器代号grid on;axis(-4 Tmi n(n,m )+2 0 n+1); %限制坐标范围for i=1: nk=No_sort(i);text(-2,i,i nt2str(k);for j=1:m%画出零件编号if i=1%第一个加工零件if j=1