作业排序(生产时间组织)

第十一章作业排序（生产过程时间组织）,生产过程时间组织的目标：减少时间损失，缩短生产周期，提高生产效率，降低在制品占用量，提高生产效益。,流水作业排序问题,流水车间(Flowshop):工件的加工路线都一致。相同零件、不同移动方式下加工周期N项任务单台机器的作业排序问题N项任务两台机器排序问题的最优算法N项任务m台设备排序问题的启发式算法,相同零件不同移动方式下加工周期的计算,当n个零件相同，则无排序问题。但不同移动方式下的加工周期不同三种典型的移动方式顺序移动方式：平行移动方式：平行顺序移动方式,一批零件在上道工序全部加工完毕后才整批地转移到下道工序继续加工。即零件在工序间是整批地移动。,工序,M1,t4,t1,t1,t1,t1,t2,t2,t2,t2,M2,M3,t3,t3,t3,t3,M4,t4,t4,t4,时间,Tp,nt1,nt4,nt3,nt2,Tp=nt1+nt2+nt3+nt4故：Tp=nti,m,i=1,（一）顺序移动方式,设零件批量为n（件），工序数目为m，一批零件不计算工序间运输时间，只考虑加工时间，设其加工的周期为T（分钟），零件在i道工序的单件工时为（分钟/件），i=1.2n.则该批零件的加工周期为：,顺序移动方式（续）,（二）平行移动方式,每个零件在前道工序加工完毕后，立即转移到后道工序去继续加工。即零件在工序间1件1件地移动。,工序,M1,M2,M3,M4,时间,t1,t1,t1,t1,t2,t2,t2,t2,t3,t3,t3,t3,t4,t4,t4,t4,t1,t2,t3,t4,(n-1)t3,To,To=t1+t2+t3+t4+(n-1)t3故：To=ti+(n-1)tLtL为最长的单件工序时间,m,i=1,平行移动方式（续）,零件平行移动的加工周期为：,（三）平行顺序移动方式,顺序移动方式下，零件搬运次数少，设备连续加工，利用率高，但加工周期长；平行移动方式下，加工周期短，但零件搬运频繁，设备间歇性加工，不便利用。平行顺序移动方式将两者的优点结合起来，既要求每道工序的设备连续加工，又要求各道工序尽可能平行地加工。（1）当titi+1时，按平行移动方式移动；（2）当titi+1时，以i工序最后一个零件的完工时间为基准，往前推移(n-1)ti+1作为零件在(i+1)工序的开始加工时间。,020406080100120140160,M1M2M3M4,T平顺,平行顺序移动方式,三种移动方式的比较,第二节生产过程任务排序,一、流水型排序问题n项任务，等待多台串联设备组成的生产线加工，各项任务的工艺顺序相同。1、n项任务，单台设备(一个单位)的排序。例：8项任务、单台设备，资料如下：,1)、最小加工时间规则(SPT),按各任务加工时间的大小，从小大到排序。本规则可得到最小平均流程时间，最小平均在制品占用量。但可能出现延期交货。,平均流程时间：,2)EDD规则（最早交货期规则）,按任务规定的交货期先后，从小到大排序。可使交货延期量最小化，但平均流程时间相对较大，平均在制品数较大。,平均流程时间,最大交货延期量为零,3）、EDD-SPT综合规则：按EDD规则排序所的方案的基础上，按SPT规则对其调整。,1、找出最大流程时间maxFi2、找出满足条件：djmaxFi的任务，当满足条件的任务只有一项时，该任务不调整，当满足条件的任务有多项时，对这些任务按SPT规则调整。去掉已调整的任务，对剩余任务反复用第二步直至所有任务调整完,平均流程时间,最大交货延期量为零,2、N项任务、两台设备的排序,N项任务，均按Ma-Mb的工艺顺序加工，要求最大流程时间最小化的最优排序方案。,用约翰孙-贝尔曼规则求解1、找出最小加工时间，如果该时间在第一台设备行，则对应的任务最先加工，若在第二台设备行，则对应的任务排在最后加工；2、去掉已排序任务，对剩下的任务反复应用第1步，直至所有任务排完。按约-贝规则对上例进行排序，得到排序结果如下：,J8-J7-J6-J1-J3-J5-J4-J2,用哈姆表算法，求得各任务在各设备上的完工时间如下表：,排序前的流程时间计算,2、N项任务、三台设备的排序例：三台设备、8项任务，各任务的工艺顺序相同，资料如下：,求最优解条件，满足如下条件之一：,求解步骤：1、把三台设备转换为两台假象设备，假想设备加工时间按如下公式转换：,用约-贝规则求得排序结果如下：,J8-J2-J5-J6-J1-J3-J7-J4；(或：-J4-J7）,上例中，满足条件,转换两台假想设备，结果如下表：,用哈姆表算法分别计算两方案的流程时间：,J8-J2-J5-J6-J1-J3-J7-J4；,J8-J2-J5-J6-J1-J3-J4-J7,按自然顺序加工的流程时间计算,4、N项任务，m台设备的排序方法：例：8项任务，须经6台设备加工，求最优加工顺序：,1）、关键任务法：求出各项任务的总加工时间；以总加工时间最大者为关键任务JC；找出：t1,jtm,j的任务，按tm,j从大到小排在JC后面；t1,j=tm,j的任务，排在JC紧前或紧后。求上例加工顺序：,关键零件：Jc=J5满足t1,jtm,j的零件有：J1、J3，按tm,j从大到小排在J5之后。得到加工顺序：J8-J4-J7-J6-J2-J5-J1-J3用哈姆