第六章 作业排序(生产管理(华中科技大学 崔南方)

《第六章 作业排序(生产管理(华中科技大学 崔南方)》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第六章作业排序一、基本概念二、最长流程时间三、n/2/F/Fmax问题的算法四、一般n/m/P/Fmax问题的启发式算法五、单件车间排序问题一、基本概念1、排序排序就是要将不同的工作任务安排一个执行的顺序，使预定的目标最优化。实际上就是要解决如何按时间的先后，将有限的人力、物力资源分配给不同工作任务，使预定目标最优化的问题。一、基本概念排序中常用的几个概念工件（Job）：服务对象；机器（Machine、Processor）：服务者。如：n个零件在机器上加工，则零件是工件，设备是机器；工人维修设备，出故障的设备是工件，工人是机器。

2、一、基本概念所以，作业排序也就是要确定工件在机器上的加工顺序，可用一组工件代号的一种排列来表示。如可用（1，6，5，4，3，2）表示加工顺序：J1—J6—J5—J4—J3—J2。一、基本概念2、作业计划（Scheduling）作业计划与排序不是一回事，它不仅要确定工件的加工顺序，而且还要确定每台机器加工每个工件的开工时间和完工时间。如果按最早可能开（完）工时间来编排作业计划，则排序完后，作业计划也就确定了。一、基本概念3、排序问题的分类与表示1）单台机器与多台机器的排序问题。2）流水车间与单件车间排序问题。一、基本概念流水车间排

3、序问题的基本特征：每个工件的加工路线都一样。如车—铣—磨。这里指的是工件的加工流向一致，并不要求每个工件必须在每台机器上加工。如有的工件为车—磨，有的为铣—磨。不仅加工路线一致，而且所有工件在各台机器上的加工顺序也一样，这种排序称为排列排序（同顺序排序）。如工件排序为：J1—J3—J2，则表示所有机器都是先加工J1，然后加工J3，最后加工J2。一、基本概念单件车间排序问题的基本特征：每个工件都有其独特的加工路线，工件没有一定的流向。一、基本概念3）表示方法一般正规的表示方法为：n/m/A/Bn：工件数；m：机器数；A：车间类型（

4、F、P、G）；B：目标函数一、基本概念4）一般来说，排列排序问题的最优解不一定是相应流水车间排序问题的最优解，但一般是比较好的解。而对于仅有2台或3台机器的情况，则排列排序问题的最优解一定是相应流水车间排序问题的最优解。一、基本概念4、排序问题的假设条件一个工件不能同时在几台不同的机器上加工。工件在加工过程中采取平行移动方式。不允许中断。每道工序只在一台机器上完成。每台机器同时只能加工一个工件。工件数、机器数和加工时间已知，加工时间与加工顺序无关。二、最长流程时间最长流程时间（加工周期）：从第一个工件在第一台机器上加工起到最后一

5、个工件在最后一台机器上加工完毕为止所经过的时间。假定所有工件的到达时间都为0，则Fmax等于排在末位加工的工件在车间的停留时间。二、最长流程时间计算Fmax的几个假定条件：机器M1不会发生空闲；对其它机器，能对某一工件加工必须具备2个条件：机器必须完成排前一位的工件的加工；要加工的工件的上道工序已经完工。二、最长流程时间二、最长流程时间ipi1pi2pi3pi4615243255144544453258217533674261012131671115202733121722303542132125323846三、n/2/F/Fm

6、ax问题的算法Johnson算法：假定：ai为工件Ji在机器M1上的加工时间，bi为工件Ji在机器M2上的加工时间，每个工件按M1—M2的路线加工。三、n/2/F/Fmax问题的算法Johnson算法的步骤：从加工时间矩阵中找出最短的加工时间。若最短时间出现在M1上，则对应的工件尽可能往前排。若最短时间出现在M2上，则对应的工件尽可能往后排。若最短时间有多个，则任选一个。划去已排序的工件。若所有工件都已排序，则停止，否则重复上述步骤。四、一般n/m/P/Fmax问题的启发式算法对于一般的n/m/P/Fmax问题，可以用分支定界法

7、求得最优解，但计算量很大。实际中，可以用启发式算法求近优解。四、一般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）即为近优解。

8、四、一般n/m/P/Fmax问题的启发式算法得到的加工顺序为(1，2，3，4)四、一般n/m/P/Fmax问题的启发式算法3、CDS法：CDS法是Johnson算法的扩展方法，从M-1个排序中找出近优解。四、一般n/m/P/Fmax问题的启发式算法L＝1，按Jo