具有先序约束的平行机排序问题

Parallel Machine Scheduling Problem with Precedence Constraints

摘要: 根据财务系统中的回避原则，构造了具有先序约束的平行机排序问题的模型，目标函数为最小化最大负载，证明了具有先序约束的平行机排序问题是一个NP-完备问题。为之设计了LPTM算法，并分析了其近似比为3-1/m。

Abstract: According to the avoidance principle in the financial system, a model of the parallel machine scheduling problem with precedence constraints is constructed, and the objective function is to minimize the maximum load, which is proved that the parallel machine scheduling problem with precedence constraints is an NP-complete problem. We design the LPTM algorithm and analyze its approximate ratio to 3-1/m.

1. 引言

在财务系统中，同一个服务者即可以核算，也可以总付。对于同一工件，服务者进行核算就不能进行总付，且每个工件的核算要在总付之前。因此，需要制定相应的分配策略，使得工件量较大时，尽可能在较短的时间完成工作。此问题实际上可以转化成具有先序约束的平行机排序问题。由于该问题在现实生活中有着广泛的应用，深受大家的重视，一直以来都有许多的研究者对此类问题进行研究。用Graham等 [1] 提出的三符号表示法来表示拟研究的排序问题。

在具有先序的平行机排序问题中，对于加工不允许被打断的情况Prot等 [2] 在2018年的一项调查中描述了先序约束结构是如何改变一个排序问题的复杂性的。Sarahí Báez等 [3] 在2019年对具有开始时间约束的平行机排序问题设计了混合元启发算法。2019年柴幸 [4] 对带有工件约束的平行机排序问题的近似算法进行了研究，考虑了m台平行机上工件带有链组约束的在线排序，工件具有相同的加工长度，目标是最小化最大完工时间。考虑了 $m\ge 3$ 的情形。证明该问题在线算法竞争比的下界为 $1+{\alpha }_m$，其中当 $3\le m\le 5$ 时， ${\alpha }_m$ 是方程 ${\alpha }_m^2+3{\alpha }_m-1=0$ 的唯一正根；当 $m\ge 6$ 时， ${\alpha }_m$ 是方程 ${\alpha }_m^3+4{\alpha }_m^2+5{\alpha }_m-2=0$ 的唯一正根。其次给出达到该竞争比的最好可能的在线算法。

2021年Lee等 [5] 对于平行机的理想排序做了调查和总结，通过对比发现，经过几十年的研究，已经取得了一些研究成果，但对于具有先序约束的平行机排序问题找到最优排序依旧困难。 $Pm|prec,p_j=p|C_{\max }$ 是Dolev等 [6] 研究的问题的一个特殊情况。本文所研究的问题相比较 $Pm|prec,p_j=p|C_{\max }$，不同点在于 $p_i\ne p_j,i\ne j$。

Graham [7] 证明，如果没有优先约束，并且根据LPT (最长处理时间优先)算法对工件进行排序，

$P_m\parallel C_{\max }$ 在LPT算法下的近似比为 $\frac{4}{3}$，受LPT算法的启发，本文针对具有先序约束的平行机排序问题设计了LPTM算法，并分析当每台机器只含有一个第一道工序时近似比为 $3-\frac{1}{m}$，当每台机器至少含两个第一道工序时近似比为 $\frac{5}{2}-\frac{1}{2m}$。

2. 问题描述

2.1. 问题的数学模型描述

2.1.1. 理论模型

m台机器，n个工件，每个工件i有两道工序，记为i1、i2，i1要先于i2完成，用符号表示，即 $i1\prec i2$，完成i1、i2的时间记为 $t_{i1}$， $t_{i2}$，且i1与i2不能在同一台机器上加工。目标为将n个工件的两道工序分配到m台机器上，最后完工的机器运行时间达到最小。

$z=\min C_{\max }=\min \left\{{\max }_{1\le k\le m}\left({\displaystyle \underset{i=1}{\overset{n}{\sum }}{t}_{i1}\cdot z_{i1k}}\right)+{\max }_{1\le k\le m}\left({\displaystyle \underset{i=1}{\overset{n}{\sum }}{t}_{i2}\cdot z_{i2k}}\right)\right\}$ (1)

$C_{i1}\le S_{i2}$ (2)

$0\le z_{i1k}+z_{i2k}\le 1$ (3)

${\displaystyle \underset{k=1}{\overset{m}{\sum }}{z}_{i1k}}=1,{\displaystyle \underset{k=1}{\overset{m}{\sum }}{z}_{i2k}}=1$ (4)

${\displaystyle \underset{j=1}{\overset{2n}{\sum }}{z}_{i1k_j}}=1,{\displaystyle \underset{j=1}{\overset{2n}{\sum }}{z}_{i2k_j}}=1$ (5)

$z_{i1k},z_{i2k},z_{i1k_j},z_{i2k_j}\in \left\{0,1\right\}$ (6)

$t_{i1}=t_{i1k},t_{i2}=t_{i2k}$ (7)

$1\le i\le n,1\le k\le m$ (8)

(1)表示目标函数，使负载最大的机器加工所用的时间最小，(2)表示i1完成之后i2的加工才可以开始，(3)表示同一个工件的不同工序不能在同一台机器上加工，(4)、(5)表示i1和i2在加工的过程中不会被打断，(6)表示i1或i2是否在第k台机器上加工，或者是否在第k台机器的第j个位置加工，若在则为1，反之为0，(7)表示i1和i2在不同机器上的加工时间相等，(8)表示i，k的取值范围。

2.2. 问题的NP-完全性证明

定理1具有先序约束的平行机排序问题是一个NP-完备问题。

证明：我们把2-划分问题的任何一个实例多项式归结到工件不同工序不能在同一台机器上加工的平行机排序问题的一个实例。

考虑2-划分问题的一个实例P：给定了n个数的集合 $A=\left\{a_1,a_2,\cdots ,a_n\right\}$。问是否存在A一个划分 $A_1,A_2$ 使得： $A_1\cap A_2=\varnothing$， $A_1\cup A_2=A$，满足 ${\displaystyle \underset{a_{1j}\in A_1}{\sum }{a}_{1j}}={\displaystyle \underset{a_{2j}\in A_2}{\sum }{a}_{2j}}=B$ ？

构造工件不同工序不能在同一台机器上加工的平行机排序问题的实例P'如下：

$I=\left\{11,21,\cdots ,n1,12,22,\cdots ,n2\right\}$, $M=\left\{m_1,m_2\right\}$, $t\left(i1\right)=a_i$, ${\displaystyle \underset{i=1}{\overset{n}{\sum }}t\left(i1\right)=2B}$, $t\left(i2\right)=0$, $\left(i=1,2,\cdots ,n\right)$.

下面证明论断：2-划分问题的实例P有解当且仅当工件不同工序不能在同一台机器上加工的平行机排序问题的实例P'有目标函数值为B的最优解。

(必要性)设2-划分问题的实例P有解为

$A_1=\left\{a_1,a_2,\cdots ,a_t\right\}$, $A_2=\left\{a_{t+1},a_{t+2},\cdots ,a_n\right\}$.

下面构造P'的可行解 $M_1,M_2$。由于

$t\left(M_k\right)={\displaystyle \underset{i1\in M_k}{\sum }t\left(i1\right)}+{\displaystyle \underset{i2\in M_k}{\sum }t\left(i2\right)}={\displaystyle \underset{a_i\in A_k}{\sum }{a}_i}=B,k=1,2$

说明 $M_1,M_2$ 是P'有目标函数值为B的一个最优解。

(充分性)设工件不同工序不能在同一台机器上加工的平行机排序问题的实例P'有目标函数值为B的最优解 $M_1,M_2$ 有

$t\left(M_k\right)={\displaystyle \underset{i1\in M_k}{\sum }t\left(i1\right)}+{\displaystyle \underset{i2\in M_k}{\sum }t\left(i2\right)}={\displaystyle \underset{a_i\in A_k}{\sum }{a}_i}=B,k=1,2$

取 $A_1=\left\{a_1,a_2,\cdots ,a_t\right\}$， $A_2=\left\{a_{t+1},a_{t+2},\cdots ,a_n\right\}$，则 ${\displaystyle \underset{a_i\in A_1}{\sum }{a}_i}={\displaystyle \underset{a_i\in A_2}{\sum }{a}_i}=B$，说明2-划分问题有解 $A_1=\left\{a_1,a_2,\cdots ,a_t\right\}$， $A_2=\left\{a_{t+1},a_{t+2},\cdots ,a_n\right\}$。

由于2-划分问题是NP-完全的 [7]，说明，工件不同工序不能在同一台机器上加工的平行机排序问题的实例P'也是完全的。因此，工件不同工序不能在同一台机器上加工的平行机排序问题是一个NP-完备问题。

3. 算法设计思路

首先按LPT算法将i1 ( $i=1,2,\cdots ,n$ )安排在m台机器上，此时得到m个互不相交的集合 $I{1}_1,I{1}_2,\cdots ,I{1}_m$， $I{1}_j$ 表示在第j台机器上加工的i1所组成的集合，加工 $I{1}_j$ 中的i1所用的时间为 $t\left(I{1}_j\right)$， $j=1,2,\cdots ,m$。令集合 $I1=\left\{I{1}_1,I{1}_2,\cdots ,I{1}_m\right\}$。

其次，以负载最大的机器加工时间 $C_1=\max \left\{t\left(I{1}_1\right),t\left(I{1}_2\right),\cdots ,t\left(I{1}_m\right)\right\}$ 作为所有i2最早开始加工时间，此时相应会产生m个互不相交的集合 $I{2}_1,I{2}_2,\cdots ,I{2}_m$，令集合 $I2=\left\{I{2}_1,I{2}_2,\cdots ,I{2}_m\right\}$， $I{2}_j\left(j=1,2,\cdots ,m\right)$

表示在第j台机器上加工的i1对应的i2所组成的集合。

最后，依次将 $I{2}_j\left(j=1,2,\cdots ,m\right)$ 中的i2按LPT算法分配到除第j台机器外的其他m-1台机器上加工。在分配 $I{2}_m$ 时，若 $t\left(m_{i2}\right)=\max \left\{t\left(1_{i2}\right),t\left(2_{i2}\right),\cdots ,t\left(m_{i2}\right)\right\}$，将大于其他机器加工时间所安排的 $i{2}_k$ 取出，按LPT算法排到除第k台机器与第m台机器外的其他m-2台机器上。反之将 $I{2}_m$ 中的i2按LPT算法分配到除第m台机器外的其他m-1台机器上。令 $t\left(j_{i2}\right),\left(j=1,2,\cdots ,m\right)$ 表示分配完所有i2，第j台机器加工i2的时间。此时，最大负载的机器加工时间为 $t\left(M_j\right)=C_1+\max \left\{t\left(1_{i2}\right),t\left(2_{i2}\right),\cdots ,t\left(m_{i2}\right)\right\}$。

4. 算法设计

LPTM

输入：具有先序约束的平行机排序问题的一个实例 $P=\left(m>2,n,t_{i1},t_{i2}\right)$。

Begin

输出：最大负载的机器所加工的时间 $t\left(M_j\right)$。

Step 1按LPT算法对n个工件的第一道工序进行分配，分配完成得最大负载机器所加工的总时间为

$C_1$，得到集合 $I1=\left\{I{1}_1,I{1}_2,\cdots ,I{1}_m\right\}$ 与 $I2=\left\{I{2}_1,I{2}_2,\cdots ,I{2}_m\right\}$，记此时 $t\left(M_1\right)=t\left(M_2\right)=\cdots =t\left(M_m\right)=C_1$。

Step 2 $k=1$，m台机器加工i2的最早开始时间均为 $C_1$。将 $I{2}_k$ 中的i2按LPT分配到除第k台及其外的m-1台机器，得到此时每台机器上加工的时间

$t\left(M_1\right)=t\left(M_1\right)+t\left(1_{i2}\right),t\left(M_2\right)=t\left(M_2\right)+t\left(2_{i2}\right),\cdots ,t\left(M_m\right)=t\left(M_m\right)+t\left(m_{i2}\right)$。

Step 3 若 $k<m$，转Step 2，否则转Step 4。

Step 4 若 $k=m$，转4.1，否则转4.2。

4.1 若此时最大负载的机器为第m台机器，则取出多出的工件 $i{2}_j$，按LPT规则排到除第j台和第m台机器外的其他机器上，否则，转Step 2。

4.2 输出最大负载的机器所加工的时间 $t\left(M_j\right)=\max \left\{t\left(M_1\right),t\left(M_2\right),\cdots ,t\left(M_m\right)\right\}$。

End

例 考虑工件不同工序不能在同一台机器上加工的平行机排序问题，其中m = 4，n = 10， $t_{i1}=t_{i2}=1$，求其算法1排序及相应的时间表长。

OPT = 5 (如图1所示)

Figure 1. Example of parallel machine sequencing where different processes cannot be processed on the same machine

图1. 不同工序不能在同一台机器上加工的平行机排序实例

5. 算法的可行性分析

由于LPT算法的时间复杂度为 $O\left(n\log n\right)$，易得LPTM算法的时间复杂度也为 $O\left(n\log n\right)$。

定理2 [8] 对于 $Pm|C_{mac}$，LPT算法是 $\frac{4}{3}$ 近似算法。

定理3 LPTM₂算法是 $3-\frac{1}{m}$ 近似算法。

证明：考虑负载最大的机器 $M_j$，令n1表示最后分配的i1，n2表示最后分配的i2。

因为

$OP{T}^{\ast }\ge \frac{1}{m}\left({\displaystyle \underset{i=1}{\overset{n}{\sum }}{t}_{i1}}+{\displaystyle \underset{i=1}{\overset{n}{\sum }}{t}_{i2}}\right)$

$OP{T}^{\ast }>t_{n1},OP{T}^{\ast }>t_{n2}$

$\begin{array}{c}t\left(M_j\right)\le \frac{1}{m}\left({\displaystyle \underset{i=1}{\overset{n}{\sum }}{t}_{i1}}-t_{n1}\right)+t_{n1}+\frac{1}{m-1}\left({\displaystyle \underset{i=1}{\overset{n}{\sum }}{t}_{i2}}-t_{n2}\right)+t_{n2}\\ =\frac{1}{m}\left({\displaystyle \underset{i=1}{\overset{n}{\sum }}{t}_{i1}}+{\displaystyle \underset{i=1}{\overset{n}{\sum }}{t}_{i2}}\right)+\left(1-\frac{1}{m}\right)t_{n1}+\left(\frac{1}{m-1}-\frac{1}{m}\right){\displaystyle \underset{i=1}{\overset{n}{\sum }}{t}_{i2}}+\left(1-\frac{1}{m-1}\right)t_{n2}\\ <OP{T}^{\ast }+\left(1-\frac{1}{m}\right)OP{T}^{\ast }+\frac{1}{m-1}OP{T}^{\ast }+\left(1-\frac{1}{m-1}\right)OP{T}^{\ast }\\ <\left(3-\frac{1}{m}\right)OP{T}^{\ast }\end{array}$

所以

$\frac{t\left(M_j\right)}{OP{T}^{\ast }}<3-\frac{1}{m}$

得证。

注：当每台机器只含有一个第一道工序时近似比为 $3-\frac{1}{m}$，当每台机器至少含两个第一道工序时，由于 $OP{T}^{\ast }>2t_{n1}$，所以此时近似比为 $\frac{5}{2}-\frac{1}{2m}$。

6. 结语

根据财务系统中的回避原则，构造了具有先序约束的平行机排序问题的数学模型，参考LPT算法对两台及多台机器设计出LPTM算法来解决此类问题，并证明此问题是一个NP-完备问题，同时分析得算法的近似比。为财务系统中工作分配提供了新的思路，有一定的现实意义和应用价值。本文只研究了每个工件有两道工序的情形，后续还可以研究每个工件有超过两道工序以及每个工件的工序数不尽相同的情况。

NOTES

^*通讯作者。