最短时间生产计划安排

1、整理文本最短时间生产计划安排曹国威 1、马俊钦 2 、何秀平 21、韶关学院 04 级数学系信息与计算科学5120052、 韶关学院 04 级数学系数学与应用数学512005摘要 离散系统仿真在工业生产的工序安排中起到了相当重要的作用，如何就一些内部机 制复杂的离散问题建立简单易行、可监测性强的数学模型一直是仿真技术的研究热 点离散事件系统现有三种仿真建模策略， 即：事件调度法，活动扫描法和进程交互法 本 文则采用了其中的活动扫描法对生产中的一个实际例子进行了处理 活动扫描法对于各 事件之间相关性很强的系统有着很好的适用性 本文针对该类方法仿真程序难以实现的 特点，特意附加了 matlab6.

2、5对该问题的实现程序.关键词:离散时间动态系统；仿真建模；活动扫描法1 问题的提出在许多工厂生产过程中，由于设备的数量、产品加工的次序限制，往往不能简单地安排生产任务我们设想，应用强大的数学软件配合简单易行的方法进行安排.设某重型机械厂产品都是单件性的，其中有一车间共有4种不同设备，现接受6件产品的加工任务，每件产品接受的程序在指定的设备上加工，其工序与加工周期如下表产工序品12345678STSTSTSTSTSTSTST13812243244621445233433347115220184273642111416335410243844112364161124173345123518（表一）

3、（S设备号、T周期）现在我们根据这一实际问题，寻求安排的方法.要求：1每件产品必须按规定的工序加工，不得颠倒.2、每台设备在同一时间只能担任一项任务（每件产品的每个工序为一个任务）3、在尽可能短的时间里，完成所接受的全部任务.为了节省电能，合理分配生产任务，厂方还要求：1、做出每件产品的每个工序开工、完工时间表2、给出每台设备承担任务的时间表2 模型的准备2.1模型的简化该问题要求在尽可能短的时间内完成所有产品的各个工序，其中每件产品的各个工 序之间是有先后顺序的；各型号设备只有一台，且同一时间只能承担一个任务在解决这个问题之前，我们可以先考虑一个类似的经简化的问题：现有编号为 A， B， C

4、， D， E， F， G 的七个零件安排在同一台机床上加工设各零 件的加工时间依次为 t1 14,t2 6,t3 24,t4 12,t5 6,t6 18,t7 12,（分钟）该机床 次只能加工一个零件，每个零件加工完毕即可运走投入下一工序要求安排一个加工次 序，使各零件的加工与等待的时间总和最小显然,加工与等待时间的总和为7T （8 k）tikK1其中 tik ti， k 意味着第 i 个零件被安排在第 k 步进行加工总和最小加工顺序是：BEDGAFC其中B和E, D和G的位置可对调，T= 288 （分钟）.推广：对于一台设备，n （n1）个耗时不同的操作，如果每次只能执行其中的一个,那么使得

5、等待时间总和最少的方案为：按时间大小排序，先处理时间小的工序在多台设备的情况中，对于每一台设备，如果在同一时间内有多个不同的任务可供 选择，则我们先选择耗时较短的那一个任务，这样可使得总耗时最少.2.2符号约定Si :第i件设备（i 1,2,4）Tjk :第j件产品的第k道工序的加工周期（j 1,26 k 1,28）t:加工过程的某时刻（t = 1,2,3,4；）3模型的建立及求解为解决之前提出的生产实例，我们列出如下的表格:S/t123456789101112131415362222offoffoffoffoffoff1166S2444444466665555&333111111114444

6、S4555555555522222俵二）（其中S表示设备号，t表示加工过程的某时刻，数字代表产品号，of表示关机）对于每时刻t，若Si处于开机状态，则在该时刻记录产品的号码，若处于关机状态， 则标记off 这样既能记录各个设备的工作状态，也便于及时找到有空闲（处于关机状 态）的设备并分配任务道理如问题分析中的简单例子，假如3现有Tmn和Tpq两个任务可选，且Tmn Tpq，那么选择Tmn将带来更多的等待时间（因为此时有一道工序等待着 这道工序的完工，然后投入工作），为了使得总的等待时间最短，我们在每次的选择中 选出造成等待时间最小的进行加工.3.1具体演算如下(I)创建表格TURNS/t123

7、45678910111213141516S1offoffoffoffoffoffoffoffoffoffoffoffoffoffoffoffS2offoffoffoffoffoffoffoffoffoffoffoffoffoffoffoffS3offoffoffoffoffoffoffoffoffoffoffoffoffoffoffoffS4offoffoffoffoffoffoffoffoffoffoffoffoffoffoffoff(II)搜索第1列，S!处于关机状态，在表一中知道 3可以接Tr或T“，其中T“时间 较短，所以在第3 = 1行，t= 1到t + T611 = 1列填上j =

8、 6; S2、S3、S4行也如此操 作，得表三.S/t12345678910111213141516S16offoffoffoffoffoffoffoffoffoffoffoffoffoffoffS24444444offoffoffoffoffoffoffoffoffS3333offoffoffoffoffoffoffoffoffoffoffoffoffS45555555555offoffoffoffoffoff(表三)(III )搜索第二列，其中S1处于关机状态，可知T61已经完成，所以6号产品可以进 行第二个工序的加工.S1可执行的操作为T21，所以在第S1 = 1行，t = 2到t +

9、T21 - 1= 5 列填上j = 2.(IV)继续上面的循环直至所有的工序都完成.3.2在matlab6.5语言环境下演算步骤如下设置时间表格TURN的初始状态（表二中各格填上OFF）;设定t的初值为1；WHILE（工序未全部完成）扫描TURN:FOR i=1 TO 4IF（MARK（i,t）=OFF）THEN扫描Si能执行的任务；IF（搜索成功）THEN设找到且此刻最短时间的任务所耗时间为Tjk，将Si行的第t到t Tjk 1列的内容改为加工的产品的序号j;ELSE搜索 Si 1 （若 i=3）;或使t+1并执行下一个循环（若i=4）;ENDIFELSE搜索 Si 1（若 imeson(m

10、)(x(k),y(k)a=x(k) y(k);endendif turnon(m),j=off & meson(m)(a(1),a(2)=100%若时间为 100则意味着这个步骤不属于我们希望使用的那件设备 while tim(a(1),a(2)0turnon(m),tim(a(1),a(2)+j-1=a(1); tim(a(1),a(2)=tim(a(1),a(2)-1;endendendfor i=1:4 if turni,j=offdai(i)=turni,j;endendfor i=1:4if turni,j=off & turni,j+1=offgongxu(turni,j)=gongxu(turni,j)+1; open(turni,j,gongxu(