运营管理12-15章

第12章作业排序管理12.1排序问题基本概念12.1.1作业排序作业排序（jobsequencing）是指合理地安排各项作业活动、运作资源利用或者配置设施的时间表。具体说就是，为每台设备、每位员工详细地确定每天的工作任务和工作顺序的过程。它要解决不同工件在同一设备上的加工顺序问题、不同工件在整个生产过程中的加工顺序问题，以及设备和员工等资源合理分配问题。概括起来就是，作业排序需要解决“服务者”与“服务对象”之间的关系。这里的“服务者”包括机器、工序、工作地、员工等等；而“服务对象”则是指各项工作、客户等。12.1.2无限负荷和有限负荷无限负荷（Infiniteloading）指的是，在对工作中心（见本书第5章5.4节工作单元的介绍）分配任务时，并不直接考虑该工作中心是否具有足够的能力来完成所分配的工作，也不考虑每个工作中心中的每个资源完成这项工作的实际顺序，而是只考虑它需要多长时间，大体上估计所分配任务与该工作中心中的关键资源的能力是否匹配。有限负荷（Finiteloading）是指，在对工作中心分配任务时，则需要考虑该工作中心的能力是否与对所分配的任务匹配，并对他们做出详细的安排，要细化到每个工作日的每一时刻，以及每一种资源要做的工作的时间安排。如果有某个作业由于工件缺货而延迟，那么整个系统就会停滞等待，一直到可以从前面的作业中获得所需的工件。理论上讲，当采用有限负荷时，所有的计划都是可行的。12.1.3前向排序和后向排序另一个区别作业排序系统特征的是看作业排序使用的是前向排序还是后向排序。前向排序（Forwardscheduling）是指系统接受某个订单后，立即对该订单所需的作业按从前向后的顺序进行排序。前向排序系统能够显示出完成某项订单的最早时间。后向排序是指从未来的某个时期开始，按照从后向前的顺序进行排序。后向排序可以显示在某个日期前完成的订单的最晚开工时间。12.1.4纵向加载和横向加载纵向加载是指向工作中心分配作业任务时，采用无限负荷法，并且不去考虑作业任务的优先性。相反，横向加载是指在向工作中心分配作业任务时，采用有限负荷法，并且需要考虑作业任务的优先性。12.2作业指派作业指派是指为各生产或操作中心分配工作任务。分配方法是一种特殊的可将任务或工作分配给相应资源的线性规划模型。例如：将一种工作分配给某台机器；某一合约分配给某个投标人：将人员分配到一定的项目上等等。分配方法的分配目标是使完成现有任务的成本或时间达到最少。分配方法所分配的问题特征为：一件工作（或一个人）仅分配给一台机器（或一个项目）。经常使用的分配方法是匈牙利方法。匈牙利方法的基本思想是，在各种指派方案的时间（成本）预算表的基础上，通过表上作业法，得出总时间（成本）最低的指派方案。请运用匈牙利分配方法给出将任务分配至相应机器上的最佳分配方案。计算模板：匈牙利法的基本步骤如下：1．将每行数字减去该行中最小数字，将每列数字减去该列中最小数字。2.画数量最小的水平线和垂直线以盖住表中所有的零。若直线数等于表的行或列数，那么最佳分配方案找到了。3.从未被直线盖住的所有数中减去其中最小的数，并将此最小数加到所有直线两两相交之处的数上，再回到步骤2往下操作直至出现可能的最佳分配。4.最佳分配总是在表中零位置出现。利用上述求解算法进行4个工件与4台设备的作业指派。各种指派方案所需的加工时间参见表12-1。表12-2、12-3、12-4、12-5、12-6分别对应着求解算法的4个步骤。分配方法的匈牙利法请运用匈牙利分配方法给出将任务分配至相应机器上的最佳分配方案。计算模板（续）表12-3表12-4表12-5表12-6表12-1表12-212.3制造业作业排序12.3.1n/1作业排序n/1作业排序就是n种工件在单台设备上加工的排序。这是一种简单的排序问题。排序问题在理论方面的难度是随着机器设备数量的增加而提高，而不是随着加工工件数量的增加而提高。因此对n的惟一约束条件就是它必须是确定的有限的数字。n/1作业排序经常使用的排序规则如下：（1）最短加工作业时间规则（SPT---shortestprocessingtime或SOT---shortestoperationtime）：优先选择加工所需时间最短的工件，然后是第二短的，依次类推；（2）先到先服务规则（FCFS---firstcomefirstserved）：按照工件到达的先后顺序，优先选择最早进入排队队列中的工件；（3）交货期规则（EDD—EarliestDueDate）：优先选择交货期最早的工件进行加工。（4）开始日期规则：用约定的交货日期减去作业的正常提前期。优先选择最早开工时间的工件进行加工；（5）剩余松弛时间规则（STR）：剩余松弛时间=交货期前的剩余时间－剩余的加工时间。优先选择剩余松弛时间最短的工件进行加工；（6）每个作业的剩余松弛时间规则（STR/OP）：STR/OP计算公式如下：剩余作业数剩余的加工时余交货货期前的剩余时OP/STR优先选择每个作业剩余的松弛时间最短的工件进行加工；（7）关键比率规则（CR）：剩余工作日数当前日期交货日期关键比率优先选择关键比率最小的工件进行加工；关键比率规则主要适用于工作在进行中情况的排序（8）排队比率规则（QR）：计划中的剩余排队时间计划中的剩余松弛时间排队比率优先选择排队比率最小的工件进行加工（9）后到先服务规则（LCFS）：后到的订单放在先到的订单上面，工作人员在操作的时候通常会先加工上面的订单。（10）随机原则：主管或工作人员选择自己喜欢的作业先进行操作。练习题20：各优先规则对比为什么说SPT规则是在n/1作业排序中比其它规则都要好的规则？例12-1是根据FCFS、SPT、EDD和CR四种规则进行的n/1作业排序实例。例12-1，某加工企业的车间要为2008年7月加工的5批产品进行作业排序，每批产品的件数都是相同的，均为2000件，企业对各种产品的加工时间都有确定的限定，销售部门也都提出了各种产品的预定交货期，如表12-7所示：产品加工限时（天）交货日期（从现在起天数）A36B54C69D45E110表12-7产品加工限时及预定交货期（1）首先选择FCFS规则，则排序结果就是A—B—C—D—E。其排序结果如表12-8所示。加工顺序加工时间（天）流程时间（天）交货日期工作延迟天数A3360B5844C61495D418513E119109合计196231表12-8FCFS规则排序的结果（天）总流程时间6219181483（天）平均流程时间4.12562天）平均延迟天数(2.65913540（2）选择SPT规则，则排序结果就是E---A---D---B---C。其排序结果如表12-9所示。加工顺序加工时间（天）流程时间（天）交货日期工作延迟天数E11100A3460D4853B51349C619910合计194522表12-9SPT规则排序的结果（天）平均延迟天数（天）平均流程时间（天）总流程时间4.4522954545（3）选择EDD规则，则排序结果就是B---D---A---C---E。其排序结果如表12-10所示。加工顺序加工时间（天）流程时间（天）交货日期工作延迟天数B5541D4954A31266C61899E119109合计196329表12-10EDD规则排序的结果总流程时间=63（天）平均流程时间=63/5=12.6（天）平均延迟时间=29/5=5.8（天）（4）选择CR规则，根据公式B的关键比率为4/5=0.8，则排序结果为B---D---C---A---E。其排序结果如12-11所示。加工顺序（天）关键比率加工时间（天）流程时间（天）交货日期延迟交货天数B0.85541D1.254954C1.561596A2318612E10119109合计196632表12-11CR规则排序的结果（天）平均延迟天数（天）平均流程时间（天）总流程时间4.65322.1356666为什么说SPT规则是在n/1作业排序中比其它规则都要好的规则？（续）将以上4种规则的排序结果汇总，如表12-12所示规则总流程时间（天）平均流程时间（天）平均延迟天数（天）FCFS6212.46.2SPT4594.4EDD6312.65.8CR6613.26.4表12-7各优先规则对比为什么说SPT规则是在n/1作业排序中比其它规则都要好的规则？（续）很明显，在这里，SPT规则比其他的都要好，但是结果一直是这样吗？答案是肯定。而且，能够从数学上证明，在n/1情况下使用其他的衡量标准，比如平均等待时间和平均完成时间，SPT都能产生最优解。实际上，这种简单的规则是如此有用，以至于被称为“整个排序学科中最重要的概念”。12.3.2n/2作业排序稍微复杂一点的就是n/2作业排序了，即两个或者更多的作业必须在两台机器上以共同的工序进行加工。在n/2作业排序当中（2台机器上分配N件工作），运用最为广泛的就是约翰逊法则（Johnson’srule）了。目的是使从第一个作业开始到最后一个作业结束的总流程时间最短。约翰逊法则包括以下几个步骤：（1）列出每个作业在两台机器上的加工时间；（2）选择最短的加工时间；（3）如果最短的加工时间来自第一台机器，那么先完成这个作业，如果来自第二台机器，那么这个作业就排在最后进行操作；（4）对于剩余的作业重复第二步和第三步，直到整个排序完成。练习题21：约翰逊法则应用实例运用约翰逊规则为其安排最佳的排程顺序（用图示表示出来），并计算整体完工时间和其中的闲置时间的应用模板。例12-2，有5件特殊的产品需要在两台设备上进行生产，第一台设备设为1，第二台设备设为2，见表12-13。产品设备1（小时）设备2（小时）A68B43C25D912E101表12-13某设备生产信息解：第一步：列出每个作业在两台机器上的加工时间；第二步：（1）操作时间最短的工作是生产产品E，它在第二台设备上生产，因此将其安排在最后，并从要安排的工作中划掉它；E（2）产品C的操作时间是第二短的，其在第一台设备上生产，因而放在第一位，并删掉它；CE（3）产品B的操作时间是第三短的，其在第二台设备上生产，因而放在倒数第二位；CBE（4）剩下的两个产品中最短的操作时间是A，6小时，在第一台设备上生产，所以先安排A，然后安排D。CADBE排序的时间为：设备1269410设备2581231这种工作排序的分段时间可通过图12-1的方式表示出来。028172131设备1CADBE空闲但可以进行其他的工作设备2CADBE02781617293233注：黑框部分为等待时间。这样，5件产品总共需要33个小时即可完成。图12-1约翰逊法则工作排序的甘特图12.4车间作业控制车间作业控制（shop—floorcontrol，现在也常常翻译成生产作业控制）是指使用来自车间的数据和数据处理文件来维护和传递关于车间工单和工作中心的状态信息。进行车间作业控制的工具和方法有很多，工具通常有日常调度单、各种状态和异常报告和输入输出控制报告。在这里，我们只简单的介绍两种车间作业控制的工具。12.4.1甘特图甘特图是作业排序与作业跟踪控制中最常用的一种方法。它最早是由亨利·L．甘特（HenryL．Gantt）在1971年提出来的。许多车间的独立部门，不管是小型的还是大型的车间，它们都使用这个古老的甘特图来帮助计划和跟踪工作。它不仅可以用来协调许多计划好的活动，而且还可以用来进行项目规划。它的优点就在于简单明了，能够普遍运用于作业、任务、项目等的计划和控制。图12-2显示了某车间的作业进度甘特图。12.4.2输入/输出控制输入/输出控制（Input/Output,control,I/O）是制造计划和控制系统的一个主要特征。它的目的是管理工作流，其主要原则是：工作中心的输入永远不能超过工作中心的输出。当输入超过输出时，工作中心就会出现积压的现象，结果导致工作中心上游作业的预计提前期被迫延长。并且会形成阻塞，导致工作中心下游的作业时