《作业计划排序方法综述》由会员分享，可在线阅读，更多相关《作业计划排序方法综述（62页珍藏版）》请在金锄头文库上搜索。
1、第第8 8章章 生产作业计划生产作业计划 第二节第二节 作业排序作业排序 作业排序作业排序 一、基本概念一、基本概念 二、最长流程时间二、最长流程时间 三、三、n/1/Fmaxn/1/Fmax问题问题 四、四、n/2/F/Fmaxn/2/F/Fmax问题的算法问题的算法 五、一般五、一般n/m/P/ Fmaxn/m/P/ Fmax问题的启发式问题的启发式 算法算法 六、单件车间排序问题六、单件车间排序问题 一、基本概念一、基本概念 1 1、排序、排序 l 排序就是要将不同的工作任务安排一个 执行的顺序，使预定的目标最优化。 l 实际上就是要解决如何按时间的先后， 将有限的人力、物力资源分配给不
2、同工 作任务，使预定目标最优化的问题。 一、基本概念一、基本概念 一、基本概念一、基本概念 l 生产作业排序就是指对于等候某个设备 或工作中心加工的多个任务，确定这些 任务加工的先后次序。 l 目的 提高设备或工作中心的效率 减少在制品占用量 保证按期交货 缩短生产周期 排序中常用的几个概念排序中常用的几个概念 u工件（Job）：代表服务对象，工件可以是单个工件， 也可以是一批相同的工件。 u机器（Machine）：服务者。 u加工路线（Process）：是工件加工经过不同机器构成 的路线。比如，某工件要经过车、钻、冲、磨得路线加 工，可以用M1，M2，M3，M4表示。 u加工顺序：表示每台机
3、器加工n个工件的优先顺序，是 排序要解决的问题。可用一组工件代号的一种排列来表 示。如可用（1，6，5，4，3，2）表示加工顺序：J1 J6J5J4J3J2。 2 2、作业计划（、作业计划（SchedulingScheduling） u作业计划与排序不是一回事，它不仅要确定 工件的加工顺序，而且还要确定每台机器加 工每个工件的开工时间和完工时间。 u如果按最早可能开（完）工时间来编排作业 计划，则排序完后，作业计划也就确定了。 3 3、排序问题的分类、排序问题的分类 排排 序序 问问 题题 分分 类类 按机器个数按机器个数 按工件到达车间的情况 按参数 按目标函数的性质分类 多台机器排序问题多
4、台机器排序问题 单台机器排序问题单台机器排序问题 单件作业排序问题单件作业排序问题 流水线作业排序问题流水线作业排序问题 动态的排序问题 静态的排序问题 随机型排序问题 确定型排序问题 流水作业问题和单件作业排序问题的基本特征 流水作业排序问题的基本特征： u每个工件的加工路线都一样。如车铣磨。这里指的是工 件的加工流向一致，并不要求每个工件必须在每台机器上加 工。如有的工件为车磨，有的为铣磨。 u不仅加工路线一致，而且所有工件在各台机器上的加工顺序 也一样，这种排序称为排列排序（同顺序排序）。如工件排 序为：J1J3J2，则表示所有机器都是先加工J1，然后加 工J3，最后加工J2。 单件作业
5、排序问题的基本特征： u每个工件都有其独特的加工路线，工件没有一定的流向。 排序问题的表示方法排序问题的表示方法n/m/A/B n：工件数； m：机器数； A：作业类型； “F”代表流水作业排序问题，工件的加工流向 一致，并不要求每个工件必须在每台机器上加工 。 “P”代表流水作业排列排序问题，即同顺序排 序，所有零件在每台机器上的加工顺序相同。 “G”代表一般单件作业排序问题。 当m=1时，则A处为空白。 B：目标函数，通常是使其值最小。 排序问题的表示方法排序问题的表示方法n/m/A/B ln/1/Fmax：所有工件在一台机器上加工。 ln/m/P/Fmax：所有工件流向相同，在每台机器上
6、 的加工顺序相同。 ln/m/F/Fmax：所有工件流向相同，不同工件在每 台机器上的加工顺序不同。如零件1在M1上不加 工，在M2上才是第一道工序；而零件2在M1上是 第一道工序。 ln/m/G/Fmax：所有工件的加工路线都不相同，工 件没有流向。 排序问题的表示方法排序问题的表示方法n/m/A/B 一般来说，排列排序n/m/P/Fmax问题的最优 解不一定是相应流水车间排序问题的最优解 ，但一般是比较好的解。而对于仅有2台或3 台机器的情况，则排列排序问题的最优解一 定是相应流水车间排序问题的最优解。 4 4、排序问题的假设条件、排序问题的假设条件 u一个工件不能同时在几台不同的机器上加
7、工。 u工件在加工过程中采取平行移动方式。 u不允许中断。 u每道工序只在一台机器上完成。 u每台机器同时只能加工一个工件。 u工件数、机器数和加工时间已知，加工时间与加工 顺序无关。 4 4、排序问题的假设条件、排序问题的假设条件 u一个工件不能同时在几台不同的机器上加工。 u工件在加工过程中采取平行移动方式。 u不允许中断。 u每道工序只在一台机器上完成。 u每台机器同时只能加工一个工件。 u工件数、机器数和加工时间已知，加工时间与加工 顺序无关。 二、最长流程时间二、最长流程时间 u最长流程时间（ Fmax加工周期）：从第一个 工件在第一台机器上加工起到最后一个工件在 最后一台机器上加工
8、完毕为止所经过的时间。 u假定所有工件的到达时间都为0，则Fmax等于 排在末位加工的工件在车间的停留时间。 二、最长流程时间二、最长流程时间 计算Fmax的几个假定条件： u机器M1不会发生空闲； u对其它机器，能对某一工件加工其相应工序，必须具备 2个条件：机器必须完成排前一位的工件的加工；要加机器必须完成排前一位的工件的加工；要加 工的工件的上道工序已经完工。本工件在该设备上的开工的工件的上道工序已经完工。本工件在该设备上的开 始时间：始时间： B B timetime=max =max（T T零件前序完成时间 零件前序完成时间， ，T T该设备前工件完成时间 该设备前工件完成时间） ）
9、 E E timetime=B =Btime time+P +P ij ij B B timetime本工序开始时间， 本工序开始时间，E Etime time为本工序结束时间。 为本工序结束时间。 二、最长流程时间二、最长流程时间 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=1,m u Wi-工件Ji在加工过程中总的等待时间, 二、最长流程时间二、最长流程时间 u Ci-工件Ji 的完成时间,
10、 u Fi-工件Ji 的流程时间，即工件在车间的实际停 留时间，在工件都已到达的情况下, Fi= Pi+ Wi u Li-工件Ji 的延误时间, Li= Ci- di , Li0 延误 u Fmax-最长流程时间， FmaxmaxFi 三、三、n/1/Fmaxn/1/Fmax问题问题 优先调度规则优先调度规则 按优先调度规则挑选工序比随意挑选一道工序的方法更能符合计划编 制者的要求，同时又不必列出所有可能的作业计划，从而计算量小。 迄今为止，人们提出了100多个调度规则，其中主要有以下几个。 uSPT(Shortest Processing Time)法则：优先选择加工时间最短的工序 。 uF
11、CFS(First Come First Served)法则：优先选择最早进入可排工序 集合的工件。 uEDD(Earliest Due Date)法则：优先选择完工期限紧的工件。 uMWKR(Most Work Remaining)法则：优先选择余下加工时间最长 的工件。 uLWKR(Least Work Remaining)法则：优先选择余下加工时间最短 的工件。 uMOPNR(Most Operations Remaining)法则：优先选择余下工序数 最多的工件。 优选排序法则优选排序法则 u按SPT法则可使工件的平均流程时间最短，从而减少 在制品量。 uFCFS法则来自排队论，它对工
12、件较公平。 uEDD法则可使工件最大延误时间最小。 uMWKR法则使不同工作量的工件的完工时间尽量接 近。LWKR法则，使工作量小的工件尽快完成。 uMOPNR法则与MWKR法则类似，只不过考虑工件 在不同机器上的转运排队时间是主要的。 三、三、n/1/Fmaxn/1/Fmax问题问题 n个作业单台工作中心的排序目标（1 1）平均流程时间最短。）平均流程时间最短。 若n个作业按照优先规则已排定顺序，则任何一个作业，假定排在 第k位，第k作业的流程时间Fk 总的流程时间为： 相应的目标函数为 即总流程时间最短。 其中，pi表示作业i的加工时间； 则全部作业的平均流程时间为： 三、三、n/1/Fm
13、axn/1/Fmax问题问题 n个作业单台工作中心的排序目标（2）最大延迟时间、总 延迟时间（或平均延迟时间）为最小。 单个作业的延迟时间为Li，如果以最大延迟时间为最小，则其目 标函数为： min Lmax=maxLi （i=1,2，n） 三、三、n/1/Fmaxn/1/Fmax问题问题 例：现有5个订单（任务）需要在一台机器上加工，5个订单的 到达顺序为A，B，C，D，E。相关数据如下： 订单（以到达的顺序） 工时间(天) 交货期(天) A B C D E 3 4 2 6 1 5 6 7 9 2 分析：分别采用FCFSFCFS（先到先服务）规则（先到先服务）规则 、最短加工时间、最短加工时
14、间SPT SPT规规 则、则、交货期交货期EDDEDD规则、规则、后到先服务后到先服务LCFSLCFS规则规则进行排序，并对排序 的结果进行比较分析。 三、三、n/1/Fmaxn/1/Fmax问题问题 方案一方案一 利用先到先服务利用先到先服务FCFSFCFS规则，其流程时间的结果如下：规则，其流程时间的结果如下： 加工顺序 加工时间 交货日期 流程时间 A B C D E 3 4 2 6 1 5 6 7 9 2 0+3=3 3+4=7 7+2=9 9+6=15 15+1=16 总流程时间=3+7+9+15+16=50（天）; 平均流程时间=50/5=10天; 将每个订单的交货日期与其流程时间
15、相比较，发现只有A订单能按时交货。订 单B，C，D和E将会延期交货，延期时间分别为1,2,6,14天。 每个订单平均延期（1+2+6+14）/5=4.6天。 三、三、n/1/Fmaxn/1/Fmax问题问题 方案二方案二 利用最短加工时间利用最短加工时间SPTSPT规则，流程时间为：规则，流程时间为： 加工顺序 加工时间 交货日期 流程时间 1 2 3 4 6 2 7 5 6 9 0+1=1 1+2=3 3+3=6 6+4=10 10+6=16 E C A B D 总流程时间=1+3+6+10+16=36（天） 平均流程时间=36/5=7.2天 SPT规则的平均流程时间比FCFS规则的平均流程
16、时间小。另外，将每个订单的交 货日期与其流程时间相比较，订单E和C将在交货日期前完成。订单A，B，D,延 期时间分别为1,4,7天。 每个订单的平均延期时间为（0+0+1+4+7）/5=2.4天。 三、三、n/1/Fmaxn/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天。 方案三方案三 利用最早交货期先加工利用最早交货期先加工EDDEDD规则，排序结果为：规则，排序结果为： 加工顺序 加工时间 交货日期 流程时间 E A B C D 1 3 4 2 6 2 5
