作业车间调度问题求解框架：规则指派算法¶

发布于：2021-08-28 | 分类：optimization , mathematics

以线性规划为代表的精确解法对作业车间调度问题求解效率随着问题规模的增大而急剧下降，我们进而转向近似解法；本文基于 jsp_framework 实现效率最高的一种近似解法：基于规则指派（Priority Dispatching based on Rule）。根据文献记载，基于规则指派算法为现实调度问题的实时滚动求解提供了有力支持。

基于规则指派算法¶

作业车间调度可以看作一个指派问题，即从作业队列中依次选择一个工序分配到相应的机器上。为了更准确地描述算法过程，定义：

前沿工序：作业工序序列中即将被处理的工序。例如开始作业前，第一道工序即为前沿工序；作业完成后，前沿工序为空。
前沿工序集：所有作业的前沿工序组成的集合。

于是，基于规则指派（Priority Dispatching based on Rule）算法：

计算前沿工序集 $\mathbb{Q}$
按照一定规则从 $\mathbb{Q}$ 中选择一个工序 $o_{i,j}$ ，分配到相应机器 $m_i$ 上
重复前两步直到 $\mathbb{Q} = \emptyset$

流程非常简单，基于 jsp_framework 框架实现：

solution.imminent_ops 获取初始前沿工序集 head_ops，初始为每个作业的第一道工序；为了保证更好的拓展性，实际上是作业工序序列中第一个尚未分配即 pre_machine_op 为空的工序。
按照规则 self.__dispatching_rule(op, solution) 排序前沿工序集 head_ops，将优先级最高即第一个工序分派到相应机器上去
每一次指派后更新前沿工序集：移除当前工序，如果存在下一道工序则将其加入前沿工序集

class PriorityDispatchSolver(JSSolver):
    '''General Priority Dispatching Solver.'''    

    def do_solve(self):
        solution = self.init_solution(direct_mode=False)
        self.solving_iteration(solution=solution)
        self.update_solution(solution=solution)


    def solving_iteration(self, solution:JSSolution):
        '''One iteration applying priority dispatching rule.'''
        # collect imminent operations in the processing queue
        head_ops = solution.imminent_ops

        # dispatch operation by priority
        while head_ops:
            # dispatch operation with the first priority
            op = min(head_ops, key=lambda op: self.__dispatching_rule(op, solution))
            solution.dispatch(op)

            # update imminent operations
            pos = head_ops.index(op)
            next_job_op = op.next_job_op
            if next_job_op is None:
                head_ops = head_ops[0:pos] + head_ops[pos+1:]
            else:
                head_ops[pos] = next_job_op

其中，定义规则的函数签名为：

def user_defined_rule(op:OperationStep, solution:JSSolution):
    pass

以工序和当前解实例为输入
返回结果为数值类型，或者数值类型元素的元组（即组合式规则，按元组顺序定义优先级）
返回数值越小表明优先级越高

典型规则¶

接下来问题的关键在于设计什么样的规则来定义工序的优先级。实际问题中，基于不同的目标例如加工周期（flow-time）、延误时间（lateness / tardiness）、在制品数等，可能有各式各样的规则，但本质上都依赖于作业工序的相关属性。

文献 ¹ 总结了 34 个典型规则，并根据依赖属性的不同分为 4 类。本文参考文献 ² 的简化版本，介绍基于如下3个静态属性和3个动态属性得到的14个基本规则。

静态属性：工序/作业的固有属性，不随加工进度改变
- 工序加工时间 $p_{i,j}$
- 作业工序数量 $|M_j|$
- 作业加工时间 $\,\Sigma_{i=1}^{m} p_{i,j}$ ：作业包含的所有工序的加工时间总和
动态属性：与加工进程相关的属性
- 工序生成时刻 $t_{i,j}$ ：工序 $O_{i,j}$ 达到机器 $m_i$ 的时刻，即上一道工序结束的时间
- 工序等待时间 $w_{i,j}$ ：从工序到达机器开始到可以进行加工的时间间隔，如果马上可以加工则等待为时间等于0
- 作业剩余工作时间 $r_{i,j}$ ：工序所在作业尚未进行的工序（包含当前工序）的加工时间之和

在这6个属性的基础上，定义出如下14个基本规则。

No. Rules   Description                     Type 
----------------------------------------------------
1   FIFO    First In First Out              Static 
2   LIFO    Last In First Out               Static 
3   SPT     Shortest Processing Time        Static 
4   LPT     Longest Processing Time         Static 
5   SPS     Shortest Process Sequence       Static 
6   LPS     Longest Process Sequence        Static 
7   STPT    Shortest Total Processing Time  Static 
8   LTPT    Longest Total Processing Time   Static 
9   ECT     Earliest Creation Time          Dynamic 
10  LCT     Longest Creation Time           Dynamic 
11  SWT     Shortest Waiting Time           Dynamic 
12  LWT     Longest Waiting Time            Dynamic 
13  LTWR    Least Total Work Remaining      Dynamic 
14  MTWR    Most Total Work Remaining       Dynamic

进而，组合其中的多个规则可以得到更多组合式规则。本文特别列出文献 ³ 提出的一个组合式规则，姑且以作者姓氏命名为 HH。

$z_{i,j} = \left (t_{i,j}+w_{i,j} \uparrow, \,\, r_{i,j}-1.5\,p_{i,j} \downarrow \right )$

该规则表明：

实际开始加工时间越早优先级越高
作业剩余工作时间与1.5倍工序加工时间的差值越大优先级越高

计算实例¶

几乎所有的文献都有一个共识：没有哪一种单一规则可以全方位优于其他规则，但折衷来看还是存在具有相对优势的某些规则。例如，上一节基本规则中的 SPT 和 MTWR得到较多文献的关注：文献 ¹ 认为 SPT 综合表现最好，文献 ² 则认为 MTWR 表现更好。本节带上 HH 规则，在最小化加工周期的目标下，看看效果究竟如何。

SPT 优先加工耗时短的工序，即简单的事情先做
MTWR 优先加工剩余活儿多的工序，即复杂的事情先做
HH 优先加工可以尽早开始的工序，在此基础上选择相对复杂的工序，即具备条件且复杂度高的事情先做

from jsp import (JSProblem, BenchMark)
from jsp.solver import PriorityDispatchSolver

# create problem from benchmark
names = ['ft06', 'la01', 'ft10', 'swv01', 'la38', 'ta24', \
        'ta31', 'swv12', 'ta24', 'ta42', 'ta54', 'ta68', 'ta69', 'ta70']
problems = [JSProblem(benchmark=name) for name in names]

# priority dispatching solver
solvers = []
rules = ['spt', 'mtwr', 'hh']
for rule in rules:
    solvers.append(PriorityDispatchSolver(rule=rule, name=rule.upper()))

# solve and result
benchmark = BenchMark(problems=problems, solvers=solvers, num_threads=6)
benchmark.run(show_info=True)

无需画成图，表格数据展示的结果已经很明显且震撼。

基于3种规则的求解时间相差无几，但相对精度差异甚大 HH >> MTWR >> SPT
HH以极高的计算效率（精度和时间的平衡）展现了其实用性

+----+---------+--------+---------------+--------------+----------+---------+------+
| ID | Problem | Solver | job x machine |   Optimum    | Solution | Error % | Time |
+----+---------+--------+---------------+--------------+----------+---------+------+
| 1  |   ft06  |  SPT   |     6 x 6     |      55      |  109.0   |   98.2  | 0.0  |
| 2  |   ft06  |  MTWR  |     6 x 6     |      55      |   74.0   |   34.5  | 0.0  |
| 3  |   ft06  |   HH   |     6 x 6     |      55      |   60.0   |   9.1   | 0.0  |
| 4  |   la01  |  SPT   |     10 x 5    |     666      |  1462.0  |  119.5  | 0.0  |
| 5  |   la01  |  MTWR  |     10 x 5    |     666      |  880.0   |   32.1  | 0.0  |
| 6  |   la01  |   HH   |     10 x 5    |     666      |  666.0   |   0.0   | 0.0  |
| 7  |   ft10  |  SPT   |    10 x 10    |     930      |  2648.0  |  184.7  | 0.1  |
| 8  |   ft10  |  MTWR  |    10 x 10    |     930      |  1289.0  |   38.6  | 0.1  |
| 9  |   ft10  |   HH   |    10 x 10    |     930      |  1082.0  |   16.3  | 0.1  |
| 10 |  swv01  |  SPT   |    20 x 10    |     1407     |  4474.0  |  218.0  | 0.3  |
| 11 |  swv01  |  MTWR  |    20 x 10    |     1407     |  2682.0  |   90.6  | 0.4  |
| 12 |  swv01  |   HH   |    20 x 10    |     1407     |  1839.0  |   30.7  | 0.5  |
| 13 |   la38  |  SPT   |    15 x 15    |     1196     |  6560.0  |  448.5  | 0.7  |
| 14 |   la38  |  MTWR  |    15 x 15    |     1196     |  1860.0  |   55.5  | 0.7  |
| 15 |   la38  |   HH   |    15 x 15    |     1196     |  1387.0  |   16.0  | 0.8  |
| 16 |   ta24  |  SPT   |    20 x 20    | (1602, 1647) | 12103.0  |  645.0  | 1.9  |
| 17 |   ta24  |  MTWR  |    20 x 20    | (1602, 1647) |  2773.0  |   70.7  | 3.0  |
| 18 |   ta24  |   HH   |    20 x 20    | (1602, 1647) |  1842.0  |   13.4  | 3.2  |
| 19 |   ta31  |  SPT   |    30 x 15    |     1764     | 12398.0  |  602.8  | 3.5  |
| 20 |   ta31  |  MTWR  |    30 x 15    |     1764     |  3120.0  |   76.9  | 4.3  |
| 21 |   ta31  |   HH   |    30 x 15    |     1764     |  2127.0  |   20.6  | 5.1  |
| 22 |  swv12  |  SPT   |    50 x 10    | (2972, 3003) | 10315.0  |  245.3  | 6.3  |
| 23 |  swv12  |  MTWR  |    50 x 10    | (2972, 3003) |  6666.0  |  123.1  | 6.7  |
| 24 |  swv12  |   HH   |    50 x 10    | (2972, 3003) |  4337.0  |   45.2  | 8.9  |
| 25 |   ta24  |  SPT   |    20 x 20    | (1602, 1647) | 12103.0  |  645.0  | 5.7  |
| 26 |   ta24  |  MTWR  |    20 x 20    | (1602, 1647) |  2773.0  |   70.7  | 7.4  |
| 27 |   ta24  |   HH   |    20 x 20    | (1602, 1647) |  1842.0  |   13.4  | 7.5  |
| 28 |   ta42  |  SPT   |    30 x 20    | (1867, 1956) | 19301.0  |  909.7  | 11.4 |
| 29 |   ta42  |  MTWR  |    30 x 20    | (1867, 1956) |  3411.0  |   78.4  | 13.2 |
| 30 |   ta42  |   HH   |    30 x 20    | (1867, 1956) |  2307.0  |   20.7  | 13.9 |
| 31 |   ta54  |  SPT   |    50 x 15    |     2839     | 18775.0  |  561.3  | 16.0 |
| 32 |   ta54  |  MTWR  |    50 x 15    |     2839     |  4419.0  |   55.7  | 16.9 |
| 33 |   ta54  |   HH   |    50 x 15    |     2839     |  3063.0  |   7.9   | 20.4 |
| 34 |   ta68  |  SPT   |    50 x 20    |     2784     | 28490.0  |  923.3  | 25.2 |
| 35 |   ta68  |  MTWR  |    50 x 20    |     2784     |  4560.0  |   63.8  | 29.2 |
| 36 |   ta68  |   HH   |    50 x 20    |     2784     |  3023.0  |   8.6   | 35.7 |
| 37 |   ta69  |  SPT   |    50 x 20    |     3071     | 27347.0  |  790.5  | 30.3 |
| 38 |   ta69  |  MTWR  |    50 x 20    |     3071     |  4819.0  |   56.9  | 35.4 |
| 39 |   ta69  |   HH   |    50 x 20    |     3071     |  3511.0  |   14.3  | 38.4 |
| 40 |   ta70  |  SPT   |    50 x 20    |     2995     | 27728.0  |  825.8  | 38.5 |
| 41 |   ta70  |  MTWR  |    50 x 20    |     2995     |  4879.0  |   62.9  | 40.8 |
| 42 |   ta70  |   HH   |    50 x 20    |     2995     |  3438.0  |   14.8  | 41.2 |
+----+---------+--------+---------------+--------------+----------+---------+------+

计算结果还是很符合我们日常做事哲学的：

优先做已经具备条件的事情（不浪费资源），在此基础上选择复杂度高的事情（抓主要矛盾）。

Blackstone, John H., Don T. Phillips, and Gary L. Hogg. "A state-of-the-art survey of dispatching rules for manufacturing job shop operations." The International Journal of Production Research 20.1 (1982): 27-45. ↩↩
Kaban, A. et al. "Comparison of dispatching rules in job-shop scheduling problem using simulation: a case study." International Journal of Simulation Modelling 11 (2012): 129-140. ↩↩
黄志, and 黄文奇. "作业车间调度问题的一种启发式算法." 计算机工程与应用 26(2004):25-27. ↩

Keys	Action
`?`	Open this help
`n`	Next page
`p`	Previous page
`s`	Search