【精品】最短时间生产计划安排.doc

【精品】最短时间生产计划安排 最短时间生产计划安排曹国威 1、马俊钦 2、何秀平 21、韶关学院04级数学系信息与计算科学 51xx2、韶关学院04级数学系数学与应用数学51xx摘要离散系统仿真在工业生产的工序安排中起到了相当重要的作用，如何就一些内部机制复杂的离散问题建立简单易行、可监测性强的数学模型一直是仿真技术的研究热点离散事件系统现有三种仿真建模策略，即事件调度法，活动扫描法和进程交互法本文则采用了其中的活动扫描法对生产中的一个实际例子进行了处理活动扫描法对于各事件之间相关性很强的系统有着很好的适用性本文针对该类方法仿真程序难以实现的特点，特意附加了matlab6.5对该问题的实现程序关键词:离散时间动态系统；仿真建模；活动扫描法问题的提出在许多工厂生产过程中，由于设备的数量、产品加工的次序限制，往往不能简单地安排生产任务我们设想，应用强大的数学软件配合简单易行的方法进行安排设某重型机械厂产品都是单件性的，其中有一车间共有4种不同设备，现接受6件产品的加工任务，每件产品接受的程序在指定的设备上加工，其工序与加工周期如下表产工序品S T S T S T S138122432144523333347115242736421154102438461124173（表一）（S设备号、T周期）现在我们根据这一实际问题，寻求安排的方法要求 1、每件产品必须按规定的工序加工，不得颠倒 2、每台设备在同一时间只能担任一项任务（每件产品的每个工序为一个任务）、在尽可能短的时间里，完成所接受的全部任务为了节省电能，合理分配生产任务，厂方还要求 1、做出每件产品的每个工序开工、完工时间表 2、给出每台设备承担任务的时间表12345678T S244xx4134TS68161251TSTST36412351841332模型的准备2.1模型的简化该问题要求在尽可能短的时间内完成所有产品的各个工序，其中每件产品的各个工序之间是有先后顺序的；各型号设备只有一台，且同一时间只能承担一个任务在解决这个问题之前，我们可以先考虑一个类似的经简化的问题现有编号为A，B，C，D，E，F，G的七个零件安排在同一台机床上加工设各零件的加工时间依次为,12,18,6,12,24,6,147654321?ttttttt（分钟）该机床一次只能加工一个零件，每个零件加工完毕即可运走投入下一工序要求安排一个加工次序，使各零件的加工与等待的时间总和最小显然,加工与等待时间的总和为?K?71)ik t8(kT其中iiktt?，k意味着第i个零件被安排在第k步进行加工总和最小加工顺序是CFAGDEB?其中B和E，D和G的位置可对调，T288（分钟）推广对于一台设备，n（n1）个耗时不同的操作，如果每次只能执行其中的一个，那么使得等待时间总和最少的方案为按时间大小排序，先处理时间小的工序在多台设备的情况中，对于每一台设备，如果在同一时间内有多个不同的任务可供选择，则我们先选择耗时较短的那一个任务，这样可使得总耗时最少2.2符号约定iS第i件设备(4,2,1?i)jkT第j件产品的第k道工序的加工周期(82,1?62,1?kj)t加工过程的某时刻(t1,2,3,4,)3模型的建立及求解为解决之前提出的生产实例，我们列出如下的表格S/t1234567891011121314151S62222offoffoffoffoffoff11662S4444444666655553S3331111111144444S555555555522222(表二)（其中S表示设备号，t表示加工过程的某时刻，数字代表产品号，off表示关机）对于每时刻t，若iS处于开机状态，则在该时刻记录产品的号码，若处于关机状态，则标记off这样既能记录各个设备的工作状态，也便于及时找到有空闲（处于关机状态）的设备并分配任务道理如问题分析中的简单例子，假如1S现有mnT和pqT两个任务可选，且pqmnTT?，那么选择mnT将带来更多的等待时间（因为此时有一道工序等待着这道工序的完工，然后投入工作），为了使得总的等待时间最短，我们在每次的选择中选出造成等待时间最小的进行加工3.1具体演算如下（I）创建表格TURN S/t123456789101112131415161S off off off off off off offoffoffoffoffoffoff off off off2S off off off off off off offoffoffoffoffoffoff offoffoff3S offoffoffoffoffoff offoffoffoffoffoffoff offoffoff4S offoffoffoffoffoff offoffoffoffoffoffoff offoffoff(II)搜索第1列，1S处于关机状态，在表一中知道1S可以接21T或61T，其中61T时间较短，所以在第1S1行，t1到t61T11列填上j6；2S、3S、4S行也如此操作，得表三S/t123456789101112131415161S6offoffoffoffoffoffoffoffoffoffoffoffoff offoff2S4444444offoffoffoffoffoffoff offoff3S333offoffoffoffoffoffoffoffoffoffoff offoff4S5555555555offoffoffoffoffoff（表三）（III）搜索第二列，其中1S处于关机状态，可知61T已经完成，所以6号产品可以进行第二个工序的加工1S可执行的操作为21T，所以在第1S1行，t2到t21T15列填上j2（IV）继续上面的循环直至所有的工序都完成在matlab6.5语言环境下演算步骤如下设置时间表格TURN的初始状态(表二中各格填上OFF);设定t的初值为1;WHILE(工序未全部完成)扫描TURN:FOR i=1TO4IF(MARK(i,t)=OFF)THEN扫描iS能执行的任务;IF(搜索成功)THEN设找到且此刻最短时间的任务所耗时间为jkT，将iS行的第t到1?jkTt列的内容改为加工的产品的序号j;ELSE搜索1?iS(若i=3);或使t+1并执行下一个循环(若i=4);ENDIF ELSE搜索1?iS(若imeson(m)(x(k),y(k)a=x(k)y(k);end end if 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;endendendfori=1:4if turni,j=offdai(i)=turni,j;endendfori=1:4if turni,j=off&turni,j+1=offgongxu(turni,j)=gongxu(turni,j