第11章-作业排序.优秀PPT.ppt

《第11章-作业排序.优秀PPT.ppt》由会员分享，可在线阅读，更多相关《第11章-作业排序.优秀PPT.ppt（35页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第十一章 作业排序（生产过程时间组织）生产过程时间组织的目标：削减时间损失，缩短生产周期，提高生产效率，降低在制品占用量，提高生产效益。流水作业排序问题流水车间(Flow shop):工件的加工路途都一样。相同零件、不同移动方式下加工周期N项任务单台机器的作业排序问题N项任务两台机器排序问题的最优算法 N项任务m台设备排序问题的启发式算法Work Center#1Work Center#2Output相同零件不同移动方式下加工周期的计算n当n个零件相同，则无排序问题。但不同移动方式下的加工周期不同n三种典型的移动方式n依次移动方式：n平行移动方式：n平行依次移动方式 一批零件在上道工序全部加工

2、完毕后才整批地转移到下道一批零件在上道工序全部加工完毕后才整批地转移到下道工序接着加工。即零件在工序间是整批地移动。工序接着加工。即零件在工序间是整批地移动。工序M1t4t1t1t1t1t2t2t2t2M2M3t3t3t3t3M4t4t4t4时间 Tpnt1nt4nt3nt2Tp=nt1+nt2+nt3+nt4 故：故：Tp=n t i mi=1（一）依次移动方式（一）依次移动方式 设零件批量为n（件），工序数目为m，一批零件不计算工序间运输时间，只考虑加工时间，设其加工的周期为T（分钟），零件在i道工序的单件工时为 （分钟/件），i=1.2n.则该批零件的加工周期为：依次移动方式（续）（二）

3、平行移动方式（二）平行移动方式 每个零件在前道工序加工完毕后，马上转移到后道工序去接着加工。即零件在工序间1 件1 件地移动。工序M1M2M3M4时间t1t1t1t1t2t2t2t2t3t3t3t3t4t4t4t4t1t2t3 t4(n-1)t3ToTo=t1+t2+t3+t4+(n-1)t3 故：故：To=t i+(n-1)tL tL为最长的单件工序时间mi=1平行移动方式（续）零件平行移动的加工周期 为：（三）平行依次移动方式（三）平行依次移动方式 依次移动方式下，零件搬运次数少，设备连续加 工，利用率高，但加工周期长；平行移动方式下，加工周期短，但零件搬运频繁，设备间歇性加工，不便利用。

4、平行依次移动方式将两者的优点结合起来，既要求每道工序的设备连续加工，又要求各道工序尽可能平行地加工。（1）当ti ti+1 时，按平行移动方式移动；（2）当ti ti+1 时，以i工序最终一个零件的完工时间为基准，往前推移(n-1)ti+1 作为零件在(i+1)工序的起先加工时间。0 20 40 60 80 100 120 140 160M1M2M3M4T平顺平行依次移动方式平行依次移动方式Top=n t i-(n-1)min(tj，tj+1)mi=1m-1j=1 三种移动方式的比较三种移动方式的比较移动方式顺序移动平行移动平行顺序移动优缺点（1）管理简单，设备不停歇，可充分负荷。（2）加工周

5、期长。（1）周期最短，（2）设备有停歇，利用率低。（3）运输频繁，管理复杂。两者结合,扬长避短 组织管理复杂选择策略小而轻；单件小批；加工时间短，调整时间长；工艺专业化。大且重；大量大批；加工时间长，调整时间短；对象专业化。小而轻；大量大批；加工时间长，调整时间短；对象专业化。其次节 生产过程任务排序一、流水型排序问题 n项任务，等待多台串联设备组成的生产线加工，各项任务的工艺依次相同。1、n项任务，单台设备(一个单位)的排序。例：8项任务、单台设备，资料如下：任 务j1j2j3j4j5j6j7j8加工时间 tj836127532交货期 dj191293348403723任 务j8j2j7j6

6、j3j5j1j4加工时间 tj233567812交货期 dj231237409481934流程时间Fi2581319263446延期量Dj000010015131)、最小加工时间规则(SPT)按各任务加工时间的大小，从小大到排序。本规则可得到最小平均流程时间，最小平均在制品占用量。但可能出现延期交货。平均流程时间：2)EDD规则（最早交货期规则）任 务j3j2j1j8j4j7j6j5加工时间 tj638212357交货期 dj912192334374048流程时间Fi69171931343946延期量Dj0000000 0n按任务规定的交货期先后，从小到大排序。n可使交货延期量最小化，但平均流

7、程时间相对较大，平均在制品数较大。n平均流程时间n最大交货延期量为零任 务j3j2j1j8j4j7j6j5加工时间 tj638212357交货期 dj912192334374048流程时间Fi69171931343946延期量Dj00000000n3）、EDD-SPT综合规则：n按EDD规则排序所的方案的基础上，按SPT规则对其调整。任 务j2j3j8j1j7j4j6j5加工时间 tj362831257交货期 dj129231937334048流程时间Fi39111922343946延期量Dj00000000n1、找出最大流程时间max Fin2、找出满足条件：djmax Fi 的任务，当满足

8、条件的任务只有一项时，该任务不调整，当满足条件的任务有多项时，对这些任务按SPT规则调整。n去掉已调整的任务，对剩余任务反复用其次步直至全部任务调整完n平均流程时间n最大交货延期量为零2、N项任务、两台设备的排序 任 务j1j2j3j4j5j6j7j8 Ma taj836 12 7 532 Mb tbj9253410711 N项任务，均按 Ma-Mb 的工艺依次加工，要求最大流程时间最小化的最优排序方案。用约翰孙-贝尔曼规则求解1、找出最小加工时间，假如该时间在第一台设备行，则对应的任务最先加工，若在其次台设备行，则对应的任务排在最终加工；2、去掉已排序任务，对剩下的任务反复应用第1步，直至全

9、部任务排完。按约-贝规则对上例进行排序，得到排序结果如下：任务j8j7j6j1j3j5j4j2 Ma taj2 23 5 5 10 8 18 6 24 7 31 12 43 3 46 Mb tbj11 137 20 10 30 9 39 5 444 48 3 51 2 53J8-J7-J6-J1-J3-J5-J4-J2用哈姆表算法，求得各任务在各设备上的完工时间用哈姆表算法，求得各任务在各设备上的完工时间如下表：如下表：排序前的流程时间计算 任 务j1j2j3j4j5j6j7j8 Ma taj8 83 116 17 12 29 7 36 5 413 44 2 46 Mb tbj9 172 19

10、5 243 324 40 10 517 5811 69任务j1j2j3j4j5j6j7j8 Ma taj23 5867123 Mb tbj1171095432Mc tcj11131215161112142 2、N N项任务、三台设备的排序项任务、三台设备的排序 例：三台设备、例：三台设备、8 8项任务，各任务的工艺依次相同，项任务，各任务的工艺依次相同，资料如下：资料如下：n求最优解条件，满足如下条件之一：n求解步骤：n 1、把三台设备转换为两台假象设备，假想设备加工时间按如下公式转换：任 务j1j2j3j4j5j6j7j8 Mg tgj131015171111155 Mh thj222022

11、2421151516用约用约-贝规则求得排序结果如下：贝规则求得排序结果如下：J8-J2-J5-J6-J1-J3-J7-J4；(或：或：-J4-J7-J4-J7）上例中，满足条件上例中，满足条件转换两台假想设备，结果如下表：转换两台假想设备，结果如下表：任务j8j2j5j6j1j3j7j4 Ma taj3 33 6 6 12 7 19 2 21 5 26 12 38 8 46 Mb tbj2 57 13 5 18 4 23 11 34 10 44 3 47 9 56 Mc tcj14 1913 3216 48 11 59 11 7012 8212 9415 109 用哈姆表算法分别计算两方案的

12、流程时间：J8-J2-J5-J6-J1-J3-J7-J4；任务j8j2j5j6j1j3j4j7 Ma taj3 33 6 6 12 7 19 2 21 5 26 8 34 12 48 Mb tbj2 57 13 5 18 4 23 11 34 10 44 9 53 3 56 Mc tcj14 1913 3216 48 11 59 11 7012 8215 97 12 109 J J8 8-J-J2 2-J-J5 5-J-J6 6-J-J1 1-J-J3 3-J-J4 4-J-J7 7任务j1j2j3j4j5j6j7j8 Ma taj2 23 5 5 108 186 247 31 12 433

13、46 Mb tbj11 137 20 10 309 395 444 48 3 51 2 53Mc tcj11 2413 3312 45 15 60 16 7611 8712 9914 113 按自然依次加工的流程时间计算4、N项任务，m台设备的排序方法：例：8项任务，须经6台设备加工，求最优加工依次：任务 设备j1j2j3j4j5j6j7j8M1t1j57525642M2t2j75866223M3t1j36447632M4t1j436193119M5t1j82961837M6t1j29138976 合 计2932332236353029n1）、关键任务法：n求出各项任务的总加工时间；n以总加工

14、时间最大者为关键任务JC；n找出：t1,j tm,j的任务，按tm,j 从大到小排在JC 后面；nt1,j=tm,j的任务，排在JC 紧前或紧后。n求上例加工依次：n关键零件：Jc=J5n满足t1,j tm,j的零件有：J1、J3，按 tm,j从大到小排在J5之后。n得到加工依次：n J8-J4-J7-J6-J2-J5-J1-J3n 用哈姆表算法计算流程时间：任务 设备j8J4j7j6j2j5j1j3M1t1j2 22 44 86 147 215 26 5 315 36M2t2j3 56 11 2 13 2 165 266 327 398 47M3t1j2 74 153 18 6 246 32

15、7 393 424 51M4t1j9 151 1611 293 323 359 484 526 58M5t1j7 226 283 318 402 421 498 609 69M6t1j6 283 317 389 499 58 8 662 681 70 任务 设备j1j2j3j4j5j6j7j8M1t1j5 57 125 172 195 246 304 342 36M2t2j7 125 178 256 316 372 392 413 44M3t1j3 156 234 294 357 446 503 532 55M4t1j4 193 266 351 369 453 5311 649 73M5t1j

16、8 27 2 299 446 501 518 613 677 80M6t1j2 29 9 381 453 538 619 707 776 86n2、最小排序系数（kj）法：按 kj 大小，从小到大排序。上例按最小排序系数法，可得到较优加工依次：J8 J7 J6 J5 J3-J1-J4-J2 当设备数为单数时，把中间设备的加工时间，平分后加到前后两部分设备上去。任务 设备j1j2j3j4j5j6j7j8M1t1j57525642M2t2j75866223M3t1j36447632M4t1j436193119M5t1j82961837M6t1j29138976 kj1.071.291.061.21.00.70.430.32