案例五作业计划与排序案例1

作业计划与排序案例•生产作业计划的编制•生产作业控制•服务作业计划•案例五EarthBuddy生产作业计划的编制•生产作业类型•安排生产负荷•作业排序•多项作业、两台机器的排序•多项作业和多个加工中心的排序二、安排生产负荷•生产负荷安排是为有限的资源安排负荷的过程。•分配任务的问题可以利用线性规划的分配方法来解决。•任务分配问题的描述•分配方法的求解（表格法）任务分配问题的描述•如果给定几种资源和这些资源的几种用途，以及每种资源应用于这些用途的效果，那么就可以得出有限资源的最优分配。任务分配可用于如下问题：•几种资源分配给几个用途•每种资源必须分配给一个用途，且只分配给一个用途•只能以一个标准衡量（如最低成本等）分配方法的求解（表格法）•步骤：–每行中数字减去该行中最小的数，使每行至少有一个零；–每列中数字减去该列中最小的数；–检查覆盖所有零的最少直线数是否等于N；–在所有未覆盖的数字中减去最小数；–确定最优分配方案。•举例分配方法举例：•有5项任务可以在5台机器上加工（N=5），每台机器的加工各项任务的时间见下表，作业计划人员希望在分配中达到时间最短。1059181113196121432445189121715116141910ABCDE12345每行中数字减去该行中最小的数分配方法举例（1）•每行中数字减去该行中最小的数，得到：•504136•713068•10223•90386•508134每列中数字减去该列中最小的数分配方法举例（2）•每列中数字减去该列中最小的数，得到：•404113•613045•00200•80363•408111分配方法举例（3）•检查覆盖所有零的最少直线数是否等于N；•404113•613045•00200•80363•408111所有未覆盖的数字中减去最小数将此最小数加到所有直线的每一个交叉点的数字上分配方法举例（4）•在所有未覆盖的数字中减去最小数，并将此最小数加到所有直线的每一个交叉点的数字上；•303102•614045•01200•70252•307100分配方法举例（5）•重复第3步；•303102•614045•01200•70252•307100检查覆盖所有零的最少直线数是否等于N重复第4步在所有未覆盖的数字中减去最小数，并将此最小数加到所有直线的每一个交叉点的数字上分配方法举例（5）•重复第4步；•10180•616045•03200•50030•327100在所有未覆盖的数字中减去最小数，并将此最小数加到所有直线的每一个交叉点的数字上分配方法举例（6）•重复第3步；•10180•616045•03200•50030•327100检查覆盖所有零的最少直线数是否等于N在所有未覆盖的数字中减去最小数，并将此最小数加到所有直线的每一个交叉点的数字上分配方法举例（7）•重复第4步；•0*0170•5160*35•0430*1•40*020•22790*分配结果：按行（列）将任务逐一分配给机器，分配后划去该零元素同行（列）的其它元素分配方法举例（7）•任务机器时间•1A10•2C6•3D4•4B9•5E10•作业时间合计39任务分配的目的•是使人对任务或工作对机器的分配所产生的利润、效率、总报酬达到最大化。任务分配•几种资源分配给几个用途•每种资源必须分配给一个用途，且只分配给一个用途•只能以一个标准衡量（如最低成本等）分配方法的求解（表格法）•步骤：–每行中数字减去该行中最小的数，使每行至少有一个零；–每列中数字减去该列中最小的数；–检查覆盖所有零的最少直线数是否等于N；–在所有未覆盖的数字中减去最小数；–确定最优分配方案。生产作业计划的编制•生产作业类型•安排生产负荷•作业排序•多项作业、两台机器的排序•多项作业和多个加工中心的排序作业排序的重要性在排序不恰当的车间，经常会出现作业等待时间占总生产周期的95%，从而造成一个较长的工作流周期，再加上库存时间和其他时间，就会使现金流周期长工作流相当于现金流，而作业排序是整个过程的核心。作业排序是安排作业的活动、资源使用或配置设施的时间表。三、作业排序车间作业排序和计划的关系作业计划和排序的关系1排序,Sequencing决定不同加工件在加工中心的加工顺序;2作业计划Scheduling而作业计划的主要问题不但要确定来件在各台机器上工件的加工顺序，而且，在通常情况下都规定最早可能开工时间和结束时间.但，当工件的加工顺序确定之后，作业计划也就基本确定了。所以，人们常常不加区别地使用“排序”与“作业计划”。作业排序的优先规则1FCFS(First-Come-First-Service)（先到优先）：按订单送到的先后顺序进行加工.2SOT（最短作业时间优先）：这个规则等同于SPT(Shortest-Processing-Time)（最短加工时间）规则。3EDD(Earliest-Due-Date)(交货期优先)：最早交货期最早加工。作业排序的优先规则4.STR(Slack-Time-Ramaining)（剩余时间最短优先、最短任务优先）：剩余时间是指交货期前所剩余时间减去加工时间所得的差值。STR=交货期前所剩余的时间–剩余的加工时间5RAN(Random)(随机排序)主管或操作工通常随意选择一件他们喜欢的进行加工。6LCFS(Last-Come-First-Service)（后到优先）：该规则经常作为缺省规则使用。因为后来的工单放在先来的上面，操作人员通常是先加工上面的工单。N个作业单台工作中心的排序“n个作业——单台工作中心的问题”或“n/1”，理论上，排序问题的难度随着工作中心数量的增加而增大，而不是随着作业数量的增加而增大，对n的约束是其必须是确定的有限的数例：n个作业单台工作中心排序问题。在一周的开始（5天），有5位顾客提交了他们的订单。原始数据为：订单（以到达的顺序）加工时间/天交货期/天ABCDE3426156792讨论•请按以上作业排序规则分别排序，并计算流程时间。哪些订单需延迟交货？延迟多少时间？1、FCFS（先到优先）2、SOT（最短作业时间）3、EDD(最早交货期最先加工)4、LCFS（后到先服务）5、随机规则6、STR（最短任务优先）方案一：FCFS规则方案一利用FCFS规则，其流程时间的结果如下：加工顺序加工时间交货日期流程时间ABCDE34261567920+3=33+4=77+2=99+6=1515+1=16总流程时间=3+7+9+15+16=50（天）平均流程时间=50/5=10天将每个订单的交货日期与其流程时间相比较，发现只有A订单能按时交货。订单B，C，D和E将会延期交货，延期时间分别为1,2,6,14天。每个订单平均延期（0+1+1+2+6+14）/5=4.6天。方案二：SOT规则方案二利用SOT（最短作业时间）规则，流程时间为：加工顺序加工时间交货日期流程时间ECABD12346275690+1=11+2=33+3=66+4=1010+6=16总流程时间=1+3+6+10+16=36（天）平均流程时间=36/5=7.5天SOT规则的平均流程时间比FCFS规则的平均流程时间小。另外，订单E和C将在交货日期前完成，订单A仅延期1天。每个订单的平均延期时间为（0+0+1+4+7）/5=2.4天。方案三：EDD规则加工顺序加工时间交货日期流程时间EABCD13426256790+1=11+3=44+4=88+2=1010+6=16总流程时间=1+4+8+10+16=39（天）平均流程时间=39/5=7.8天在这种情况下，订单B，C和D将会延期，平均延期时间为（0+0+2+3+7）/5=2.4天。方案三利用EDD(最早交货期最先加工)规则，排序结果为方案四：LCFS规则加工顺序加工时间交货日期流程时间EDCBA16243297650+1=11+6=77+2=99+4=1313+3=16总流程时间=1+7+9+13+16=46（天）平均流程时间=46/5=9.2天平均延期=4.0天方案四利用LCFS（后到先服务）规则，预计流程时间为：方案五：随机加工顺序加工时间交货日期流程时间DCAEB62314975260+6=66+2=88+3=1111+1=1212+4=16总流程时间=6+8+11+12+16=55（天）平均流程时间=55/5=11天平均延期=5.4天方案五利用随机规则，排序结果为：方案六：STR规则加工顺序加工时间交货日期流程时间EABDC13462256970+6=61+3=44+4=88+6=1414+2=16总流程时间=6+4+8+14+16=43（天）平均流程时间=43/5=8.6天平均延期=3.2天方案六利用STR（最短任务优先，剩余时间最短优先）规则，排序结果为：优先调度规则比较规则总的完成时间平均完成时间平均延期FCFSSOT(SPT)DDateLCFS随机STR503639465343107.27.89.210.68.64.62.42.44.05.43.2很明显，此例中SOT比其余的规则都好，但情况总是这样的吗？答案是肯定的。另外，从数学上可以证明，在n/1情况下，用其他的评价准则，如等待时间均值和完成时间均值最小，SOT规则也是最优方案。事实上，这个简单被称为“在整个排序学科中最重要的概念”•证明SPT规则可以使n种产品在一台设备上加工的流程时间最短。•证明：假设n种产品按照作业时间由小到大排序，第一个产品的作业时间为t1，第二个产品的作业时间为t2，第n个产品的作业时间为tn，t1t2…tn。•则第一个产品的流程时间为t1•第一个产品的流程时间为t1+t2•…..•第n个产品的流程时间为niit1•总的流程时间为T=nt1+(n-1)t2+…+2tn-1+tn•现调换n个产品中任意两件（第h件和第m件）的加工顺序，thtm，则总流程时间变为：•T`=nt1+…+(n-h+1)tm+…+(n-m+1)th+…+tn•T`-T=(m-h)(tm-th)0•因此，SPT规则的总流程时间最短。生产作业计划的编制•生产作业类型•安排生产负荷•作业排序•多项作业、两台机器的排序多项作业和多个加工中心的排序四、多项作业、两台机器的排序多项作业和多个加工中心的排序--Johnson方法•N项作业，2台机器，所有工件的加工路线都相同。（S.M.Johnson，1954）AB•目标：使全部完工时间最小。•条件：每种工件在每台机器上的加工时间均为已知。Johnson方法•步骤：–1.选择最短的作业时间；–2.如果最短时间的作业在第1个加工中心，则安排在最前面，若在第2个加工中心，则安排在最后；–3.在等待的队列中，取消第2步安排了的作业；–4.重复1，2，3步。N个作业两台工作中心排序S.M.Johnson提出了一个排序方法，其目的是极小化从第一个作业开始到最后一个作业为止的全部流程时间。约翰逊规则包含下列几个步骤：A.列出每个作业在两台工作中心上的作业时间表；B.找出最短的作业时间；C.如果最短的作业时间来自第一台工作中心，则将它排到前面；如果最短的作业时间来自第二个工作中心，则将该作业排到最后；D.对剩余作业重复进行步骤A和B，直到排序完成。n种零件由2台设备加工•编号车床铣床加工加工A511B89C103D42E76•原则：•1.找min，前道工序--最前•后道工序--最后•2.若多个min,任选。•D•C--D•A----------C--D•A------E--C--D•A--B--E--C--D例题1•某工厂有5项特殊的工作需通过两个生产中心的操作，各项工作的操作时间如表。为使5项工作总周期时间最小化，找出各项工作的操作排序。工作生产中心1/h生产中心2/hA51B67C83D147E912•约翰逊规则:•B-E-D-C-AN个作业两台工作中心排序约翰逊规则还可以扩展到3台设备的情况，这3台设备（A，B，C）必须满足以下两个条件之一：（1）A设备的最小加工时间大于或等于B设备的任一加工时间。（2）C设备的最小加工时间大于或等于B设备的任一加工时间。•3台设备简化为