1、l 排序排序就是要将不同的工作任务安排一个就是要将不同的工作任务安排一个执行的顺序，使预定的目标最优化。执行的顺序，使预定的目标最优化。l 实际上实际上就是要解决如何按时间的先后，就是要解决如何按时间的先后，将有限的人力、物力资源分配给不同工将有限的人力、物力资源分配给不同工作任务，使预定目标最优化的问题。作任务，使预定目标最优化的问题。l 生产作业排序就是指对于等候某个设备或工作中心加工的多个任务，确定这些任务加工的先后次序。l 目的目的 提高设备或工作中心的效率 减少在制品占用量 保证按期交货 缩短生产周期u工件（工件（Job）：）：代表服务对象，工件可以是单个工件，也可以是一批相同的工件
2、。u机器（机器（Machine）：）：服务者。u加工路线（加工路线（Process）：）：是工件加工经过不同机器构成的路线。比如，某工件要经过车、钻、冲、磨得路线加工，可以用M1，M2，M3，M4表示。u加工顺序加工顺序：表示每台机器加工n个工件的优先顺序，是排序要解决的问题。可用一组工件代号的一种排列来表示。如可用（1，6，5，4，3，2）表示加工顺序：J1J6J5J4J3J2。u作业计划与排序不是一回事，它不仅要确定作业计划与排序不是一回事，它不仅要确定工件的加工顺序，而且还要确定每台机器加工件的加工顺序，而且还要确定每台机器加工每个工件的开工时间和完工时间。工每个工件的开工时间和完工时间
3、。u如果按最早可能开（完）工时间来编排作业如果按最早可能开（完）工时间来编排作业计划，则排序完后，作业计划也就确定了。计划，则排序完后，作业计划也就确定了。按工件到达车间的情况按工件到达车间的情况按参数按参数按目标函数的性质分类按目标函数的性质分类动态的排序问题动态的排序问题静态的排序问题静态的排序问题随机型排序问题随机型排序问题确定型排序问题确定型排序问题流水作业问题和单件作业排序问题的基本特征流水作业问题和单件作业排序问题的基本特征流水作业排序问题的基本特征：流水作业排序问题的基本特征：u每个工件的加工路线都一样。如车铣磨。这里指的是工件的加工流向一致，并不要求每个工件必须在每台机器上加工
4、。如有的工件为车磨，有的为铣磨。u不仅加工路线一致，而且所有工件在各台机器上的加工顺序也一样，这种排序称为排列排序（同顺序排序）。如工件排序为：J1J3J2，则表示所有机器都是先加工J1，然后加工J3，最后加工J2。单件作业排序问题的基本特征：单件作业排序问题的基本特征：u每个工件都有其独特的加工路线，工件没有一定的流向。n/m/A/B n：工件数；：工件数；m：机器数；：机器数；A：作业类型；：作业类型；“F”代表流水作业排序问题，工件的加工流代表流水作业排序问题，工件的加工流向一致，并不要求每个工件必须在每台机器上加向一致，并不要求每个工件必须在每台机器上加工。工。“P”代表流水作业排列排
5、序问题，即同顺序代表流水作业排列排序问题，即同顺序排序，所有零件在每台机器上的加工顺序相同。排序，所有零件在每台机器上的加工顺序相同。“G”代表一般单件作业排序问题。代表一般单件作业排序问题。当当m=1时，则时，则A处为空白。处为空白。B：目标函数，：目标函数，通常是使其值最小。通常是使其值最小。n/m/A/Bln/1/Fmax：所有工件在一台机器上加工。：所有工件在一台机器上加工。ln/m/P/Fmax：所有工件流向相同，在每台机器上：所有工件流向相同，在每台机器上的加工顺序相同。的加工顺序相同。ln/m/F/Fmax：所有工件流向相同，不同工件在每：所有工件流向相同，不同工件在每台机器上的
6、加工顺序不同。如零件台机器上的加工顺序不同。如零件1在在M1上不加上不加工，在工，在M2上才是第一道工序；而零件上才是第一道工序；而零件2在在M1上是上是第一道工序。第一道工序。ln/m/G/Fmax：所有工件的加工路线都不相同，工：所有工件的加工路线都不相同，工件没有流向。件没有流向。n/m/A/B 一般来说，排列排序一般来说，排列排序n/m/P/Fmax问题的最优问题的最优解不一定是相应流水车间排序问题的最优解，解不一定是相应流水车间排序问题的最优解，但一般是比较好的解。而对于仅有但一般是比较好的解。而对于仅有2台或台或3台台机器的情况，则排列排序问题的最优解一定机器的情况，则排列排序问题
7、的最优解一定是相应流水车间排序问题的最优解。是相应流水车间排序问题的最优解。u一个工件不能同时在几台不同的机器上加工。一个工件不能同时在几台不同的机器上加工。u工件在加工过程中采取平行移动方式。工件在加工过程中采取平行移动方式。u不允许中断。不允许中断。u每道工序只在一台机器上完成。每道工序只在一台机器上完成。u每台机器同时只能加工一个工件。每台机器同时只能加工一个工件。u工件数、机器数和加工时间已知，加工时间与加工工件数、机器数和加工时间已知，加工时间与加工顺序无关。顺序无关。u一个工件不能同时在几台不同的机器上加工。一个工件不能同时在几台不同的机器上加工。u工件在加工过程中采取平行移动方式
8、。工件在加工过程中采取平行移动方式。u不允许中断。不允许中断。u每道工序只在一台机器上完成。每道工序只在一台机器上完成。u每台机器同时只能加工一个工件。每台机器同时只能加工一个工件。u工件数、机器数和加工时间已知，加工时间与加工工件数、机器数和加工时间已知，加工时间与加工顺序无关。顺序无关。u最长流程时间（最长流程时间（Fmax加工周期）：从第一个加工周期）：从第一个工件在第一台机器上加工起到最后一个工件在工件在第一台机器上加工起到最后一个工件在最后一台机器上加工完毕为止所经过的时间。最后一台机器上加工完毕为止所经过的时间。u假定所有工件的到达时间都为假定所有工件的到达时间都为0，则，则Fma
9、x等于等于排在末位加工的工件在车间的停留时间排在末位加工的工件在车间的停留时间。计算计算Fmax的几个假定条件：的几个假定条件：u机器机器M1不会发生空闲；不会发生空闲；u对其它机器，能对某一工件加工其相应工序，必须具备对其它机器，能对某一工件加工其相应工序，必须具备2个条件：个条件：u Ji-工件工件i，i=1,2,.n。u Mj-机器机器j，j1，2，m.u di-工件工件Ji 的完工期限。的完工期限。u pij-工件工件Ji在机器在机器Mj上的加工时间上的加工时间,j=1,m u Pi-工件工件Ji的加工时间的加工时间,u wij-工件工件Ji在机器在机器Mj前的等待时间前的等待时间,j
10、=1,m u Wi-工件工件Ji在加工过程中总的等待时间在加工过程中总的等待时间,u Ci-工件工件Ji 的完成时间的完成时间,u Fi-工件工件Ji 的流程时间，即工件在车间的实际停的流程时间，即工件在车间的实际停留时间，在工件都已到达的情况下留时间，在工件都已到达的情况下,Fi=Pi+Wi u Li-工件工件Ji 的延误时间的延误时间,Li=Ci-di,Li0 延误延误u Fmax-最长流程时间，最长流程时间，FmaxmaxFi按优先调度规则挑选工序比随意挑选一道工序的方法更能符合计划编按优先调度规则挑选工序比随意挑选一道工序的方法更能符合计划编制者的要求，同时又不必列出所有可能的作业计划
11、，从而计算量小。制者的要求，同时又不必列出所有可能的作业计划，从而计算量小。迄今为止，人们提出了迄今为止，人们提出了100多个调度规则，其中主要有以下几个。多个调度规则，其中主要有以下几个。uSPT(Shortest Processing Time)法则：优先选择加工时间最短的工序。法则：优先选择加工时间最短的工序。uFCFS(First Come First Served)法则：优先选择最早进入可排工序法则：优先选择最早进入可排工序集合的工件。集合的工件。uEDD(Earliest Due Date)法则：优先选择完工期限紧的工件。法则：优先选择完工期限紧的工件。uMWKR(Most Wor
12、k Remaining)法则：优先选择余下加工时间最长法则：优先选择余下加工时间最长的工件。的工件。uLWKR(Least Work Remaining)法则：优先选择余下加工时间最短法则：优先选择余下加工时间最短的工件。的工件。uMOPNR(Most Operations Remaining)法则：优先选择余下工序数法则：优先选择余下工序数最多的工件。最多的工件。u按按SPT法则可使工件的平均流程时间最短，从而减少法则可使工件的平均流程时间最短，从而减少在制品量。在制品量。uFCFS法则来自排队论，它对工件较公平。法则来自排队论，它对工件较公平。uEDD法则可使工件最大延误时间最小。法则可使
13、工件最大延误时间最小。uMWKR法则使不同工作量的工件的完工时间尽量接法则使不同工作量的工件的完工时间尽量接近。近。LWKR法则，使工作量小的工件尽快完成。法则，使工作量小的工件尽快完成。uMOPNR法则与法则与MWKR法则类似，只不过考虑工件法则类似，只不过考虑工件在不同机器上的转运排队时间是主要的。在不同机器上的转运排队时间是主要的。n n个作业单台工作中心的排序目标个作业单台工作中心的排序目标若若n n个作业按照优先规则已排定顺序，则任何一个作业，假定排在个作业按照优先规则已排定顺序，则任何一个作业，假定排在第第k k位，第位，第k k作业的流程时间作业的流程时间F Fk kkiikpF
14、1nkkF1总的流程时间为：总的流程时间为：npinnpnFFniinkkiinkk1111)1(相应的目标函数为相应的目标函数为 即总流程时间最短。即总流程时间最短。Fmin其中，其中，p pii表示作业表示作业ii的加工时间；的加工时间；则全部作业的平均流程时间为：则全部作业的平均流程时间为：n n个作业单台工作中心的排序目标个作业单台工作中心的排序目标（2 2）最大延迟时间、总）最大延迟时间、总延迟时间（或平均延迟时间）为最小。延迟时间（或平均延迟时间）为最小。单个作业的延迟时间为单个作业的延迟时间为Li，如果以最大延迟时间为最小，则其目，如果以最大延迟时间为最小，则其目标函数为：标函数
15、为：min Lmax=maxLi （i=1,2，n）例：现有例：现有5 5个订单（任务）需要在一台机器上加工，个订单（任务）需要在一台机器上加工，5 5个订单的个订单的到达顺序为到达顺序为A A，B B，CC，D D，E E。相关数据如下：。相关数据如下：订单（以到达的顺序）订单（以到达的顺序）工时间工时间(天天)交货期交货期(天天)A AB BCCD DE E3 34 42 26 61 15 56 67 79 92 2分析：分别采用分析：分别采用进行排序，并对排序进行排序，并对排序的结果进行比较分析。的结果进行比较分析。加工顺序加工顺序 加工时间加工时间 交货日期交货日期 流程时间流程时间A
16、 AB BCCD DE E3 34 42 26 61 15 56 67 79 92 20+3=30+3=33+4=73+4=77+2=97+2=99+6=159+6=1515+1=1615+1=16总流程时间总流程时间=3+7+9+15+16=50=3+7+9+15+16=50（天）（天）;平均流程时间平均流程时间=50/5=10=50/5=10天天;将每个订单的交货日期与其流程时间相比较，发现只有A订单能按时交货。订单B，C，D和E将会延期交货，延期时间分别为1,2,6,14天。每个订单平均延期（每个订单平均延期（1+2+6+141+2+6+14）/5=4.6/5=4.6天。天。加工顺序加工
17、顺序 加工时间加工时间 交货日期交货日期 流程时间流程时间12346275690+1=11+2=33+3=66+4=1010+6=16ECABD总流程时间总流程时间=1+3+6+10+16=36=1+3+6+10+16=36（天）（天）平均流程时间平均流程时间=36/5=7.2=36/5=7.2天天SPT规则的平均流程时间比FCFS规则的平均流程时间小。另外，将每个订单的交货日期与其流程时间相比较，订单E和C将在交货日期前完成。订单A，B，D,延期时间分别为1,4,7天。每个订单的平均延期时间为（每个订单的平均延期时间为（0+0+1+4+70+0+1+4+7）/5=2.4/5=2.4天。天。总
18、流程时间总流程时间=1+4+8+10+16=39=1+4+8+10+16=39（天）（天）平均流程时间平均流程时间=39/5=7.8=39/5=7.8天天订单B，C和D将会延期2,3,7天，每个订单的平均延期时间为每个订单的平均延期时间为:（0+0+2+3+70+0+2+3+7）/5=2.4/5=2.4天。天。加工顺序加工顺序 加工时间加工时间 交货日期交货日期 流程时间流程时间EABCD13426256790+1=11+3=44+4=88+2=1010+6=16 加工顺序加工顺序 加工时间加工时间 交货日期交货日期 流程时间流程时间E ED DCCB BA A1 16 62 24 43 32
19、 29 97 76 65 50+1=10+1=11+6=71+6=77+2=97+2=99+4=139+4=1313+3=1613+3=16总流程时间总流程时间=1+7+9+13+16=46=1+7+9+13+16=46（天）（天）平均流程时间平均流程时间=46/5=9.2=46/5=9.2天天平均延期（平均延期（0+0+2+7+110+0+2+7+11）/5=4.0/5=4.0天天l 很明显，此例中最短加工时间很明显，此例中最短加工时间SPTSPT比其余的规则都好，但情况总是这样的比其余的规则都好，但情况总是这样的吗？答案是肯定的。吗？答案是肯定的。l 另外，从数学上可以证明，在另外，从数学
20、上可以证明，在n/1n/1情况下，用其他的评价准则，如等待时情况下，用其他的评价准则，如等待时间均值和完成时间均值最小，间均值和完成时间均值最小，SPTSPT规则都能获得最佳的方案，所以，该规规则都能获得最佳的方案，所以，该规则被称为则被称为“在整个排序学科中最重要的概念在整个排序学科中最重要的概念”。规则规则 总流程（完成）时间总流程（完成）时间 平均完成时间平均完成时间 平均延期平均延期FCFSSPTEDDLCFS50363946107.27.89.24.62.42.44.0u假定：ai为工件Ji在机器M1上的加工时间，bi为工件Ji在机器M2上的加工时间，每个工件按M1M2的路线加工。u
21、从加工时间矩阵中找出最短的加工时间。u若最短时间出现在M1上，则对应的工件尽可能往前排。u若最短时间出现在M2上，则对应的工件尽可能往后排。u若最短时间有多个，则任选一个。u划去已排序的工件。u若所有工件都已排序，则停止，否则重复上述步骤。u将工件2排在第1位 2u将工件3排在第6位 2 3u将工件5排在第2位 2 5 3u将工件6排在第3位 2 5 6 3u将工件4排在第5位 2 5 6 4 3u将工件1排在第4位 2 5 6 1 4 3u最优加工顺序为S=(2,5,6,1,4,3),Fmax=28 I 1 2 3 4 5 6 1 5 1 8 5 3 4 2 7 2 2 4 7 4工件最工件
22、最优加工优加工顺序顺序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)Fmax=28：iPi1Pi2Pi3Pi4615243255144544453258217533674261012131671115202733121722303542132125323846右上角为该工序结束时间右上角为该工序结束时间Fmax=46iPi1Pi2Pi3Pi414635244541753255136744453258245710141681520263035132025333846172326374148Fmax=48 对
23、于一般的对于一般的n/m/P/Fmax问题，可以用分问题，可以用分支定界法求得最优解，但计算量很大。实支定界法求得最优解，但计算量很大。实际中，可以用启发式算法求近优解际中，可以用启发式算法求近优解。1 1、PalmerPalmer法法 n作业作业m机器排程的机器排程的Palmer启发式算法，是启发式算法，是基于作业的加工时间按斜度顺序指标排列作基于作业的加工时间按斜度顺序指标排列作业的启发式算法。按机器的顺序，业的启发式算法。按机器的顺序，加工时间加工时间趋于增加的作业被赋予较大的优先权数趋于增加的作业被赋予较大的优先权数。1 1、PalmerPalmer法法u计算工件斜度指标计算工件斜度指
24、标 i i：m:m:机器数机器数 p pikik ：工件：工件i i在机器在机器k k上的加工时间。上的加工时间。i=1,2,i=1,2,n,nu排序方法排序方法:按按 i i从大到小的顺序排列。从大到小的顺序排列。u按排序的顺序计算按排序的顺序计算FmaxFmaxmkikipmk11-22 2、关键工件法、关键工件法：u计算计算Pi=Pij，找出，找出Pi最长的工件，将之作为最长的工件，将之作为关键工件关键工件C。u对其余工件，若对其余工件，若Pi1Pim，则按，则按Pi1由小到大排由小到大排成序列成序列SA。若若Pi1 Pim，则按，则按Pim由大到小排成由大到小排成序列序列SB。u顺序（
25、顺序（SA，C，SB）即为近优解。）即为近优解。关键工件为关键工件为3SA=（1，2）SB=（4）近似最优解（近似最优解（1，2，3，4）Fmax=28i -2Pi1+2Pi31-2P11+2P13=-2862-2P21+2P23=-4+10=63-2P31+2P33=-12+16=44-2P41+2P43=-6+4=-2按i不增的顺序排列工件，得到加工顺序（1，2，3，4）和（）和（2，1，3，4），），Fmax=28Pikkk311-32k=1，2，3 3 3、CDS法法：uCDS法法是Johnson算法算法的扩展方法，被认为是好的具有鲁棒性的启发式算法；u算法步骤：将m台机器分组，产生m
26、-1个两台机器问题的集合；然后利用Johnson算法获得m-1个加工顺序(每个两台机器问题获得一个加工顺序)；选取这m-1个加工顺序中考核指标最好（一般为Makespan最短）的加工顺序作为近似最优调度解；3 3、CDS法法：uCDS法法是Johnson算法算法的扩展方法，从M-1个排序中找出近优解。uL1，按Johnson算法得到加工顺序(1，2，3，4)，Fmax28uL2，按Johnson算法得到加工顺序(2，3，1，4)，Fmax29u取顺序(1，2，3，4）为最优顺序。1 1、问题描述问题描述u(i，j，k)：表示工件i的第j道工序是在机器k上进行。u加工描述矩阵D：每一行描述一个工
27、件的加工，每一列的工序序号相同。D=1,1,1 1,2,3 1,3,22,1,3 2,2,1 2,3,2u加工时间矩阵T：与D相对应。D=1,1,1 1,2,3 1,3,22,1,3 2,2,1 2,3,2T=4 6 35 7 4u加工顺序矩阵S：每一行与机器相对应，每一列与工件相对应。D=1,1,1 1,2,3 1,3,22,1,3 2,2,1 2,3,2S=1,1,1 2,2,11,3,2 2,3,22,1,3 1,2,3u用甘特图图表示单件车间作业排序：D=1,1,1 1,2,3 1,3,22,1,3 2,2,1 2,3,2S=1,1,1 2,2,11,3,2 2,3,22,1,3 1,2,3T=4 6 35 7 41,1,12,1,31,2,32,2,11,3,22,3,2M1M2M32 2、智能优化算法、智能优化算法
