作业计划排序方法幻灯片

第8章生产作业计划第二节作业排序作业排序一、基本概念二、最长流程时间三、n/1/Fmax问题四、n/2/F/Fmax问题的算法五、一般n/m/P/Fmax问题的启发式算法六、单件车间排序问题一、基本概念1、排序排序就是要将不同的工作任务安排一个执行的顺序，使预定的目标最优化。实际上就是要解决如何按时间的先后，将有限的人力、物力资源分配给不同工作任务，使预定目标最优化的问题。一、基本概念排序中常用的几个概念工件（Job）：代表服务对象，工件可以是单个工件，也可以是一批相同的工件。机器（Machine）：服务者。加工路线（Process）：是工件加工经过不同机器构成的路线。比如，某工件要经过车、钻、冲、磨得路线加工，可以用M1，M2，M3，M4表示。加工顺序：表示每台机器加工n个工件的优先顺序，是排序要解决的问题。可用一组工件代号的一种排列来表示。如可用（1，6，5，4，3，2）表示加工顺序：J1—J6—J5—J4—J3—J2。2、作业计划（Scheduling）作业计划与排序不是一回事，它不仅要确定工件的加工顺序，而且还要确定每台机器加工每个工件的开工时间和完工时间。如果按最早可能开（完）工时间来编排作业计划，则排序完后，作业计划也就确定了。3、排序问题的分类排序问题分类按机器个数按工件到达车间的情况按参数按目标函数的性质分类多台机器排序问题单台机器排序问题单件作业排序问题流水线作业排序问题动态的排序问题静态的排序问题随机型排序问题确定型排序问题流水作业问题和单件作业排序问题的基本特征流水作业排序问题的基本特征：每个工件的加工路线都一样。如车—铣—磨。这里指的是工件的加工流向一致，并不要求每个工件必须在每台机器上加工。如有的工件为车—磨，有的为铣—磨。不仅加工路线一致，而且所有工件在各台机器上的加工顺序也一样，这种排序称为排列排序（同顺序排序）。如工件排序为：J1—J3—J2，则表示所有机器都是先加工J1，然后加工J3，最后加工J2。单件作业排序问题的基本特征：每个工件都有其独特的加工路线，工件没有一定的流向。排序问题的表示方法——n/m/A/Bn：工件数；

m：机器数；

A：作业类型；

“F”代表流水作业排序问题，工件的加工流向一致，并不要求每个工件必须在每台机器上加工。

“P”代表流水作业排列排序问题，即同顺序排序，所有零件在每台机器上的加工顺序相同。

“G”代表一般单件作业排序问题。

当m=1时，则A处为空白。B：目标函数，通常是使其值最小。排序问题的表示方法——n/m/A/Bn/1/Fmax：所有工件在一台机器上加工。n/m/P/Fmax：所有工件流向相同，在每台机器上的加工顺序相同。n/m/F/Fmax：所有工件流向相同，不同工件在每台机器上的加工顺序不同。如零件1在M1上不加工，在M2上才是第一道工序；而零件2在M1上是第一道工序。n/m/G/Fmax：所有工件的加工路线都不相同，工件没有流向。排序问题的表示方法——n/m/A/B

一般来说，排列排序n/m/P/Fmax问题的最优解不一定是相应流水车间排序问题的最优解，但一般是比较好的解。而对于仅有2台或3台机器的情况，则排列排序问题的最优解一定是相应流水车间排序问题的最优解。4、排序问题的假设条件一个工件不能同时在几台不同的机器上加工。工件在加工过程中采取平行移动方式。不允许中断。每道工序只在一台机器上完成。每台机器同时只能加工一个工件。工件数、机器数和加工时间已知，加工时间与加工顺序无关。4、排序问题的假设条件一个工件不能同时在几台不同的机器上加工。工件在加工过程中采取平行移动方式。不允许中断。每道工序只在一台机器上完成。每台机器同时只能加工一个工件。工件数、机器数和加工时间已知，加工时间与加工顺序无关。二、最长流程时间最长流程时间（Fmax加工周期）：从第一个工件在第一台机器上加工起到最后一个工件在最后一台机器上加工完毕为止所经过的时间。假定所有工件的到达时间都为0，则Fmax等于排在末位加工的工件在车间的停留时间。二、最长流程时间计算Fmax的几个假定条件：机器M1不会发生空闲；对其它机器，能对某一工件加工其相应工序，必须具备2个条件：机器必须完成排前一位的工件的加工；要加工的工件的上道工序已经完工。本工件在该设备上的开始时间：Btime=max（T零件前序完成时间，T该设备前工件完成时间）Etime=Btime+PijBtime本工序开始时间，Etime为本工序结束时间。二、最长流程时间Ji----工件i，i=1,2,..n。Mj----机器j，j＝1，2，…，m.di----工件Ji的完工期限。pij----工件Ji在机器Mj上的加工时间,j=1,…,mPi----工件Ji的加工时间,wij----工件Ji在机器Mj前的等待时间,j=1,…,mWi----工件Ji在加工过程中总的等待时间,二、最长流程时间

Ci----工件Ji的完成时间,Fi----工件Ji的流程时间，即工件在车间的实际停留时间，在工件都已到达的情况下,Fi=Pi+WiLi----工件Ji的延误时间,Li=Ci-di,Li<=0按期或完成提前；Li>0延误Fmax----最长流程时间，Fmax＝max{Fi}三、n/1/Fmax问题优先调度规则按优先调度规则挑选工序比随意挑选一道工序的方法更能符合计划编制者的要求，同时又不必列出所有可能的作业计划，从而计算量小。迄今为止，人们提出了100多个调度规则，其中主要有以下几个。SPT(ShortestProcessingTime)法则：优先选择加工时间最短的工序。FCFS(FirstComeFirstServed)法则：优先选择最早进入可排工序集合的工件。EDD(EarliestDueDate)法则：优先选择完工期限紧的工件。MWKR(MostWorkRemaining)法则：优先选择余下加工时间最长的工件。LWKR(LeastWorkRemaining)法则：优先选择余下加工时间最短的工件。MOPNR(MostOperationsRemaining)法则：优先选择余下工序数最多的工件。优选排序法则按SPT法则可使工件的平均流程时间最短，从而减少在制品量。FCFS法则来自排队论，它对工件较公平。EDD法则可使工件最大延误时间最小。MWKR法则使不同工作量的工件的完工时间尽量接近。LWKR法则，使工作量小的工件尽快完成。MOPNR法则与MWKR法则类似，只不过考虑工件在不同机器上的转运排队时间是主要的。三、n/1/Fmax问题n个作业单台工作中心的排序目标——（1）平均流程时间最短。若n个作业按照优先规则已排定顺序，则任何一个作业，假定排在第k位，第k作业的流程时间Fk总的流程时间为：相应的目标函数为即总流程时间最短。其中，pi表示作业i的加工时间；则全部作业的平均流程时间为：三、n/1/Fmax问题n个作业单台工作中心的排序目标——（2）最大延迟时间、总延迟时间（或平均延迟时间）为最小。单个作业的延迟时间为Li，如果以最大延迟时间为最小，则其目标函数为：minLmax=max{Li}（i=1,2，．．，n）

三、n/1/Fmax问题例：现有5个订单（任务）需要在一台机器上加工，5个订单的到达顺序为A，B，C，D，E。相关数据如下：订单（以到达的顺序）工时间(天)交货期(天)ABCDE3426156792分析：分别采用FCFS（先到先服务）规则、最短加工时间SPT规则、交货期EDD规则、后到先服务LCFS规则进行排序，并对排序的结果进行比较分析。三、n/1/Fmax问题方案一 利用先到先服务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天。每个订单平均延期（1+2+6+14）/5=4.6天。三、n/1/Fmax问题方案二 利用最短加工时间SPT规则，流程时间为：

加工顺序加工时间交货日期流程时间12346275690+1=11+2=33+3=66+4=1010+6=16ECABD总流程时间=1+3+6+10+16=36（天）平均流程时间=36/5=7.2天SPT规则的平均流程时间比FCFS规则的平均流程时间小。另外，将每个订单的交货日期与其流程时间相比较，订单E和C将在交货日期前完成。订单A，B，D,延期时间分别为1,4,7天。每个订单的平均延期时间为（0+0+1+4+7）/5=2.4天。三、n/1/Fmax问题总流程时间=1+4+8+10+16=39（天）平均流程时间=39/5=7.8天订单B，C和D将会延期2,3,7天，每个订单的平均延期时间为:（0+0+2+3+7）/5=2.4天。方案三 利用最早交货期先加工EDD规则，排序结果为：

加工顺序加工时间交货日期流程时间E

ABC1=11+3=44+4=88+2=1010+6=16三、n/1/Fmax问题

加工顺序加工时间交货日期流程时间EDCB

A16243297650+1=11+6=77+2=99+4=1313+3=16总流程时间=1+7+9+13+16=46（天）平均流程时间=46/5=9.2天平均延期（0+0+2+7+11）/5=4.0天方案四 利用后到先服务LCFS规则，预计流程时间为：三、n/1/Fmax问题很明显，此例中最短加工时间SPT比其余的规则都好，但情况总是这样的吗？答案是肯定的。另外，从数学上可以证明，在n/1情况下，用其他的评价准则，如等待时间均值和完成时间均值最小，SPT规则都能获得最佳的方案，所以，该规则被称为“在整个排序学科中最重要的概念”。

规则总流程（完成）时间平均完成时间平均延期FCFSSPTEDDLCFS50363946107.27.89.24.62.42.44.0四、n/2/F/Fmax问题的算法Johnson算法：假定：ai为工件Ji在机器M1上的加工时间，bi为工件Ji在机器M2上的加工时间，每个工件按M1—M2的路线加工。四、n/2/F/Fmax问题的算法Johnson算法的步骤：从加工时间矩阵中找出最短的加工时间。若最短时间出现在M1上，则对应的工件尽可能往前排。若最短时间出现在M2上，则对应的工件尽可能往后排。若最短时间有多个，则任选一个。划去已排序的工件。若所有工件都已排序，则停止，否则重复上述步骤。四、n/2/F/Fmax问题的算法四、n/2/F/Fmax问题的算法将工件2排在第1位

2将工件3排在第6位

2

3将工件5排在第2位

2

5

3将工件6排在第3位

2

5

6

3将工件4排在第5位

2

5

6

4

3将工件1排在第4位

2

5

6

1

4

3最优加工顺序为S=(2,5,6,1,4,3),Fmax=28I12345615185342722474四、n/2/F/Fmax问题的算法工件最优加工顺序256143M11(1)3(4)4(8)5(8-13)5(18)8(26)M22(3)7(11)4(15)7(22)4(26)2(28)某工件的工序开工时间和完工时间确定：Btime=max（T零件前序完成时间，T该设备前工件完成时间）Etime=Btime+PijBtime本工序开始时间，Etime为本工序结束时间。Fmax=28五、一般n/m/P/Fmax问题的启发式算法n/m/P/Fmax问题：五、一般n/m/P/Fmax问题的启发式算法iPi1Pi2Pi3Pi4615243255144544453258217533674261012131671115202733121722303542132125323846右上角为该工序结束时间Fmax=46五、一般n/m/P/Fmax问题的启发式算法iPi1Pi2Pi3Pi414635244541753255136744453258245710141681520263035132025333846172326374148Fmax=48五、一般n/m/P/Fmax问题的启发式算法

对于一般的n/m/P/Fmax问题，可以用分支定界法求得最优解，但计算量很大。实际中，可以用启发式算法求近优解。五、一般n/m/P/Fmax问题的启发式算法1、Palmer法n作业m机器排程的Palmer启发式算法，是基于作业的加工时间按斜度顺序指标排列作业的启发式算法。按机器的顺序，加工时间趋于增加的作业被赋予较大的优先权数。

五、一般n/m/P/Fmax问题的启发式算法1、Palmer法计算工件斜度指标i：

m:机器数

pik

：工件i在机器k上的加工时间。

i=1,2,,n排序方法:按i从大到小的顺序排列。按排序的顺序计算Fmax五、一般n/m/P/Fmax问题的启发式算法2、关键工件法：计算Pi=Pij

，找出Pi最长的工件，将之作为关键工件C。对其余工件，若Pi1≤Pim

，则按Pi1由小到大排成序列SA。若Pi1>Pim

，则按Pim由大到小排成序列SB。顺序（SA，C，SB）即为近优解。五、一般n/m/P/Fmax问题的启发式算法关键工件为3SA=（1，2）SB=（4）近似最优解（1，2，3，4）Fmax=28五、一般n/m/P/Fmax问题的启发式算法λi＝＝-2Pi1+2Pi3λ1＝-2P11+2P13=-2＋8＝6λ2＝-2P21+2P23=-4+10=6λ3＝-2P31+2P33=-12+16=4λ4＝-2P41+2P43=-6+4=-2按λi不增的顺序排列工件，得到加工顺序（1，2，3，4）和（2，1，3，4），Fmax=28k=1，2，3五、一般n/m/P/Fmax问题的启发式算法3、CDS法：CDS法是Johnson算法的扩展方法，被认为是好的具有鲁棒性的启发式算法；算法步骤：

将m台机器分组，产生m-1个两台机器问题的集合；然后利用Johnson算法获得m-1个加工顺序(每个两台机器问题获得一个加工顺序)；

选取这m-1个加工顺序中考核指标最好（一般为Makespan最短）的加工顺序作为近似最优调度解；

五、一般n/m/P/Fmax问题的启发式算法3、CDS法：CDS法是Johnson算法的扩展方法，从M-1个排序中找出近优解。五、一般n/m/P/Fm