具有周期维护的最小化加权总完工时间的平行机调度研究

Research on Parallel Machine Scheduling Problem with Periodic Maintenance to Minimize Total Weighted Completion Times

摘要: 针对具有周期维护的最小化加权总完工时间的平行机调度问题，首先证明了该调度问题是NP-难问题，并提出最优调度方案的4条性质。然后在WSPT规则的基础上结合工件在多机环境中的分配机制(JCT、MCT、BF)提出了WSPTJCT算法、WSPTMCT算法、WSPTBF算法以及ROPT算法，其中ROPT算法为其他3个算法的最优输出。最后通过数值实验对4个算法进行性能分析，结果显示：WSPTJCT算法、WSPTBF算法以及ROPT算法的性能与最大加工时长p_max呈倒U型；工件个数n越大，WSPTJCT算法、WSPTMCT算法、WSPTBF算法以及ROPT算法的性能越好。

Abstract: This paper tackles the parallel machine scheduling problem with periodic maintenance to minimize the weighted sum of completion times. This problem is proved to be NP-hard and four properties are proposed. Then, WSPTJCT algorithm, WSPTMCT algorithm and WSPTBF algorithm are proposed with three assignment mechanisms (JCT, MCT, BF) and WSPT rules. ROPT algorithm is the best one of the outputs of the three algorithms. Finally, the performance of the four algorithms is analyzed by numerical experiments. The results show that the performance of WSPTJCT algorithm, WSPTMCT algorithm, WSPTBF algorithm and ROPT algorithm is inverted U-shaped with the maximum processing time p_max and increases with the number of jobs n.

1. 引言

随着社会的发展，需要加工的工件种类和个数越来越多，过去不考虑机器维护的短时间加工模型已经无法满足当前需要。因此，将车间内机器的运行与维护综合考虑是很有必要的，尤其是周期维护。

在实际生产中，当货物是小批量生产时，不同的订单或者说不同的顾客对于企业的重要程度不一定完全相同，往往需要根据订单或顾客的重要性对每一批订单赋以权重。基于此，以最小化加权总完工时间为目标函数的调度问题引起了多个领域的注意。具有单次维护的单机调度问题 $1,h_i\left|\right|{\displaystyle \sum w_j}{C}_j$ 是一个强NP-难问题 [1]。可以从最优调度应有的性质的角度对具有维护的该目标函数问题提出相应启发式算法。

从文献角度来看，目标函数为最小化加权总完工时间的调度问题主要集中于单机环境 [2] - [8]。然而，在实际生产车间中，机器往往有多台。对于平行机调度问题的目标函数，研究得更多的是最小化时间表长 [9] 以及最小化总完工时间 [10]。基于此，我们在具有周期维护的多机环境中思考如何最小化加权总完工时间。

2. 问题描述

现有 $n$ 个在零时刻均已到达可随时加工的独立工件 $J_1,J_2,\cdots ,J_n$ 需要在 $m$ 台需要进行周期维护的机器 $M_1,M_2,\cdots ,M_m$ 上加工，且在加工过程中不可中断。其中工件 $J_j$ 的加工时长为 $p_j$，权重为 $w_j$，完工时间为 $C_j$。所有机器每隔时间单位 $T$ 就需要进行时长为 $t$ 的维护活动，在进行维护活动时不可加工任何工件。目标是给出工件的完工时刻 $C_j$ 与权重 $w_j$ 乘积之和 ${\displaystyle \sum w_j}{C}_j$ 最小的调度方案。当 $p_j>T$ 时，不存在可行调度方案，故下文中均假设 $p_j\le T\left(1\le j\le n\right)$。根据三参数表示法 [11]，上述调度问题可以被表示为 $P_m,PM\left|\right|{\displaystyle \sum w_j}{C}_j$。其中 $P_m$ 表示有 $m$ 台平行机可供使用； $PM$ 表示机器需要周期维护； ${\displaystyle \sum w_j}{C}_j$ 表示目标函数为最小化加权总完工时间。

若将机器 $M_i$ 的两个相邻维护之间的时间间隔 $T$ 看作一个时长为 $T$ 的批次，使用 $B_{i,k}$ 表示机器 $M_i$ 的第 $k$ 个批次，则调度问题 $P_m,PM\left|\right|{\displaystyle \sum w_j}{C}_j$ 的一个可行调度方案 $\sigma$ 可以被表示为：

$\sigma =\left\{B_{1,1},t,B_{1,2},t,\cdots ,B_{1,k_1},B_{2,1},t,\cdots ,B_{2,k_2},\cdots ,B_{m,1},t,B_{m,2},t,\cdots ,B_{m,k_m}\right\}$

3. 复杂性分析

由于调度问题 $1,h_i\left|\right|{\displaystyle \sum w_j{C}_j}$ 是NP-难问题 [1]，根据复杂度理论的归结性可知，具有周期维护的最小化加权总完工时间的调度问题 $P_m,PM\left|\right|{\displaystyle \sum w_j}{C}_j$ 也是NP-难问题。

4. 近似算法

4.1. 最优调度方案的性质

由于该调度问题是NP-难问题，无法直接给出最优调度方案。但是，我们可以根据目标函数提出几点最优调度方案应有的性质。

性质1：在最优调度方案中，一定存在 $0\le k_{\max }-k_{\min }\le 1$。其中 $k_{\max }=\max \left\{k_1,k_2,\cdots ,k_m\right\}$ ； $k_{\min }=\min \left\{k_1,k_2,\cdots ,k_m\right\}$。

证 明 不失一般性，假设调度方案 $\sigma$ 是最优调度方案， $k_{\max }=k_1$， $k_{\min }=k_2$， $\sigma$ 可以被表示为

$\sigma =\left\{B_{1,1},t,B_{1,2},t,\cdots ,B_{1,k_1},B_{2,1},t,\cdots ,B_{2,k_2},\cdots ,B_{m,1},t,B_{m,2},t,\cdots ,B_{m,k_m}\right\}$

其中， $k_{\max }-k_{\min }\ge 2$，且 $B_{1,k_1}$ 非空，至少有一个工件 $J_j$ 存在。

若将批次 $B_{1,k_1}$ 内的工件放入 $B_{2,k_2}$ 加工，其余批次不变，其目标函数为 $f$，则不等式 $f\left(\sigma \right)-f\ge w_j\left(t+p_j\right)>0$ 成立。也就是说，当 $k_{\max }-k_{\min }\ge 2$，且 $B_{1,k_1}$ 非空时，还有更优的调度方案。故，在最优调度方案中，一定存在 $0\le k_{\max }-k_{\min }\le 1$。证毕。

性质2：在最优调度方案中，所有平行机的批次的权重和都应该是由大到小的，不同机器的批次内的权重和也是。

证 明 不失一般性，假设调度方案 ${\sigma }_1$ 在机器 $M_i$ 的调度结果为 ${\sigma }_{1,i}=\left\{B_{i,1},t,B_{i,2},t,\cdots ,B_{i,l},t,B_{i,l+1},t,\cdots ,B_{i,k_i}\right\}$，在机器 $M_{i\text{+}q}$ 的调度结果为 ${\sigma }_{1,i+q}=\left\{B_{i+q,1},t,B_{i+q,2},t,\cdots ,B_{i+q,l},t,B_{i+q,l+1},t,\cdots ,B_{i+q,k_{i+q}}\right\}$。

调度方案 ${\sigma }_2$ 在机器 $M_i$ 的调度结果为 ${\sigma }_{2,i}=\left\{B_{i,1},t,B_{i,2},t,\cdots ,B_{i+q,l+1},t,B_{i,l+1},t,\cdots ,B_{i,k_i}\right\}$，在机器 $M_{i\text{+}q}$ 的调度

结果为 ${\sigma }_{2,i+q}=\left\{B_{i+q,1},t,B_{i+q,2},t,\cdots ,B_{i+q,l+1},t,B_{i,l},t,\cdots ,B_{i+q,k_{i+q}}\right\}$。

调度方案 ${\sigma }_1$ 和 ${\sigma }_2$ 除了批次 $B_{i,l}$ 和批次 $B_{i+q,l\text{+}1}$ 内的工件发生了对换外，其余批次没有任何变化。其中，

机器 $M_i$ 的第 $l$ 个批次的权重和为 ${\displaystyle \underset{j=1}{\overset{n_{i,l}}{\sum }}{w}_j^{i,l}}$ ；机器 $M_{i+q}$ 的第 $l+1$ 个批次 $B_{i+q,l\text{+}1}$ 的权重和为 ${\displaystyle \underset{j=1}{\overset{n_{i+q,l+1}}{\sum }}{w}_j^{i+q,l+1}}$ ；机器

$M_i$ 上的调度方案 ${\sigma }_1$ 和 ${\sigma }_2$ 的目标函数分别为 $f\left({\sigma }_1\right)$ 和 $f\left({\sigma }_2\right)$。

假设 ${\displaystyle \underset{j=1}{\overset{n_{i,l}}{\sum }}{w}_j^{i,l}}\ge {\displaystyle \underset{j=1}{\overset{n_{i+q,l+1}}{\sum }}{w}_j^{i+q,l+1}}$，则有

$\begin{array}{c}f\left({\sigma }_1\right)-f\left({\sigma }_2\right)\\ ={\displaystyle \underset{1}{\overset{n_{i,l}}{\sum }}{w}_j^{i,l}{C}_j^{i,l}}+{\displaystyle \underset{1}{\overset{n_{i,l+1}}{\sum }}{w}_j^{i,l+1}{C}_j^{i,l+1}}+{\displaystyle \underset{1}{\overset{n_{i+q,l}}{\sum }}{w}_j^{i+q,l}{C}_j^{i+q,l}}+{\displaystyle \underset{1}{\overset{n_{i+q,l+1}}{\sum }}{w}_j^{i+q,l+1}{C}_j^{i+q,l+1}}\\ -{\displaystyle \underset{1}{\overset{n_{i+q,l+1}}{\sum }}{w}_j^{i+q,l+1}\left[C_j^{i+q,l+1}-\left(T+t\right)\right]}-{\displaystyle \underset{1}{\overset{n_{i,l+1}}{\sum }}{w}_j^{i,l+1}{C}_j^{i,l+1}}-{\displaystyle \underset{1}{\overset{n_{i+q,l}}{\sum }}{w}_j^{i+q,l}{C}_j^{i+q,l}}-{\displaystyle \underset{1}{\overset{n_{i,l}}{\sum }}{w}_j^{i,l}\left[C_j^{i,l}+\left(T+t\right)\right]}\\ ={\displaystyle \underset{1}{\overset{n_{i,l}}{\sum }}{w}_j^{i,l}{C}_j^{i,l}}+{\displaystyle \underset{1}{\overset{n_{i+q,l+1}}{\sum }}{w}_j^{i+q,l+1}{C}_j^{i+q,l+1}}-{\displaystyle \underset{1}{\overset{n_{i+q,l+1}}{\sum }}{w}_j^{i+q,l+1}\left[C_j^{i+q,l+1}-\left(T+t\right)\right]}-{\displaystyle \underset{1}{\overset{n_{i,l}}{\sum }}{w}_j^{i,l}\left[C_j^{i,l}+\left(T+t\right)\right]}\\ \text{=}{\displaystyle \underset{1}{\overset{n_{i+q,l+1}}{\sum }}{w}_j^{i+q,l+1}\left(T+t\right)}-{\displaystyle \underset{1}{\overset{n_{i,l}}{\sum }}{w}_j^{i,l}\left(T+t\right)}\\ \text{=}\left({\displaystyle \underset{1}{\overset{n_{i+q,l+1}}{\sum }}{w}_j^{i+q,l+1}}-{\displaystyle \underset{1}{\overset{n_{i,l}}{\sum }}{w}_j^{i,l}}\right)\left(T+t\right)\\ \le 0.\end{array}$

由以上不等式可知，当批次按照权重和由大到小排列时，其加权总完工时间小于其他调度方案结果。因此，在最优调度方案中，所有平行机的批次的权重和都应该是由大到小的，不同机器的批次的权重和也是。证毕。

性质3：在最优调度方案中，任一批次内的工件都是按照WSPT规则排序的。

证 明 我们知道，同一批次内工件的加工不需要维护。对于无约束的单机调度问题 $1\text{||}{\displaystyle \sum w_j}{C}_j$，我们知道WSPT规则可以得到最优调度方案。因此，在最优调度方案中，任一批次内的工件都应按照WSPT规则排序。证毕。

性质4：在最优调度方案中，在加工了工件 $J_j$ 的批次前，所有平行机都没有可以加工工件 $J_j$ 的空闲时间。

证 明 不失一般性，假设在调度方案 $\sigma$ 为最优调度中，工件 $J_j$ 被安排在机器 $M_i$ 的第 $l+1$ 批次 $B_{i,l\text{+}1}$ 内加工，完工时刻为 $C_j$。且机器 $M_{i\text{+}q}$ 的第 $l$ 个批次 $B_{i,l}$ 内有可以加工工件 $J_j$ 的空闲时间。若将工件 $J_j$ 放入批次 $B_{i,l}$ 内加工，其余工件不变，其目标函数为 $f$，则不等式 $f\left(\sigma \right)-f\ge w_j\left(t+p_j\right)>0$ 成立。故，在最优调度方案中， 在加工了工件 $J_j$ 的批次前，所有平行机都没有可以加工工件 $J_j$ 的空闲时间。证毕。

对于单机调度问题 $1\text{||}{\displaystyle \sum w_j}{C}_j$，根据WSPT规则可以得到最优调度方案。在多机环境中，当有多台机器均可以加工工件时，应该安排在哪一台机器上加工会有更优的结果，我们是不知道的。工件完成时间优先(JCT)、机器完成时间优先(MCT)作为两种工件分配机制被何杰(文献 [12] )提出用于解决最小化时间表长的车间调度。因此，我们可以将这两个工件分配机制以及FF规则与WSPT规则结合考虑，提出以下算法。

4.2. WSPTJCT算法

步骤1：将所有工件按照WSPT规则排序，不失一般性，假设 $\frac{w_1}{p_1}\ge \frac{w_2}{p_2}\ge \cdots \ge \frac{w_n}{p_n}$ ；若 $\frac{w_j}{p_j}=\frac{w_{j+q}}{p_{j+q}}$，且

$p_j\ge p_{j+q}$，则工件 $J_j$ 排在 $J_{j\text{+}p}$ 前；

步骤2：若工件 $J_j$ 按照FF规则在机器 $M_i$ 上加工的当前完成时刻 $C_j^i$ 不大于在其他机器上加工的完成时刻，则将工件 $J_j\left(j=1,2,\cdots ,n\right)$ 按照FF规则安排在机器 $M_i$ 上加工；

步骤3：将所有批次按照其权重和由大到小排，依次放入各机器上；

步骤4：计算目标值 $f_{WSPTJCT}={\displaystyle \sum w_j}{C}_j$。

4.3. WSPTMCT算法

步骤1：将所有工件按照WSPT规则排序，不失一般性，假设 $\frac{w_1}{p_1}\ge \frac{w_2}{p_2}\ge \cdots \ge \frac{w_n}{p_n}$ ；若 $\frac{w_j}{p_j}=\frac{w_{j+q}}{p_{j+q}}$，且

$p_j\ge p_{j+q}$，则工件 $J_j$ 排在 $J_{j\text{+}p}$ 前；

步骤2：若按照FF规则加工工件 $J_j$ 后，机器 $M_i$ 的当前完成时刻不大于其他机器加工完工件 $J_j$ 的完成时刻，则将工件 $J_j\left(j=1,2,\cdots ,n\right)$ 按照FF规则安排在机器 $M_i$ 上加工；

步骤3：将所有批次按照其权重和由大到小排，依次放入各机器上；

步骤4：计算目标值 $f_{WSPTMCT}={\displaystyle \sum w_j}{C}_j$。

4.4. WSPTBF算法

步骤1：将所有工件按照WSPT规则排序，不失一般性，假设 $\frac{w_1}{p_1}\ge \frac{w_2}{p_2}\ge \cdots \ge \frac{w_n}{p_n}$ ；若 $\frac{w_j}{p_j}=\frac{w_{j+q}}{p_{j+q}}$，且

$p_j\ge p_{j+q}$，则工件 $J_j$ 排在 $J_{j\text{+}p}$ 前；

步骤2：将所有工件按照BF规则依次放入各机器上；

步骤3：将所有批次按照其权重和由大到小排，依次放入各机器上；

步骤4：不失一般性，假设时间表长在平行机 $M_1$ 的第 $l$ 个批次内取得，若每台平行机的使用的批次个数不完全相同，则将每一台平行机的第 $l$ 个批次内的工件全部取出，按照WPSTJCT算法放在 $m$ 台平行机上加工；

步骤5：计算目标值 $f_{WSPTBF}={\displaystyle \sum w_j}{C}_j$。

4.5. ROPT算法

计算目标值 $f_{ROPT}=\min \left\{f_{WSPTJCT},f_{WSPTMCT},f_{WSPTBF}\right\}$。

5. 数值实验

下面我们将通过数值实验来比较WSPTJCT算法、WSPTMCT算法、WSPTBF算法以及ROPT算法的性能的相对优劣。各实验的工件的加工时长均为某时间区间 $\left[1,p_{\max }\right]$ 上均匀分布随机生成的正整数，其中 $p_{\max }$ 为工件最大加工时长。

5.1. $\frac{w_j}{p_j}$ 为任意一组正数

为考察WSPTJCT算法、WSPTMCT算法、WSPTBF算法以及ROPT算法与最大加工时长 $p_{\max }$ 的关系。此数值实验选取了 $p_{\max }=20,40,60,80,100$， $n=400$， $T=100$， $t=2$， $m=2$。工件权重 $w_i$ 在区间 $\left[1,10\right]$ 上随机生成。共有5组参数，对不同的参数都随机的生成100个实例。

由图1可以知道，当 $n=400$ 时，在相同参数下，这4个算法的性能与 $p_{\max }$ 的大小呈倒U型，当 $p_{\max }=80$ 时，WSPTJCT算法、WSPTMCT算法、WSPTBF算法以及ROPT算法的性能最好；ROPT算法的性能优于WSPTJCT算法、WSPTMCT算法、WSPTBF算法；WSPTBF算法优于WSPTMCT算法及WSPTJCT算法；WSPTMCT算法优于WSPTJCT算法。

Figure 1. The relationship between performance of algorithms and maximum processing time $p_{\max }$

图1. 算法性能与最大加工时长 $p_{\max }$ 的关系

为考察WSPTJCT算法、WSPTMCT算法、WSPTBF算法以及ROPT算法与工件加工个数 $n$ 的关系。此数值实验选取了 $n=100,200,400,600,800,1000,1500,2000$。 $p_{\max }=100$， $T=100$， $t=2$， $m=2$。工件权重在区间 $\left[1,10\right]$ 上根据均匀分布随机生成。共有9组参数，对不同的参数都随机的生成100个实例。

由图2可以知道，在相同参数下：加工个数n越大，WSPTJCT算法、WSPTMCT算法、WSPTBF算法以及ROPT算法的性能越好。

Figure 2. The relationship between performance of algorithms and the number of jobs n

图2. 算法性能与工件加工个数n的关系

相对而言，ROPT算法的性能优于WSPTJCT算法、WSPTMCT算法、WSPTBF算法；WSPTBF算法优于WSPTMCT算法及WSPTJCT算法；WSPTMCT算法优于WSPTJCT算法；当 $n\ge 800$ 时，WSPTMCT算法、WSPTBF算法以及ROPT算法的性能几乎一致，但WSPTJCT算法的性能始终劣于其他三个算法。

5.2. $\frac{w_j}{p_j}$ 为一组单调不减的正数

由于在现实生产车间中存在以工作时长评估订单的重要性的情况，故在以下实验中假设 $\frac{w_j}{p_j}$ 为一组单调不减的正数，根据WSPT规则可知，工件是根据 $p_j$ 由大到小排序的。由WSPTJCT算法、WSPTMCT算法以及WSPTBF算法的步骤1可知，若 $\frac{w_j}{p_j}=1\left(1\le j\le n\right)$，步骤1的排序结果也是根据 $p_j$ 由大到小排序的。因此， $\frac{w_j}{p_j}=1\left(1\le j\le n\right)$ 是该情况的一个特例。

为考察WSPTJCT算法、WSPTMCT算法、WSPTBF算法以及ROPT算法与最大加工时长 $p_{\max }$ 的关系。此数值实验选取了 $p_{\max }=20,40,60,80,100$， $T=100$， $t=2$， $m=2$， $n=400$。共有5组参数，对不同的参数都随机的生成100个实例。

由图3可以知道，当 $n=400$ 时，在相同参数下，其性能变化与图1相似，但其拐点为60而非80。

为考察WSPTJCT算法、WSPTMCT算法、WSPTBF算法以及ROPT算法与工件加工个数 $n$ 的关系。此数值实验选取了 $n=100,200,400,600,800，1000,1500,2000$， $T=100$， $t=2$， $m=2$， $p_{\max }=100$。共有9组参数，对不同的参数都随机的生成100个实例。

由图4可以知道，在相同参数下其性能变化与图1相似，但存在以下两点不同：

(1) 当 $n\le 400$ 时，WSPTJCT算法、WSPTMCT算法、WSPTBF算法以及ROPT算法的性能变化较快；当 $n>400$ 时，四个算法性能变化较慢；

(2) 相对而言，图4的WSPTJCT算法的性能与其他三个算法的性能差没有图2的大，当 $n>800$ 时，四个算法性能差别不大，而图2中WSPTJCT算法的性能始终小于其他3个算法。

Figure 3. The relationship between performance of algorithms and maximum processing time $p_{\max }$ for a group of non-decreasing positive numbers $\frac{w_j}{p_j}$

图3. $\frac{w_j}{p_j}$ 为一组单调不减的正数时，算法性能与最大加工时长 $p_{\max }$ 的关系

Figure 4. The relationship between performance of algorithms and the number of jobs n for a group of non-decreasing positive numbers $\frac{w_j}{p_j}$

图4. $\frac{w_j}{p_j}$ 为一组单调不减的正数时，算法性能与工件加工个数n的关系

6. 结束语

对于具有周期维护，目标函数为最小化加权总完工时间的平行机调度问题，提出了4个性质，根据性质以及3个工件分配机制提出了4个近似算法，并通过数值实验对4个启发式算法进行了性能分析。结果显示：WSPTJCT算法、WSPTMCT算法、WSPTBF算法、ROPT算法的性能依次增强；相对而言，且各算法的性能与最大加工时长 $p_{\max }$ 呈倒U型与加工个数 $n$ 呈正相关。从该结果中我们知道WSPTBF的算法性能比WSPTJCT和WPSTMCT算法好，这提供了一个思路就是将该算法应用于恒速机调度问题中其性能将如何变化，我们下一步将对此展开研究。