顺序依赖并行机调度问题介绍

生产调度问题是指：给定一个加工任务，根据已有的生产条件，对有限的系统资源进行分配，对产品的加工步骤进行安排，使得某项性能指标最优。在实际生产过程中，所涉及的约束条件主要有：机器的加工能力，机器的数量，加工的产品数量，产品的加工顺序，产品的交货时间，生产原料的数量，成本限制，机器故障，产品投产期等。考虑的性能指标主要有：产品交货时间最短，加工时间最短，生产周期最短，成本最少，设备利用率最高等，实际的生产过程一般要平衡多个性能指标[1]。

问题分类：

根据加工能力的不同，调度问题可以分为单机调度、并行机调度、流水车间调度和作业车间调度等多种类型。其中单机调度只有一台机器参与加工，最终要找到一个最优工序排列；并行机调度是指有多台性能一样的并行机可以参与加工，所有加工任务只有一道工序，加工任务可以在其中的任意一台加工完成；流水车间调度指的是，对应于不同的加工工件，有着相同的加工顺序，各工件的加工时间可以相同或不同；作业车间调度指的是，每个工件都有自己的加工线路，任意的工件之间其加工顺序和加工时间都可以不同[2]。

图1 并行机调度示意图

由于不同的调度问题所涉及的机器、工件的性质及所要求的目标不同，出现了形式多样的调度模型，Graham等在1979年提出了目前通用的三参数表示方法，三参数方法a|b|g由三个域组成，其中a表示机器的环境及性质，b域表示工件的性质及对加工影响的约束条件，g域表示需要优化的目标[3]。常见的域参数见下表。

表 1 调度问题模型域参数

单机调度问题可以描述为，相互独立的任务需要在系统中的一台机器上序贯处理，每项任务都有加工时间、交货期等参数，此外还要满足一些调度环境和约束条件的要求，调度目标就是要找到一个最优的任务序列使得系统总成本最小。

其中处理顺序无关的单机调度问题是指工件的准备时间相同或固定，此时工件的加工准备时间是顺序无关的，称为顺序无关的单机调度问题。处理顺序依赖的单机调度问题是，任务的加工准备时间依赖与前一个加工任务，如两个任务共享部分模具时，其换型时间会缩短，此时问题称为顺序依赖准备时间的单机调度问题。

批量加工单机调度问题是指，加工任务可以分为若干种类，同种加工任务是相同的，之间不用换型；而非批量加工单机调度问题是指，每个加工任务都是不同的，无法合并为一个连续任务加工。

并行机调度作为单机调度问题的延伸，除了考虑单机调度的特点外，还需要考虑设备性能的问题，和环境的因素。按照设备性能的不同，可以分为等同并行机调度与不相关并行机调度。其中等同并行机调度是指所有机器皆可对工件进行加工，并且每台机器加工同一工件的时间相同。而不相关并行机又称为不相关并行机，即同一种工件可以在任意一台机器上加工，但是在不同机器上工件的加工时间不同。按照环境的不同可以分为静态调度与动态调度。其中静态调度将并行机车间生产加工过程理想化，仅考虑工件在机器上的加工时间，不考虑外界突发因素和约束条件的影响。而动态调度需要考虑外界各种突发因素和实际工况存在的约束条件，如机器故障、订单修改等，动态调度需要根据外界突发因素和实际工况环境的变化对规划进行改动，以便保持规划的优度[4]。

求解算法：

由于P||STsd|Cmax问题本身NP-难的性质，精确方法难以在短时间内有效求解，因此，其求解方法可以总结为启发式规则方法和元启发式算法。

启发式规则依据一定的规则和策略来决定下一步需要调度的工作，从而产生较好的调度解。优点是简单实用，计算代价小，但面临复杂的调度问题时，难以得到全局最优解。针对不同的问题，业内提出了各种调度规则[5,6]。

1、EDD规则：最早工期（earliest due date）优先，按照工期从小到大排列，该规则对1||Lmax是最优的。

2、EDDF规则：同产品族内优先（EDD within families），同种任务类型内部按照EDD规则进行排序。

3、EDDB规则：产品批量最早工期优先（EDD for batches），不同批次间的任务按照EDD规则排序。

4、ATC规则：明显滞后成本（apparent tardiness cost）规则。该规则针对1||∑wjTj问题具有较好效果。ATC根据一项指数每次调度一项工作。每次机器空闲时，选择具有最高排序指数的工作作为下一个加工的工作。指数定义如下：

其中，K是由经验确定的比例规则参数，是剩余工作的平均加工时间。

5、NEH规则

NEH规则方法是Nawaz、Enscore和Ham提出的NEH启发式规则，其主要步骤如下[7]：

步骤1：计算各工件在各台机器上加工时间的总和并且进行降序排列；

步骤2：排列序列中的前两个工件，保存具有较好部分目标函数值得排列，固定这两个工件的顺序；

步骤3：从第三个工件开始，依次取出第k个工件，将其插入到之前固定的k-1个工件排序中所有可能的k个位置上，保存具有最优部分目标函数值得工件序列，并固定这k个工件的位置。

6、多插入启发规则[8]

多插入启发规则来源于对旅行商问题的求解，其主要步骤如下：

步骤1：计算各任务修正加工时间；

步骤2：对各个加工任务按照修正加工时间降序排列；

步骤3：按照步骤2的顺序依次安排各个加工任务的顺序

     步骤3.1：安排任务j至每台机器上的每个可能位置；

     步骤3.2：计算任务j引起的增量完成时间；

     步骤3.2：安排任务j至最小增量完成时间的机器和位置。

常见的用于并行机调度的元启发式算法有遗传算法（Genetic Algorithm，GA）、人工蜂群算法（Artificial Bee Colony，ABC）、和迭代贪婪算法（Iterated, Greedy，IG）等。

文献[9]应用遗传算法来求解带顺序依赖的不相关并行机的调度问题，作者构建了问题的混合整数模型，并针对问题设计了交叉算子和邻域搜索算法，对比了不同算法子下求解效果的差异。

文献[10]针对考虑预防性维修的不相关并行机调度问题，设计了一种以最小最大完工时间为目标的人工蜂群算法。通过多个子蜂群的设计，平衡了算法的全局搜索与局部搜索，通过计算验证算法在计算时间方面相比传统遗传算法有一定优势。

文献[11]使用迭代贪婪算法来求解不相关并行机的调度问题，作者使用迭代贪婪框架，设计了两个local search 算子来加速算法的搜索效率，利用并行插入算子来快速构建新的可行解。

文献[12]在迭代贪婪的框架下设计了一种的解的编码方式，利用高效的启发式构造方法快速实现对任务的分批与调度，取得了比蚁群算法和模拟退火算法更优的求解质量。

综上所述，基于启发式算法通常能够较快的获得一个可行解，但解的质量不容易得到保证；基于元启发式算法能够对解进行提升，但通常要花费较多的时间。在实际问题处理中，往往需要结合两种方法，在元启发式算法的框架内，设计高效的启发式方法，在一定时间内获得优度指标内的解。

参考文献

[1] 赵诗奎. 基于遗传算法的柔性资源调度优化方法研究[D]. 浙江大学, 2013.

[2] 徐建有. 基于智能优化算法的生产调度问题研究[D]. 2015.

[3] Graham R L , Lawler E L , Lenstra J K , et al. Optimization and Approximation in Deterministic Sequencing and Scheduling: A Survey[J]. Annals of Discrete Mathematics, 1979, 5(1):287-326.

[4] 邴孝锋. 考虑机器调整时间的并行机分批优化调度研究[D].昆明理工大学,2019.

[5] 邓冠龙. 基于元启发式算法的调度问题若干研究[D]. 华东理工大学.

[6] Baker K R. Heuristic procedures for scheduling job families with setups and due dates[J]. Naval Research Logistics (NRL), 1999, 46(8): 978-991.

[7] Nawaz M, Enscore Jr E E, Ham I. A heuristic algorithm for the m-machine, n-job flow-shop sequencing problem[J]. Omega, 1983, 11(1): 91-95.

[8] Kurz M E, Askin R G. Heuristic scheduling of parallel machines with sequence-dependent set-up times[J]. International journal of production research, 2001, 39(16): 3747-3769.

[9] Vallada E, Ruiz R. A genetic algorithm for the unrelated parallel machine scheduling problem with sequence dependent setup times[J]. European Journal of Operational Research, 2011, 211(3): 612-622.

[10] 刘美瑶, 雷德明. 基于新型人工蜂群算法的分布式不相关并行机调度[J]. 控制理论与应用, 2020, 037(005):1080-1089.

[11] Fanjul-Peyro L, Ruiz R. Iterated greedy local search methods for unrelated parallel machine scheduling[J]. European Journal of Operational Research, 2010, 207(1): 55-69.

[12] Arroyo J E C, Leung J Y T, Tavares R G. An iterated greedy algorithm for total flow time minimization in unrelated parallel batch machines with unequal job release times[J]. Engineering Applications of Artificial Intelligence, 2019, 77: 239-254.