【学习目标】
1.掌握作业排序的有关概念；
2.掌握并能够运用作业排序规则解决一些简单的作业排序问题；
3.了解车间作业控制的方法；
4.理解服务企业的有关排序方法。
【导入案例】棘手的排队问题
位于格林尼治镇的大联盟超市通过市场调查了解，顾客可以忍受的最长队伍为7人；超过这个限度，客户会因厌烦而离去。因此，大联盟超市使用计算机系统对收银员进行科学调度，努力使等待结账的队伍不超过3人。为了应付高峰时期的客流量，大联盟超市和其他超市一样，采用雇用兼职员工的办法。大联盟超市雇用了很多家庭妇女和学生，这些临时工每天在超市里工作4个小时。
顾客在等待的时候会感到烦躁，而这时如果能够提供一些消遣，则会减少顾客的烦躁程度。自1950年以来，曼哈顿储蓄银行就开始在中午的高峰时间里向顾客提供一些娱乐节目。
曼哈顿储蓄银行的13个分行中均有钢琴师弹奏乐曲。为了使顾客排队等待的时间更加精彩，曼哈顿储蓄银行偶尔还会安排一些展览。曼哈顿储蓄银行相信，由于有了以上这些消遣活动，顾客能够忍受比较长的等待时间。银行的一位高级副总裁说：“即使在非常拥挤的高峰期，顾客向我们提出抱怨的情况也比较少。”
在酒店和办公楼的电梯的门上镶上镜子，可以使人们在等电梯时不至于太烦躁。人们通常会对着镜子整理一下自己的发型和衣服，而忽视了等待时间。拉塞尔·阿克夫研究指出，如果一家酒店的电梯门上有镜子，则这家酒店收到的关于电梯太慢的抱怨会比没有镜子的酒店少得多。
12.1排序问题基本概念
12.1.1作业排序
作业排序（Job Sequencing）是指合理地安排各项作业活动、运作资源利用或者配置设施的时间表。具体来说就是，为每台设备、每位员工详细地确定每天的工作任务和工作顺序的过程。它要解决不同工件在同一设备上的加工顺序问题、不同工件在整个生产过程中的加工顺序问题，以及设备和员工等资源合理分配问题。概括起来就是，作业排序需要解决“服务者”与“服务对象”之间的关系。这里的“服务者”包括机器、工序、工作地、员工等，而“服务对象”则是指各项工作、客户等。
12.1.2无限负荷和有限负荷
无限负荷（Infinite Loading），是指在对工作中心（见5.4节工作单元的介绍）分配任务时，并不直接考虑该工作中心是否具有足够的能力来完成所分配的工作，也不考虑每个工作中心中的每个资源完成这项工作的实际顺序，而是只考虑它需要多长时间，大体上估计所分配任务与该工作中心中关键资源的能力是否匹配。
有限负荷（Finite Loading），是指在对工作中心分配任务时，需要考虑该工作中心的能力是否与所分配的任务匹配，并对其作出详细的安排，要细化到每个工作日的每一时刻，以及每一种资源要做的工作的时间安排。如果有某个作业由于工件缺货而延迟，那么整个系统就会停滞，开始进入等待时间，一直到可以从前面的作业中获得所需的工件。理论上讲，当采用有限负荷时，所有的计划都是可行的。
12.1.3前向排序和后向排序
前向排序（For Ward Scheduling）是指系统接受某个订单后，立即对该订单所需的作业按从前向后的顺序进行排序。前向排序系统能够显示出完成某项订单的最早时间。后向排序是指从未来的某个时期开始，按照从后向前的顺序进行排序。后向排序可以显示在某个日期前完成订单的最晚开工时间。
12.1.4纵向加载和横向加载
纵向加载是指向工作中心分配作业任务时，采用无限负荷法，并且不去考虑作业任务的优先性；相反，横向加载是指在向工作中心分配作业任务时，采用有限负荷法，并且需要考虑作业任务的优先性。
小资料
根据行业的不同，作业排序可分为制造业的排序和服务业的排序。制造业的排序工作只是解决工件在生产过程中的加工次序问题，而服务业中由于有客户的参与以及其产品的不可储存性，因此在服务业中的排序工作中，主要是解决如何安排服务能力以满足客户的需求。
12.2作业指派
作业指派是指为各生产或操作中心分配工作任务。分配方法是一种特殊的可将任务或工作分配给相应资源的线性规划模型。例如，将一种工作分配给某台机器；某一合约分配给某个投标人；将人员分配到一定的项目上等。分配方法的分配目标是使完成现有任务的成本或时间达到最少。分配方法所分配的问题特征为：一件工作（或一个人）仅分配给一台机器（或一个项目）。经常使用的分配方法是匈牙利法。匈牙利法的基本思想是，在各种指派方案的时间（成本）预算表的基础上，通过表上作业法，得出总时间（成本）最低的指派方案。
匈牙利法的基本步骤如下。
（1）将每行数字减去该行中的最小数字，将每列数字减去该列中的最小数字。
（2）画数量最小的水平线和垂直线以盖住表中所有的零，若直线数等于表中的行或列数，那么最佳分配方案就找到了。
（3）从未被直线盖住的所有数中减去其中最小的数，并将此最小数加到所有直线两两相交之处的数上，再回到步骤（2）往下操作直至出现可能的最佳分配。
（4）最佳分配总是在表中零位置出现。
利用上述求解算法进行4个工件与4台设备的作业指派。
12.3制造业作业排序
12.3.1n/1作业排序
n/1作业排序就是n种工件在单台设备上加工的排序。这是一种简单的排序问题。排序问题在理论方面的难度随着机器设备数量的增加而提高，而不是随着加工工件数量的增加而提高。因此，对n的唯一约束条件就是它必须是确定的、有限的数字。n/1作业排序经常使用的排序规则如下。
（1）最短加工作业时间规则（Shortest Processing Time，SPT或Shortest Operation Time，SOT）。优先选择加工所需时间最短的工件，然后是第二短的，以此类推。
（2）先到先服务规则（First Come First Served，FCFS）。按照工件到达的先后顺序，优先选择最早进入排队队列中的工件。
（3）交货期规则（Earliest Due Date，EDD）。优先选择交货期最早的工件进行加工。
（4）开始日期规则。用约定的交货日期减去作业的正常提前期。优先选择最早开工时间的工件进行加工。
（5）剩余松弛时间规则（STR）。
STR＝交货期前的剩余时间－剩余的加工时间优先选择剩余松弛时间最短的工件进行加工。
（6）每个作业的剩余松弛时间规则（STR/OP）。
优先选择每个作业剩余松弛时间最短的工件进行加工。
（7）关键比率规则（CR）。
优先选择关键比率最小的工件进行加工。
（8）排队比率规则（QR）。
优先选择排队比率最小的工件进行加工。
（9）后到先服务规则（LCFS）。
后到的订单放在先到的订单上面，工作人员在操作的时候通常会先加工上面的订单。
（10）随机原则。主管或工作人员选择自己喜欢的作业先进行操作。
根据FCFS、SPT、EDD和CR4种规则进行的n/1作业排序实例。
某加工企业的车间要为2008年7月加工的5批产品进行作业排序，每批产品的件数都是相同的，均为2000件，企业对各种产品的加工时间都有确定的限定，销售部门也都提出了各种产品的预定交货期。
很明显，在这里，SPT规则比其他的都要好，但是结果一直是这样吗？答案是肯定的。
而且，能够从数学上证明，在n/1情况下使用其他的衡量标准，如平均等待时间和平均完成时间，SPT都能产生最优解。实际上，这种简单的规则是如此有用，以至于被称为“整个排序学科中最重要的概念”。
的工序进行加工。在n/2作业排序当中，运用最为广泛的就是约翰逊法则（Johnson"s Rule）了。目的是使从第一个作业开始到最后一个作业结束的总流程时间最短。约翰逊法则包括以下几个步骤：
（1）列出每个作业在两台机器上的加工时间；
（2）选择最短的加工时间；
（3）如果最短的加工时间来自第一台机器，那么先完成这个作业，如果来自第二台机器，那么这个作业就排在最后进行操作；
（4）对于剩余的作业重复（1）和（3），直到整个排序完成。
是约翰逊法则应用实例。
有5件特殊的产品需要在两台设备上进行生产，第一台设备设为1，第二台设备设为2。
12.3.3n/m作业排序
n/m（m≥3）的流水作业排序是一个相当复杂的问题。像一些比较简单的流水作业排序问题，只要采取枚举法就可以解决了。但是当n和m的数值都很大的时候，计算量就会相当大了，为求最优解而付出的代价是不经济的。这个时候，只需要得到自己满意的解就可以了，这时也可以把它称作现实最优解，并不需要理论上的最优解。
为了解决一些较复杂的排序问题，人们提出了各种启发式算法，其中比较有名的就是CDS法。CDS法是由坎贝尔（Cambell）、杜德克（Dudek）和史密斯（Smith）三个人提出来的，取三个人名字的第一个字母命名的方法。CDS法是受约翰逊法则的启发而得来的。
它是将n/m排序问题转换成m－1个n/2排序问题，然后取其中的最优值，从而得到n/m排序问题的较为满意的解。
（1）求加工时间为pi1和pim的排序问题，先不管中间其他设备的情况，而是只考虑第一台设备和最后一台设备。
（2）求加工时间为pi1＋pi2和pi，m－1＋pim的排序问题，就是将第一台设备和第二台设备看成是一个工作中心，将第m－1台设备和第m台设备看成是一个工作中心，同样不考虑其他设备情况。
12.4车间作业控制
车间作业控制（Shop Floor Control，现在也常常翻译成生产作业控制）是指使用来自车间的数据和数据处理文件来维护和传递关于车间工单和工作中心的状态信息。进行车间作业控制的工具和方法有很多，工具通常有日常调度单、各种状态和异常报告和输入输出控制报告。在这里，只简单地介绍两种车间作业控制的工具。
12.4.1甘特图
甘特图是作业排序与作业跟踪控制中最常用的一种方法。它最早是由亨利·L·甘特（Henry L.Gantt）在1971年提出来的。许多车间的独立部门，不管是小型的还是大型的车间，都使用这个古老的甘特图来帮助计划和跟踪工作。它不仅可以用来协调许多计划好的活动，而且还可以用来进行项目规划。其优点就在于简单明了，能够普遍运用于作业、任务、项目等的计划和控制。