《作业计划排序方法详解课件.ppt》由会员分享，可在线阅读，更多相关《作业计划排序方法详解课件.ppt（62页珍藏版）》请在三一办公上搜索。
1、第8章 生产作业计划,第二节 作业排序,作业排序,一、基本概念二、最长流程时间三、n/1/Fmax问题四、n/2/F/Fmax问题的算法五、一般n/m/P/ Fmax问题的启发式算法六、单件车间排序问题,一、基本概念,1、排序排序就是要将不同的工作任务安排一个执行的顺序，使预定的目标最优化。实际上就是要解决如何按时间的先后，将有限的人力、物力资源分配给不同工作任务，使预定目标最优化的问题。,一、基本概念,一、基本概念,生产作业排序就是指对于等候某个设备或工作中心加工的多个任务，确定这些任务加工的先后次序。目的提高设备或工作中心的效率减少在制品占用量保证按期交货缩短生产周期,排序中常用的几个概念
2、,工件（Job）：代表服务对象，工件可以是单个工件，也可以是一批相同的工件。机器（Machine）：服务者。加工路线（Process）：是工件加工经过不同机器构成的路线。比如，某工件要经过车、钻、冲、磨得路线加工，可以用M1，M2，M3，M4表示。加工顺序：表示每台机器加工n个工件的优先顺序，是排序要解决的问题。可用一组工件代号的一种排列来表示。如可用（1，6，5，4，3，2）表示加工顺序：J1J6J5J4J3J2。,2、作业计划（Scheduling）,作业计划与排序不是一回事，它不仅要确定工件的加工顺序，而且还要确定每台机器加工每个工件的开工时间和完工时间。如果按最早可能开（完）工时间来编
3、排作业计划，则排序完后，作业计划也就确定了。,3、排序问题的分类,排序问题分类,按机器个数,按工件到达车间的情况,按参数,按目标函数的性质分类,多台机器排序问题,单台机器排序问题,单件作业排序问题,流水线作业排序问题,动态的排序问题,静态的排序问题,随机型排序问题,确定型排序问题,流水作业问题和单件作业排序问题的基本特征,流水作业排序问题的基本特征：每个工件的加工路线都一样。如车铣磨。这里指的是工件的加工流向一致，并不要求每个工件必须在每台机器上加工。如有的工件为车磨，有的为铣磨。不仅加工路线一致，而且所有工件在各台机器上的加工顺序也一样，这种排序称为排列排序（同顺序排序）。如工件排序为：J1
4、J3J2，则表示所有机器都是先加工J1，然后加工J3，最后加工J2。,单件作业排序问题的基本特征：每个工件都有其独特的加工路线，工件没有一定的流向。,排序问题的表示方法n/m/A/B,n：工件数； m：机器数； A：作业类型； “F”代表流水作业排序问题，工件的加工流向一致，并不要求每个工件必须在每台机器上加工。 “P”代表流水作业排列排序问题，即同顺序排序，所有零件在每台机器上的加工顺序相同。 “G”代表一般单件作业排序问题。 当m=1时，则A处为空白。 B：目标函数，通常是使其值最小。,排序问题的表示方法n/m/A/B,n/1/Fmax：所有工件在一台机器上加工。n/m/P/Fmax：所有
5、工件流向相同，在每台机器上的加工顺序相同。n/m/F/Fmax：所有工件流向相同，不同工件在每台机器上的加工顺序不同。如零件1在M1上不加工，在M2上才是第一道工序；而零件2在M1上是第一道工序。n/m/G/Fmax：所有工件的加工路线都不相同，工件没有流向。,排序问题的表示方法n/m/A/B,一般来说，排列排序n/m/P/Fmax问题的最优解不一定是相应流水车间排序问题的最优解，但一般是比较好的解。而对于仅有2台或3台机器的情况，则排列排序问题的最优解一定是相应流水车间排序问题的最优解。,4、排序问题的假设条件,一个工件不能同时在几台不同的机器上加工。工件在加工过程中采取平行移动方式。不允许
6、中断。每道工序只在一台机器上完成。每台机器同时只能加工一个工件。工件数、机器数和加工时间已知，加工时间与加工顺序无关。,4、排序问题的假设条件,一个工件不能同时在几台不同的机器上加工。工件在加工过程中采取平行移动方式。不允许中断。每道工序只在一台机器上完成。每台机器同时只能加工一个工件。工件数、机器数和加工时间已知，加工时间与加工顺序无关。,二、最长流程时间,最长流程时间（ Fmax加工周期）：从第一个工件在第一台机器上加工起到最后一个工件在最后一台机器上加工完毕为止所经过的时间。假定所有工件的到达时间都为0，则Fmax等于排在末位加工的工件在车间的停留时间。,二、最长流程时间,计算Fmax的
7、几个假定条件：机器M1不会发生空闲；对其它机器，能对某一工件加工其相应工序，必须具备2个条件：机器必须完成排前一位的工件的加工；要加工的工件的上道工序已经完工。本工件在该设备上的开始时间：Btime=max（T零件前序完成时间，T该设备前工件完成时间）Etime=Btime+PijBtime本工序开始时间，Etime为本工序结束时间。,二、最长流程时间,Ji-工件i，i=1,2,.n。 Mj - 机器j，j1，2，m. di-工件Ji 的完工期限。 pij-工件Ji在机器Mj上的加工时间,j=1,m Pi-工件Ji的加工时间, wij-工件Ji在机器Mj前的等待时间, j=1,m Wi-工件J
8、i在加工过程中总的等待时间,二、最长流程时间,Ci-工件Ji 的完成时间, Fi-工件Ji 的流程时间，即工件在车间的实际停留时间，在工件都已到达的情况下, Fi= Pi+ Wi Li-工件Ji 的延误时间, Li= Ci- di , Li0 延误 Fmax-最长流程时间， FmaxmaxFi,三、n/1/Fmax问题,优先调度规则,按优先调度规则挑选工序比随意挑选一道工序的方法更能符合计划编制者的要求，同时又不必列出所有可能的作业计划，从而计算量小。迄今为止，人们提出了100多个调度规则，其中主要有以下几个。SPT(Shortest Processing Time)法则：优先选择加工时间最短
9、的工序。FCFS(First Come First Served)法则：优先选择最早进入可排工序集合的工件。EDD(Earliest Due Date)法则：优先选择完工期限紧的工件。MWKR(Most Work Remaining)法则：优先选择余下加工时间最长的工件。LWKR(Least Work Remaining)法则：优先选择余下加工时间最短的工件。MOPNR(Most Operations Remaining)法则：优先选择余下工序数最多的工件。,优选排序法则,按SPT法则可使工件的平均流程时间最短，从而减少在制品量。FCFS法则来自排队论，它对工件较公平。EDD法则可使工件最大延
10、误时间最小。MWKR法则使不同工作量的工件的完工时间尽量接近。LWKR法则，使工作量小的工件尽快完成。MOPNR法则与MWKR法则类似，只不过考虑工件在不同机器上的转运排队时间是主要的。,三、n/1/Fmax问题,n个作业单台工作中心的排序目标（1）平均流程时间最短。若n个作业按照优先规则已排定顺序，则任何一个作业，假定排在第k位，第k作业的流程时间Fk,总的流程时间为：,相应的目标函数为 即总流程时间最短。,其中，pi表示作业i的加工时间；,则全部作业的平均流程时间为：,三、n/1/Fmax问题,n个作业单台工作中心的排序目标（2）最大延迟时间、总延迟时间（或平均延迟时间）为最小。单个作业的
11、延迟时间为Li，如果以最大延迟时间为最小，则其目标函数为： min Lmax=maxLi （i=1,2，n）,三、n/1/Fmax问题,例：现有5个订单（任务）需要在一台机器上加工，5个订单的到达顺序为A，B，C，D，E。相关数据如下：,订单（以到达的顺序） 工时间(天) 交货期(天),ABCDE,34261,56792,分析：分别采用FCFS（先到先服务）规则 、最短加工时间SPT规则、交货期EDD规则、后到先服务LCFS规则进行排序，并对排序的结果进行比较分析。,三、n/1/Fmax问题,方案一利用先到先服务FCFS规则，其流程时间的结果如下：,总流程时间=3+7+9+15+16=50（天
12、）;平均流程时间=50/5=10天; 将每个订单的交货日期与其流程时间相比较，发现只有A订单能按时交货。订单B，C，D和E将会延期交货，延期时间分别为1,2,6,14天。每个订单平均延期（1+2+6+14）/5=4.6天。,三、n/1/Fmax问题,方案二利用最短加工时间SPT规则，流程时间为：,总流程时间=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）/
13、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规则，排序结果为：,三、n/1/Fmax问题,总流程时间=1+7+9+13+16=46（天）平均流程时间=46/5=9.2天平均延期（0+0+2+7+11）/5= 4.0天,方案四利用后到先服务LCFS规则，预计流程时间为：,三、n/1/Fmax问题,很明显，此例中最短加工时间SPT比其余的规则都好，但情况总是这样的吗？答案是肯定的。另外，从数
14、学上可以证明，在n/1情况下，用其他的评价准则，如等待时间均值和完成时间均值最小，SPT规则都能获得最佳的方案，所以，该规则被称为“在整个排序学科中最重要的概念”。,规则 总流程（完成）时间 平均完成时间 平均延期,FCFSSPTEDDLCFS,50363946,107.27.89.2,4.62.42.44.0,四、n/2/F/Fmax问题的算法,Johnson算法：假定：ai为工件Ji在机器M1上的加工时间，bi为工件Ji在机器M2上的加工时间，每个工件按M1M2的路线加工。,四、n/2/F/Fmax问题的算法,Johnson算法的步骤：从加工时间矩阵中找出最短的加工时间。若最短时间出现在M
15、1上，则对应的工件尽可能往前排。若最短时间出现在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 =28,I 1 2 3 4 5 6,1 5 1 8 5 3 4 2 7 2 2 4 7 4,四、n/
16、2/F/Fmax问题的算法,某工件的工序开工时间和完工时间确定：Btime=max（T零件前序完成时间，T该设备前工件完成时间）Etime=Btime+PijBtime本工序开始时间，Etime为本工序结束时间。,Fmax =28,五、一般n/m/P/ Fmax问题的启发式算法,n/m/P/ Fmax问题：,五、一般n/m/P/ Fmax问题的启发式算法,i,Pi1,Pi2,Pi3,Pi4,6,1,5,2,4,3,2,5,5,1,4,4,5,4,4,4,5,3,2,5,8,2,1,7,5,3,3,6,7,4,2,6,10,12,13,16,7,11,15,20,27,33,12,17,22,3
17、0,35,42,13,21,25,32,38,46,右上角为该工序结束时间,Fmax =46,五、一般n/m/P/ Fmax问题的启发式算法,i,Pi1,Pi2,Pi3,Pi4,1,4,6,3,5,2,4,4,5,4,1,7,5,3,2,5,5,1,3,6,7,4,4,4,5,3,2,5,8,2,4,5,7,10,14,16,8,15,20,26,30,35,13,20,25,33,38,46,17,23,26,37,41,48,Fmax =48,五、一般n/m/P/ Fmax问题的启发式算法,对于一般的n/m/P/Fmax问题，可以用分支定界法求得最优解，但计算量很大。实际中，可以用启发式算
18、法求近优解。,五、一般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。对其余工件，
19、若Pi1Pim ，则按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+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=28,k=1，2
20、，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/ Fmax问题的启发式算法,L1，按Johnson算法得到加
21、工顺序(1，2，3，4)，Fmax28L2，按Johnson算法得到加工顺序(2，3，1，4)， Fmax29取顺序(1，2，3，4）为最优顺序。,六、单件车间排序问题（n/m/G/Fmax）,1、问题描述(i，j，k)：表示工件i的第j道工序是在机器k上进行。加工描述矩阵D：每一行描述一个工件的加工，每一列的工序序号相同。,六、单件车间排序问题（n/m/G/Fmax）,加工时间矩阵T：与D相对应。,六、单件车间排序问题（n/m/G/Fmax）,加工顺序矩阵S：每一行与机器相对应，每一列与工件相对应。,S=,1,1,1 2,2,1,1,3,2 2,3,2,2,1,3 1,2,3,六、单件车间排序问题（n/m/G/Fmax）,用甘特图图表示单件车间作业排序：,六、单件车间排序问题（n/m/G/Fmax）,2、智能优化算法启发式算法遗传算法模拟退火算法禁忌搜索算法蚁群算法粒子群算法,
