作业排序

---

作业排序又称加工顺序的安排。

它是指在一定的生产条件下，合理地规定各种加工件在设备上加工的次序，以求得总加工时间最短的管理活动。当加工件品种多、加工工艺路线复杂且各加工件工艺路线不一致时，作业排序问题十分复杂，通常采用计算机动态模拟的方法处理。

若各种加工件工艺路线一致，即按同一次序经过各加工工序，则情形较为简单，可以采用静态的排序方法，不必进行动态模拟。

现将静态的作业排序方法介绍如下。

(1)n种零件在一台设备上加工的排序。n种零件在同一设备上加工，总的加工时间等于各零件加工时间之和，因而，不管排序如何，总加工时间是相等的。

但由于排列次序不同，各零件等待加工的时间是不同的，因此这一排序问题评价的目标是平均等待时间为最小。设t_i为第i种零件在设备上的加工时间，排序规则为：t₁≤t₂≤…≤t_n，即将加工件依加工时间的长短，由小到大依次上机加工。

这种程序称为最短流程时间规则，简称SPT。

(2)n种零件在两台设备上加工排序。n种零件加工路线必须一致，即按同一次序先经设备1，然后再经设备2加工。约翰逊(S．M．Johnson)于1954年提出了一个规则，成功地解决了这一排序问题。

设问题如表4－4－2。

表4－4－2

约翰逊规则如下：

❶ 先从加工时间表中找出最小值。

❷ 若最小值在t_fi一行中，则该零件安排最先加工；若最小值在t_ei一行中，则该零件安排最后加工。

❸ 将已安排的零件剔除，再找出剩下的零件的加工时间的最小值。

❹ 重复❷ ❸ 两步，直到所有零件安排完毕。

(3)n种零件在三台以上设备上加工的排序。若n种零件依次通过设备A、B及C，在满足下列条件时，仍可应用约翰逊规则。其前提条件为：

min{t_Ai}≥max{t_Bi}

或者min{t_ci}≥max{t_Bi}

若满足上述条件则可虚设两台机器，the former和the later，令：

t_fi=t_Ai+t_Bi

t_ei=t_Bi+t_ci

则可按约翰逊规则找到最优排序。

对于不满足上述条件的三台设备或m台设备的排序问题，伊格纳尔(Ignall)和斯拉格(Schrage)于1965年提出分支界限法(Branch－and-Bound Technique)加以处理。随著电子计算机技术的发展，目前此类问题已借助电子计算机来求得最优解。