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

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

2、的生产进度。关键字：加工顺序最优 Matlab 甘特图 约翰逊贝尔曼算法2目录一、问题重述与分析 .21.1 问题的重述 .21.2 问题的分析 .2二、符号说明 .2三、调度问题模型的建立 .33.1 两个工作条件的给出 .33.3 算法的描述 .43.4 问题的求解和结果 .5四、参考文献 .9五、附录 .93一、 问题重述与分析1.1 问题的重述工厂中，有 n 个不同的配件需要生产，每个配件都必须由 m 台不同的机器进行顺序加工处理，配件 i 在机器 j 上所需的处理时间为 t(i,j)。现约定未完工前不允许中断处理，配件不能拆分成更小配件。要求给出一种配件调度方案，使所给的 n 个配件

3、在尽可能短的时间内处理完成。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

4、) 用来存放 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 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 个加工零件在第一个

5、机器上加工，开始时间为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,画出这一段

6、时间内的加工图过程 1第一个加工零件在第 j 个机器上加工，开始时间为 Tmin(1,j-1)，结束时间为Tmin(1,1). 高度为 i,画出这一段时间内的加工图过程 1标出机器号 j 标出机器号 j 9根据上述利用软件进行仿真，最终运行结果为：请输入加工时间矩阵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 192 1 2 9 19 263 2 4 14 23 304 3 10 19 29 335 4 17 23 32 34输出结果说明第一列元素表示加工顺序，第二

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

8、器 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 % A(:,i) 表示 第 i 中分法下的排序方法index1=zeros(n,m-1);index2=zeros(n,m-1); % index1 index2 分别存放两台虚拟机器的时间排序后对应的零件序号newsort=zeros(n,m-1); % newsort(:,i) 表示根据 J % T1(:,:,i)表示根据 J % T2(:,:,i)表示根据 J % Tmin(n,m) 加工完成时间矩阵，表示 i 零件在 j机器上完成后的总时间No_sort=zeros(1,n); % No_sort 为最后根据 m-1 中分法下的最后的最优解for i=1:n % 编号No(i,1)=i;end% J %机器 1