作业排序管理

1、12.1 排序问题概述排序问题概述 一、排序问题的分类一、排序问题的分类 按行业分： 生产作业排序 劳动力作业排序 制造业制造业为主为主 服务业服务业为主为主 按机器种类和数量不同分 单机排序 多机排序 按工件加工路线的特征 流水型排序 非流水型作业排序 二、影响作业排序的因素影响作业排序的因素 1、生产任务的到达方式、生产任务的到达方式 2、设备种类和数量、设备种类和数量 3、工作人员数量、工作人员数量 4、生产工艺流程方式、生产工艺流程方式 三、作业排序的任务和目标三、作业排序的任务和目标 （1） 进行优先权设定；进行优先权设定；（2）针对具体设备分配任务及人力；）针对具体设备分配任务及人

2、力；（3）为目标分配工作，使工作任务按期完成；）为目标分配工作，使工作任务按期完成；（4）不断监督以确保任务的完成；）不断监督以确保任务的完成；（5）对实施过程中的问题或异常辨识；）对实施过程中的问题或异常辨识；（6）作业排序进行检查和修改。）作业排序进行检查和修改。 12.2 制造业作业排序制造业作业排序 一、排序问题的假设排序问题的假设 一个工件不能同时在几台机器上加工；一个工件不能同时在几台机器上加工； 每台机器同时只能加工一个工件；每台机器同时只能加工一个工件； 每道工序只在一台机器上完成；每道工序只在一台机器上完成； 工件在加工过程中采取平行移动方式；工件在加工过程中采取平行移动方式

3、； 工件在加工过程中不允许中断；工件在加工过程中不允许中断； 工件数、机器数和加工时间均已知；工件数、机器数和加工时间均已知；二、排序方案的评价标准二、排序方案的评价标准 总流程时间最短；总流程时间最短； 平均流程时间最短；平均流程时间最短； 最大延迟时间或最大误期最短；最大延迟时间或最大误期最短； 平均延迟或平均误期最短；平均延迟或平均误期最短； 平均在制品占用量最小；平均在制品占用量最小； 总调整时间最小；总调整时间最小； 三、作业排序的优先规则三、作业排序的优先规则 fcfs规则：优先选择最早到达的工件。规则：优先选择最早到达的工件。 spt规则：优先选择加工时间最短的工件。规则：优先选

4、择加工时间最短的工件。 edd规则：优先选择交货期最短的工件。规则：优先选择交货期最短的工件。 scr：优先选择临界比最小的工件。临界比：优先选择临界比最小的工件。临界比为工件允许停留时间和工件余下加工时间之比。为工件允许停留时间和工件余下加工时间之比。 mwkr规则：优先选择余下加工时间最长的规则：优先选择余下加工时间最长的工件。工件。 lwkr规则：优先选择余下加工时间最短的规则：优先选择余下加工时间最短的工件。工件。 mopnr：优先选择余下工序数最多的工件。：优先选择余下工序数最多的工件。四、单台设备排序问题四、单台设备排序问题例12-1 生产任务编生产任务编号号jij1j2j3j4j

5、5j6加工时间加工时间ti (天天)482593预定交货期预定交货期di (天天)2423863213解法一、按spt规则排序 加工顺序为： j3 j6 j1 j4 j2 j5生产任务编生产任务编号号jij3j6j1j4j2j5完成时间完成时间ci (天天)259142231交货延期量交货延期量li (天天)000800最大延期量lmax=8天，平均延期量为：8/6=1.33天，平均流程时间： 8 .13312214952616161iiff解法二、按edd规则排序 加工顺序为：j4 j3 j6 j2 j1 j5生产任务编生产任务编号号jij4j3j6j2j1j5完成时间完成时间ci (天天)

6、5710182231交货延期量交货延期量li (天天)000000最大延期量和平均延期量均为零，而平均流程时间为： 5 .153122181075616161iiff五、流水型排序问题五、流水型排序问题（一）两台设备的流水型排序问题（一）两台设备的流水型排序问题 1、排序方法： 约翰逊贝尔曼规则 设零件ji（i=1、2、，n）的加工顺序是从设备a到设备b， 和 分别是零件ji在a和b上的加工时间。atiibt约翰逊约翰逊贝尔曼规则步骤：贝尔曼规则步骤： 1)1) 以零件编号为列，零件在机床上的加工以零件编号为列，零件在机床上的加工时间为行列表，从中找最小值（如果有时间为行列表，从中找最小值（如

7、果有多个最小值，可任取一个）；多个最小值，可任取一个）；2)2) 如果上述最小值属于如果上述最小值属于t tiaia行，则对应零件行，则对应零件应尽先安排；如果上述最小值属于应尽先安排；如果上述最小值属于t tibib 行，则对应零件应尽后安排；行，则对应零件应尽后安排；3)3) 将已经排定的零件除去，再重复前两步，将已经排定的零件除去，再重复前两步，直到全部零件排完为止。直到全部零件排完为止。例12-2 jit（小时）（小时）j1j2j3j4j5tia681237tib119534加工顺序如下：加工顺序如下： j4j1 j2j3j5 或或 j1 j2 j3j5j4 2、确定总流程时间甘特图法

8、 画法与零件移动方式图的画法相同；矩阵表法 按确定的零件加工顺序列表。（见下页）上例方案1，采用矩阵法计算总流程时间为40小时j4j1j2j3j5ta33698171229736tb361120929534440同样，可求得方案2总流程时间也为40小时。但不同之处在于，两种排序结果中机床b的加工、停歇时间不同，设备利用率不同。（二）三台设备的流水型排序问题（二）三台设备的流水型排序问题约翰逊约翰逊贝尔曼拓展法：贝尔曼拓展法：设有a、b、c三台加工设备，在满足：mintiamaxtkb 或minticmaxtkb 两条件之一的情况下，可将三台设备转换为两台假想设备g与h，且： tig=tia+t

9、ibtih=tib+tic 例12-3 jitj1j2j3j4tia158612tib3156tic41057因为mintia=6maxtkb=6，符合条件1，故可将a、b、c转换为g与h: 加工顺序：j2 j4 j3j1,求得总流程时间为48小时(记得减去多加的一组b机器上的零件的加工时间)。 jitj1j2j3j4tig1891118tih7111013（三）（三）m台设备的流水型排序问题台设备的流水型排序问题 1. 关键零件法：关键零件法：把总工时最大的零件作为关键零件，其余零件按照一定规则排列在关键零件之前或之后，可得到近似最优的加工顺序安排方案。 2. 最小排序系数法：最小排序系数法

10、：按排序系数的值由小到大排列。 排序系数：零件在前半部机床上加工工时与在后半部机床上加工工时的比值。若机床数为奇数，最中间机床的加工工时平分于前后两部分。 3.约翰逊约翰逊贝尔曼扩展法贝尔曼扩展法 1) 将零件在第1台与第m台设备上的加工看作两台设备流水排序问题，排出方案1；2) 将零件在第1、2台设备上的加工时间合并、第（m-1）、m台设备上的加工时间合并，所得到的两组加工时间，排出方案2；3) 将第1、2、3台设备的加工时间合并、第（m-2）、（m-1）、m台设备上的加工时间合并，所得到的两组加工时间，排出方案3；约翰逊约翰逊贝尔曼规则扩展法贝尔曼规则扩展法（续）4) 重复以上运算。最后将

11、第1、2、（m-1）台共（m-1）台机床的加工时间合并，第2、3、m台共（m-1）台机床的加工时间合并，所得到的两组加工时间，排出方案m-1；5) 求出以上（m-1）个方案中总流程时间最短者为最优或近似最优方案。以8台设备为例的贝尔曼扩展法 1；8 1、2；7、8 1、2、3；6、7、8 1、2、3、4；5、6、7、8 1、2、3、4、5；4、5、6、7、8 1、2、3、4、5、6；3、4、5、6、7、8 1、2、3、4、5、6、7；2、3、4、5、6、7、8mint六、非流水型排序问题六、非流水型排序问题 坐标图法坐标图法例12-4： 设有j1、j2两种零件，在a、b、c、d四种机床上加工，其工艺顺序及所需时间如表12-8所示，要求合理安排每台机床上零件的加工顺序，以便使总流程时间最短。（a、b、c、d四种机床各一台） 零 件机 床j1工艺顺序时间（小时）abcd2 1 8 2j2工艺顺序时间（小时）adbc1 4 1 4 零件在四台机床上的加工顺序及时间零件在四台机床上的加工顺序及时间 求解最短的总流程时间可采用最短折线上的时间之和。在本例中：f=2+1+8+2+（2）=15小时 a b c d 产品产品j1产品产品j2c