Two-Agent Parallel-Batch Scheduling with Split Orders

本文研究的问题正式描述如下：两个代理(A和B)分别有工件(排序论中，常用工件表示诸如“订单”等加工任务)集合J^A={J₁^A，J₂^A，…，J_nA^A}和J^B={J₁^B，J₂^B，…，J_nB^B}，其中n_A和n_B分别表示代理A和代理B的工件数，且J^A∩J^B=φ. 两个代理竞争使用同一台机器加工各自工件. 每个工件J_j^X(X∈{A，B})有相同的长度或加工时间p，不同的尺寸(对应于订单中产品数量)q_j^X. 此外，代理B的每个工件J_j^B还有一个费用函数f_j^B(t). 本文假设所有费用函数f_j^B(t)，1≤j≤n_B均是正则的，即是关于完工时间t的非减函数. (平行批)机器分批加工工件，容量为b. 每一批的加工时间均为p. 工件都可以拆分为多个部分并连续地在机器上加工. 要求在同一批内加工的工件(或部分)的总尺寸不超过机器容量，且对被拆分的工件，每一部分一旦完工立刻交付. 假设q_j^X≤b < ∑_{Jj^X∈J^A∪J^B}q_j^X，则每个工件或完全在某批中加工，或被拆分成两部分并在两个相邻批中加工. 但是，由于化学性质等因素影响，假设来自不同代理的工件不能安排在同一批内加工.

令σ为任一可行排序(调度又称排序). 在σ中，若工件J_j^X，X∈{A，B}完全在代理B的第k批工件中加工，则定义其完工时间C_j^X(σ)与加工费用f_j^X(σ)为

若工件J_j^X，X∈{A，B}被拆分为两部分，其中一部分(尺寸为α_j^X)在第k批ψ_k中加工，剩下的部分(尺寸为q_j^X－α_j^X)在第k+1批ψ_k+1中加工，则定义其完工时间C_j^X(σ)与加工费用f_j^X(σ)为

进而用∑_1≤j≤nAC_j^A(σ)表示代理A的工件的完工时间之和，用f_max^B(σ)=max_1≤j≤nBf_j^B(σ)表示代理B的工件的最大加工费用. 采用文献[7]的记号，本文考虑的问题可表示为

其中：1代表一台批机器；β代表工件特征，蕴含工件可拆分、不同代理的工件不相容等信息；最后一部分代表目标函数，具体地，在满足代理B的工件的最大加工费用f_max^B不超过门槛值Q的条件下，最小化代理A的工件的完工时间之和∑C_j^A.

注意，由于目标函数∑C_j^A和f_max^B都是正则的，所以在下文中只需考虑满足如下性质的可行排序即可：①从零时刻开始一批接一批地连续加工，相邻批之间不存在空闲时间；②除了最后一批以外，每一批都填满了工件，即该批中工件(或部分)的总尺寸等于机器容量.

本节首先证明一般情形问题1|β|∑C_j^A：f_max^B≤Q是NP难的，然后对其中一种特殊情形给出多项式时间算法.

本小节首先描述著名的NP完全问题^[17]——等规模划分问题(equal size partition，ESP)的一种限制形式(restricted equal size partition，RESP)，并通过将ESP多项式归结为RESP，证明RESP也是NP完全问题. 接着，将RESP多项式归结为问题1|β|∑C_j^A：f_max^B≤Q，从而证明1|β|∑C_j^A：f_max^B≤Q是NP难的.

1) ESP问题. 给定2m+1个正整数a₁，a₂，…，a_2m和C，满足∑_1≤j≤2ma_j=2C，问是否存在指标集{1，2，…，2m}的一个划分(I₁，I₂)，使得∑_j∈I1a_j=∑_j∈I2a_j=C且|I₁|=|I₂|？

2) RESP问题. 给定2m+1个正整数a₁，a₂，…，a_2m和C，满足∑_1≤j≤2ma_j=2C，且对任意的1≤j≤2m，有$ \frac{\bar{C}}{m+1} \leqslant \bar{a}_{j} \leqslant \frac{\bar{C}}{m-1} $. 问是否存在指标集{1，2，…，2m}的一个划分(I₁，I₂)，使得∑_j∈I1a_j=∑_j∈I2a_j=C且|I₁|=|I₂|？

引理1  RESP是NP完全问题.

证  显然，RESP属于NP类. 令(a₁，a₂，…，a_2m，C)为ESP的一个实例. 不失一般性，可假设m≥2且a₁≤a₂≤…≤a_2m. 定义RESP的实例(a₁，a₂，…，a_2m，C)如下：

由(3)式可知，Δ>C－(m+1)a₁，Δ>(m－1)a_2m－C，也有$ a_{1}>\frac{C-\varDelta}{m+1}, a_{2 m}<\frac{C+\varDelta}{m-1} $，于是

进而，因a₁≤a₂≤…≤a_2m，故对任意1≤j≤2m，有

又由于

因此，上面构造的实例确实是问题RESP的一个实例.

明显地，上述实例的构造可以在多项式时间内完成，并且(a₁，a₂，…，a_2m，C)是ESP的YES实例当且仅当(a₁，a₂，…，a_2m，C)是RESP的YES实例.

注意到，由于所有费用函数f_j^B(t)，1≤j≤n_B都是正则的，所以，对于给定的门槛值Q，“条件f_max^B≤Q”等价于“代理B的每个工件J_j^B，1≤j≤n_B都有一个截止交货期(最迟完工时间)d_j^B”. 具体地，定义

因而，本文研究的问题也可等价表示为1|β；d_j^B|∑C_j^A.

引理2  问题1|β；d_j^B|∑C_j^A是NP困难的.

证  显然，此排序问题的判定形式属于NP类. 给定RESP的一个实例(a₁，a₂，…，a_2m，C)，定义排序问题的实例如下：

1) 共有n=2m+1个工件J₁，J₂，…，J_2m+1，其中，前2m个工件均属于代理A，只有最后一个工件属于代理B. 所有工件的加工时间均为1. 工件J_j(1≤j≤2m)的尺寸为q_j=a_j，工件J_2m+1的尺寸为q_2m+1=C. 工件J_2m+1的截止交货期为d_2m+1=2.

2) 机器容量为b=C. 设置门槛值Q_A=4m.

对于上述排序实例，问题1|β；d_j^B|∑C_j^A的判定形式可描述为：是否存在可行排序σ使得∑C_j^A(σ)≤Q_A？

明显地，上述实例的构造过程可以在多项式时间内完成. 接下来，证明(a₁，a₂，…，a_2m，C)是RESP的YES实例当且仅当上面构造的排序实例存在可行排序σ使得∑C_j^A(σ)≤Q_A.

首先，假设(a₁，a₂，…，a_2m，C)是RESP的YES实例，则存在指标集{1，2，…，2m}的一个划分(I₁，I₂)，使得∑_j∈I1a_j=∑_j∈I2a_j=C且|I₁|=|I₂|=m. 令ψ₁={J_j：j∈I₁}，ψ₂={J_2m+1}，ψ₃={J_j：j∈I₂}. 定义排序σ=(ψ₁，ψ₂，ψ₃). 对于σ，代理B的唯一工件J_2m+1的完工时间C_2m+1(σ)=2=d_2m+1，代理A的工件的完工时间之和为

因此，σ是排序实例满足要求的可行排序.

接着，假设排序实例存在可行排序σ使得∑C_j^A(σ)≤Q_A. 由工件J_2m+1的尺寸和截止交货期以及工件的可拆分性可知，在σ中只有如下3种情形可能发生：

情形1  J_2m+1完全填满第一批ψ₁，即ψ₁={J_2m+1}. 则其他(属于代理A)工件将填满第二批ψ₂和第三批ψ₃，可能会有某个工件被拆分成两部分，一部分在ψ₂，另一部分在ψ₃. 由于$ \frac{\bar{C}}{m+1} \leqslant \bar{a}_{j} \leqslant \frac{\bar{C}}{m-1}, b=\bar{C}$，故ψ₂中至多包含m个完整工件和某个工件的一部分，ψ₃至少包含m－1个完整工件和某个工件的一部分. 因而，代理A的工件的完工时间之和为

这与假设∑C_j^A(σ)≤Q_A相矛盾，故此种情形不会发生.

情形2  J_2m+1被拆分成两部分，其中一部分在第一批ψ₁，另一部分在第二批ψ₂. 由于来自不同代理的工件不能在同一批中加工，故其他工件将填满第三批ψ₃和第四批ψ₄，可能会有某个工件被拆分成两部分，其中一部分在ψ₃，另一部分在ψ₄. 类似情形1中结尾部分的证明，可得

与假设∑C_j^A(σ)≤Q_A相矛盾，故此种情形也不会发生.

情形3  J_2m+1完全填满第二批ψ₂，即ψ₂={J_2m+1}. 则代理A的工件将会被安排在第一批ψ₁和第三批ψ₃，也可能有工件全部或部分在第四批ψ₄. 进一步，假设在ψ₁中加工的工件的总尺寸小于机器容量b. 由于代理A的工件的尺寸之和为2C=2b，故一定会有某个工件全部或部分被安排在了ψ₄. 因为ψ₁和ψ₃各自至多包含m个完整工件，所以代理A的工件的完工时间之和为

这再次与假设∑C_j^A(σ)≤Q_A相矛盾，故在ψ₁中加工的工件的总尺寸恰好等于机器容量b，自然地，ψ₃中加工的工件的总尺寸也等于机器容量b. 又由$ \frac{\bar{C}}{m+1} \leqslant \bar{a}_{j} \leqslant \frac{\bar{C}}{m-1}, b=\bar{C} $可知，ψ₁和ψ₃中各自包含了m个工件. 定义I₁={j：J_j∈ψ₁}，I₂={j：J_j∈ψ₃}. 明显地，(I₁，I₂)构成了指标集{1，2，…，2m}的一个划分，使得∑_j∈I1a_j=∑_j∈I2a_j=C且|I₁|=|I₂|=m.

由引理2可直接得到下面的定理.

定理1  问题1|β|∑C_j^A：f_max^B≤Q是NP-难的.

本小节考虑问题1|β|∑C_j^A：f_max^B≤Q的一个特殊情形：代理A的所有工件有相同的尺寸q_j^A=q，1≤j≤n_A. 相应地，此特殊情形记为1|β；q_j^A=q|∑C_j^A：f_max^B≤Q. 对该问题，我们给出一个动态规划算法.

对于给定的门槛值Q，“条件f_max^B≤Q”等价于“代理B的每个工件J_j^B，1≤j≤n_B都有一个截止交货期(最迟完工时间)d_j^B”. 因而，本节研究的问题也可等价地表示为

引理3  问题1|β；q_j^A=q；d_j^B|∑C_j^A存在最优解，使得代理B的工件按截止交货期d_j^B由小到大的顺序加工，而代理A的工件按任意顺序加工.

证  任取问题的一个最优解σ. 假设在σ中存在代理B的两个工件J_i^B和J_j^B，d_i^B < d_j^B，但J_j^B排在J_i^B的前面. 可以将J_j^B移至紧挨在J_i^B之后，记新得到的排序为σ′. 比较排序σ和σ′可知，σ中排在J_j^B之前以及排在J_i^B之后的每个工件保持其完工时间不变；σ中排在J_j^B和J_i^B之间的工件(除了J_j^B)的完工时间减小或者保持不变；对于工件J_j^B，有

由上述分析可知，在新排序σ′中，代理B的所有工件仍然满足截止日期的要求，代理A的工件的完工时间之和没有增加. 因此，σ′也是问题的一个最优排序. 接着，如果σ′仍然不具有引理中描述的最优解的结构，则重复上面的移动操作. 经过有限次重复操作后，将会得到一个满足条件的最优解.

依据引理3，可以给出如下求解问题1|β；q_j^A=q|∑C_j^A：f_max^B≤Q的动态规划算法(DP算法)：

1) 利用公式d_j^B=max{T：当t≤T时，f_j^B(t)≤Q；当t>T时，f_j^B(t)>Q}，计算代理B的每个工件的截止交货期；

2) 将代理B的工件按照截止交货期由小到大的顺序重新标号(截止交货期相同的工件任意标号)，使得d₁^B≤d₂^B≤…≤d_nB^B；

3) 令TC(i，j)表示由代理A的前i(1≤i≤n_A)个工件J₁^A，J₂^A，…，J_i^A和代理B的前j(1≤j≤n_B)个工件J₁^B，J₂^B，…，J_j^B构成的子问题的最优排序中代理A的工件的完工时间之和. 初始值设置为TC(1，0)=p，TC(0，1)=0；

4) 递归关系：

5) 最优值为TC(n_A，n_B)，最优解可通过反向追踪找到.

定理2  DP算法是问题1|β；q_j^A=q|∑C_j^A：f_max^B≤Q的最优算法，其运行时间为O(n_An_B+n_Bmax{logn_B，logQ}).

证  由引理3，可通过求解一系列子问题的最优解并利用动态规划原理求解原问题. 对由代理A的前i(1≤i≤n_A)个工件J₁^A，J₂^A，…，J_i^A和代理B的前j(1≤j≤n_B)个工件J₁^B，J₂^B，…，J_j^B构成的子问题而言，在其最优排序中排在最后位置的工件只可能是J_i^A或J_j^B. 当最后位置安排J_i^A时，J_i^A的完工时间为

于是TC(i，j)=TC(i－1，j)+C_i^A；当最后位置安排J_j^B时，TC(i，j)=TC(i，j－1). 因而

根据动态规划原理，DP算法能最优求解问题1|β；q_j^A=q|∑C_j^A：f_max^B≤Q.

接下来，分析算法的运行时间. 在DP算法中，步骤1)对于给定的门槛值Q，计算代理B的每个工件的截止交货期，需要采用二元搜索方法花费O(logQ)时间完成，于是，计算代理B的所有工件的截止交货期共需花费O(n_BlogQ)时间；步骤2)对代理B的工件按截止交货期由小到大重新标号需要花费O(n_Blogn_B)时间；步骤3)-5)是动态规划的迭代执行过程，至多需进行n_An_B次迭代，每次迭代可以在常数时间完成，于是，总共花费O(n_An_B)时间. 综合上面的分析，DP算法的运行时间为

本文研究了工件可拆分的多代理分批调度问题，目标函数是在满足不超过一个代理的最大加工费用预算条件下，最小化另一个代理的工件的完工时间之和. 证明了此问题是NP难的，并对该问题的一个特殊情形给出了多项式时间算法. 未来，可进一步研究其他目标函数，如加权完工时间等问题.