第七章 作业排序(生产运作与管理,陈荣秋)

第七章作业排序流程规划战略能力计划综合计划主生产计划（MPS）物料需求计划（MRP）生产作业计划——将MRP转化为各个车间、班组、工作地的任务第一节作业排序的基本概念一、名词术语排序（Sequencing）：确定工件在机器上的加工顺序。加工顺序：每台机器加工n个工件的先后顺序作业计划（Scheduling）：不仅包括确定工件的加工顺序，而且还包括确定机器加工每个工件的开始时间与完成时间。加工路线：工件加工在技术上的约束——工件加工的工艺过程决定二、作业排序问题的分类（一）两种基本形式1、劳动力作业排序（人员排序）：主要确定人员何时工作2、生产作业排序：将不同工件安排到不同设备上或安排不同的人做不同的工作。在制造业中，生产作业排序是最主要的——加工工件是焦点；在服务业中，劳动力作业排序是主要的——服务的及时性是影响公司竞争力的主要因素。（二）制造业作业排序的分类1、按机器的种类和数量单台机器的排序问题多台机器的排序问题2、按工件到达车间的情况单件作业（Job-shop）排序问题：工件的加工路线不同流水作业（Flow-shop）排序问题：所有工件的加工路线完全相同静态排序问题动态排序问题3、按目标函数的性质平均流程时间最短的排序问题使误期完工的工件数最少的排序问题……三、作业排序的任务和目标有效的作业排序应做到以下几点：1、对将要做的工作进行优先权设定，以使工作任务按最有效顺序排列；2、针对具体设备分配任务及人力，通常以可利用的能力为基础；3、以实施为目标分配工作，以使工作任务如期完成。目标满足交货期要求极小化提前期极小化准备时间或成本极大化设备利用或劳动力的利用第二节制造业的作业排序一、作业排序方案的评价标准1、工件流程时间：从工件开始加工至完工的时间。包括在各个机器之间的移动时间、等待时间、加工时间等。2、全部完工时间（最长流程时间）完成一组工件所需的全部时间——从第一个工件在第一台机器开始加工，到最后一个工件在最后一台机器上完成加工时为止所经过的时间。3、延迟：比预定完工时间延迟的时间部分4、在制品库存5、总库存：计划入库量与现有库存量的总和6、利用率：一台机器或一个工人的有效生产时间占总工作时间的百分比。注：这些标准之间并不完全独立二、优先调度规则1、SPT（ShortestProcessingTime）规则（最短加工时间规则）优先选择加工时间最短的工件

——使工件的平均流程时间最短，从而减少在制品量。2、FCFS（FirstComeFirstServed）规则（先到先服务规则）按订单的先后顺序进行加工（优先选择最早进入可排工序集合的工件）——来自排队论，对工件较公平3、EDD（EarliestDueDate）规则优先选择完工期限最紧的工件——使工件延误时间最少根据不同的目标确定优先规则，按优先规则确定各任务的优先权，由此排定加工顺序。4、MWKR（MostWorkRemaining）规则

优先选择余下加工时间最长的工件——使不同工作量的工件完工时间尽量接近。5、LWKR（LeastWorkRemaining）规则优先选择余下加工时间最短的工件——使工作量小的工件尽快完成6、MOPNR（MostOperationsRemaining）规则优先选择余下工序数最多的工件7、SCR（SmallestCriticalRatio）规则优先选择临界比最小的工件——使工件延误时间最小

临界比=工件允许停留时间/工件余下加工时间8、RANDOM规则随机地挑选下一个三、优先调度规则事例在理论方面，排序问题的难度随着机床数量的增加而增大，而不是随需加工的作业数量的增加而增大。（一）n个作业单台机床的排序零件所需标准加工时间（h）顾客预计取货时间（h）A8

10B

6

12C

15

20D3

18E

12

22用SPT规则得出的作业排序加工顺序开始工作加工时间结束工作流程时间预计取货时间实际取货时间提前小时数拖延时间

总数

平均

平均在制品库存102/44=2.32（个）平均总库存120/44=2.78（个）D0333181815B369912123A98171710177E1712292922297C29154444204424102120183820.43.67.6EDD规则加工顺序开始工作加工时间结束工作流程时间预计取货时间实际取货时间提前小时数拖延时间

总数

平均

平均在制品库存115/44=2.61（个）平均总库存118/44=2.68（个）A088810102B86141412142D143171718181C17153232203212E32124444224422115118336230.67.2SPT规则：平均流程时间最短，在制品库存量更少。EDD规则：平均延迟时间较少，可以给顾客提供更好的服务，也提供了更低的总库存水平。从数学上可以证明：SPT规则是最优的方案。（二）n个作业两台机床的排序——流水作业排序约翰逊规则（方法）——目标函数是使全部完工时间最少约翰逊规则的基本步骤：1、列出每个作业在两台机床上的作业时间；2、选择最短的作业时间；3、如果最短的作业时间来自于第一台机床，则首先进行该作业；如果最短的作业时间来自于第二台机床，则该作业最后完成。4、对剩余的作业重复进行步骤2和3，直到排序完成。工件A1A2A3A4A5机床112451510机床22253168A3A2A2A2A3A3A3A5A5A5A1A1A4A3A2

甘特图：机床1机床2A2（4）空闲A1（12）A2（5）空闲A4（15）A1（22）A5（10）A4（6）A3（5）A5（8）A3（3）空闲比较：A2、A3、A5、A1、A4机床1机床2A2（4）空闲A3（5）A2（5）A5（10）A3（3）A1（12）A5（10）空闲空闲A4（15）A1（22）空闲A4（6）全部流程时间：55、59（三）n项作业在m台机床上的排序要求最优，计算量相当大，甚至连计算机也难以求解——无法用于实际生产中。人们提出了多种启发式算法，以便以最小的计算量得到足够好的结果。第三节服务业作业排序一、服务业作业排序与生产作业排序的主要区别区别的根本原因：服务不能储存（一）所提供的产品类型服务有顾客的参与，顾客是服务的一部分——作业排序对顾客有直接影响生产作业排序对最终使用者或消费者无直接影响（二）排序内容服务要定义服务交易的时间和地点制造业仅仅定义产品生产的操作步骤（三）过程控制服务业中，用户参与服务过程，并且对全部操作时间施加影响；制造业中，用户仅与最终产品或交付时间相关。（四）人员规模顾客化服务业中，服务的输出与劳动力的最佳规模之间的关系很难确定；制造业中，两者之间有紧密联系，可以算出最优的作业排序服务业有两种基本的排序方式：1、将顾客需求分配到服务能力的不同时间段内；2、将服务人员安排到顾客需求的不同时间段内。二、安排顾客需求在这种方式下，服务能力保持一定，而顾客需求被适当安排，以提供准时服务和充分利用能力。（一）预约——顾客化程度高一个预约系统给予顾客特定的服务时间——及时的顾客服务和服务人员的高效率。（二）预定——顾客化程度低通常用于顾客接受服务时需占据或使用相关的服务设施。（三）排队等待各种优先规则可用来决定服务先后顺序——通常的规则是先到先服务。重要问题：应尽量使顾客等待时间缩短——排队论的方法三、安排服务人员——人员班次计划作业排序每一个人日常的排班计划单班次问题：每天只有一个班次，部门每天都要营业多班次问题：每天有多班，一般为两班或三班班次计划的种类制定全年、每个月以至每周的人员需求计划单班次问题：1、保证工人每周有两个休息日；2、保证工人每周有两个休息日为连休。启发式算法：第一步：从每周的人员需求量中，找出全部具有最少人员需求量的两个连续日，再从中找出两日需求量总和最小者；第二步：指定一名人员在上述两日休息，从其余准备安排该人员工作的各日的人员需求量中减去1人的需求量；第三步：重复第一、二步星期一星期二星期三星期四星期五星期六星期日4342312工人14342312工人2工人3工人4工人5**3231212**2120211*