作业排序管理.ppt

12.1 排序问题概述排序问题概述 一、排序问题的分类一、排序问题的分类 按行业分：生产作业排序 劳动力作业排序 制造业制造业为主为主服务业服务业为主为主按机器种类和数量不同分 单机排序 多机排序 按工件加工路线的特征 流水型排序 非流水型作业排序 二、影响作业排序的因素影响作业排序的因素 1、生产任务的到达方式、生产任务的到达方式 2、设备种类和数量、设备种类和数量 3、工作人员数量、工作人员数量 4、生产工艺流程方式、生产工艺流程方式 三、作业排序的任务和目标三、作业排序的任务和目标（1）进行优先权设定；进行优先权设定；（2）针对具体设备分配任务及人力；）针对具体设备分配任务及人力；（3）为目标分配工作，使工作任务按期完成；）为目标分配工作，使工作任务按期完成；（4）不断监督以确保任务的完成；）不断监督以确保任务的完成；（5）对实施过程中的问题或异常辨识；）对实施过程中的问题或异常辨识；（6）作业排序进行检查和修改。）作业排序进行检查和修改。12.2 制造业作业排序制造业作业排序 一、排序问题的假设排序问题的假设 一个工件不能同时在几台机器上加工；一个工件不能同时在几台机器上加工；每台机器同时只能加工一个工件；每台机器同时只能加工一个工件；每道工序只在一台机器上完成；每道工序只在一台机器上完成；工件在加工过程中采取平行移动方式；工件在加工过程中采取平行移动方式；工件在加工过程中不允许中断；工件在加工过程中不允许中断；工件数、机器数和加工时间均已知；工件数、机器数和加工时间均已知；二、排序方案的评价标准二、排序方案的评价标准 总流程时间最短；总流程时间最短；平均流程时间最短；平均流程时间最短；最大延迟时间或最大误期最短；最大延迟时间或最大误期最短；平均延迟或平均误期最短；平均延迟或平均误期最短；平均在制品占用量最小；平均在制品占用量最小；总调整时间最小；总调整时间最小；三、作业排序的优先规则三、作业排序的优先规则 FCFS规则：优先选择最早到达的工件。规则：优先选择最早到达的工件。SPT规则：优先选择加工时间最短的工件。规则：优先选择加工时间最短的工件。EDD规则：优先选择交货期最短的工件。规则：优先选择交货期最短的工件。SCR：优优先先选选择择临临界界比比最最小小的的工工件件。临临界界比比为工件允许停留时间和工件余下加工时间之比。为工件允许停留时间和工件余下加工时间之比。MWKR规规则则：优优先先选选择择余余下下加加工工时时间间最最长长的的工件。工件。LWKR规规则则：优优先先选选择择余余下下加加工工时时间间最最短短的的工工件。件。MOPNR：优先选择余下工序数最多的工件。：优先选择余下工序数最多的工件。四、单台设备排序问题四、单台设备排序问题例12-1 生产任务编生产任务编号号JiJ1J2J3J4J5J6加工时间加工时间ti(天天)482593预定交货期预定交货期di(天天)2423863213解法一、按SPT规则排序加工顺序为：J3 J6 J1 J4 J2 J5生产任务编生产任务编号号JiJ3J6J1J4J2J5完成时间完成时间Ci(天天)259142231交货延期量交货延期量Li(天天)000800最大延期量Lmax=8天，平均延期量为：8/6=1.33天，平均流程时间：解法二、按EDD规则排序加工顺序为：J4 J3 J6 J2 J1 J5生产任务编生产任务编号号JiJ4J3J6J2J1J5完成时间完成时间Ci(天天)5710182231交货延期量交货延期量Li(天天)000000最大延期量和平均延期量均为零，而平均流程时间为：五、流水型排序问题五、流水型排序问题（一）两台设备的流水型排序问题（一）两台设备的流水型排序问题 1、排序方法：约翰逊贝尔曼规则 设零件Ji（i=1、2、，n）的加工顺序是从设备A到设备B，和 分别是零件Ji在A和B上的加工时间。约翰逊约翰逊贝尔曼规则步骤：贝尔曼规则步骤：1)1)以以零零件件编编号号为为列列，零零件件在在机机床床上上的的加加工工时时间间为为行行列列表表，从从中中找找最最小小值值（如如果果有有多个最小值，可任取一个）；多个最小值，可任取一个）；2)2)如如果果上上述述最最小小值值属属于于t tiAiA行行，则则对对应应零零件件应应尽尽先先安安排排；如如果果上上述述最最小小值值属属于于t tiBiB 行，则对应零件应尽后安排；行，则对应零件应尽后安排；3)3)将将已已经经排排定定的的零零件件除除去去，再再重重复复前前两两步步，直到全部零件排完为止。直到全部零件排完为止。例12-2 Jit（小时）（小时）J1J2J3J4J5tiA681237tiB119534加工顺序如下：加工顺序如下：J4J1J2J3J5或或J1J2J3J5J42、确定总流程时间甘特图法 画法与零件移动方式图的画法相同；矩阵表法 按确定的零件加工顺序列表。（见下页）上例方案1，采用矩阵法计算总流程时间为40小时J4J1J2J3J5ta33698171229736tb361120929534440同样，可求得方案2总流程时间也为40小时。但不同之处在于，两种排序结果中机床B的加工、停歇时间不同，设备利用率不同。（二）三台设备的流水型排序问题（二）三台设备的流水型排序问题约翰逊约翰逊贝尔曼拓展法：贝尔曼拓展法：设有A、B、C三台加工设备，在满足：mintiAmaxtkB 或mintiCmaxtkB 两条件之一的情况下，可将三台设备转换为两台假想设备G与H，且：tiG=tiA+tiBtiH=tiB+tiC 例12-3 JitJ1J2J3J4tiA158612tiB3156tiC41057因为mintiA=6maxtkB=6，符合条件1，故可将A、B、C转换为G与H:加工顺序：J2 J4 J3J1,求得总流程时间为48小时(记得减去多加的一组B机器上的零件的加工时间)。JitJ1J2J3J4tiG1891118tiH7111013（三）（三）m台设备的流水型排序问题台设备的流水型排序问题 1.关键零件法：关键零件法：把总工时最大的零件作为关键零件，其余零件按照一定规则排列在关键零件之前或之后，可得到近似最优的加工顺序安排方案。2.最小排序系数法：最小排序系数法：按排序系数的值由小到大排列。排序系数：零件在前半部机床上加工工时与在后半部机床上加工工时的比值。若机床数为奇数，最中间机床的加工工时平分于前后两部分。3.约翰逊约翰逊贝尔曼扩展法贝尔曼扩展法 1)将零件在第1台与第m台设备上的加工看作两台设备流水排序问题，排出方案1；2)将零件在第1、2台设备上的加工时间合并、第（m-1）、m台设备上的加工时间合并，所得到的两组加工时间，排出方案2；3)将第1、2、3台设备的加工时间合并、第（m-2）、（m-1）、m台设备上的加工时间合并，所得到的两组加工时间，排出方案3；约翰逊约翰逊贝尔曼规则扩展法贝尔曼规则扩展法（续）4)重复以上运算。最后将第1、2、（m-1）台共（m-1）台机床的加工时间合并，第2、3、m台共（m-1）台机床的加工时间合并，所得到的两组加工时间，排出方案m-1；5)求出以上（m-1）个方案中总流程时间最短者为最优或近似最优方案。以8台设备为例的贝尔曼扩展法1；81、2；7、81、2、3；6、7、81、2、3、4；5、6、7、81、2、3、4、5；4、5、6、7、81、2、3、4、5、6；3、4、5、6、7、81、2、3、4、5、6、7；2、3、4、5、6、7、8六、非流水型排序问题六、非流水型排序问题坐标图法坐标图法例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小时 ABCD产品产品J1产品产品J2CBDA12.3 服务业中的作业排序服务业与制造业排序的区别服务作业排序的分类u服务作业的排序准则顾客平均等待时间最短准则响应顾客服务的概率最大准则总成本最小准则销售损失最小准则预期利润最大准则服务作业的排序方法1.优先准则排序2.服务人员的轮班排序全部雇佣专职人员情况下的排序（重点）雇佣部分兼职人员情况下的排序教材教材P311 P311 例例：连续休息两天的五日工作制下的人员安排方法。