1. 引言

排序问题是一类重要的组合最优化问题，在运筹学、计算机科学、管理科学与工业生产等领域中有广泛的应用。在经典排序模型中，工件(任务)的加工时间是固定的，是与加工位置和资源分配无关的常数。不过在实际生产过程中，工件的加工时间可能会在分配给工件一定的资源(如人力，电力，催化剂等)后相应缩短，或者由于操作人员经过多次重复加工而提高了技术后，工作效率提高，加工时间缩短。这一现象称为学习效应。相反的，由于机器在加工大量任务后速度变低，一个任务排在后边加工时间变长。这是所谓的退货效应。总之，这时任务加工时间除了与任务本身有关，还与所处位置有关。这类排序问题在工业生产加工等实际环境中有广泛应用，近年来受到了广泛研究。文 [1] 研究具有学习效应和资源分配的工期指派单机排序问题；文 [2] [3] 分别在公共流和公共窗口假设下研究具有学习效应和资源分配的单机工期窗口指派排序问题；文 [4] 在可控加工时间条件下研究具有退化效应的单机排序问题。分别给出了多项式时间的最优算法。

具有资源分配的排序问题近年来得到了高度的重视。一般资源消费函数有两种：线性资源消费函数和凸资源消费函数。后者能够很好地反映边际效益递减这一广泛存在的经济现象，因而受到学者的重视，有关的研究论文十分丰富。其中文 [5] 比较全面地介绍了关于可控处理时间的研究论文，包括近期的绝大多数研究成果。

本文研究具有与任务和位置有关的可控处理时间的凸资源单机排序问题。假定任务的实际加工时间是所获得的资源量、与任务位置有关的负荷的函数。主要考虑两个问题。第一个问题是在资源总量有上界的条件下，确定任务排序、资源分配方案，使得时间表长最小。第二个问题中资源总量没有限制，目标是求出最小资源总量、任务排序和资源分配方案，使得由时间表长和资源总量加权和取最小值。证明了上述问题都可以在多项式时间内求出最优解，并分别给出了求解相应问题的多项式时间最优算法。

2. 问题描述

设有n个独立的任务(工件) $J=\left\{J_1,J_2,\cdots ,J_n\right\}$ 需要在一台机器上加工，所有任务在零时刻都已到达。机器在同一时刻最多只能加工一个工件，工件加工不允许中断。用 $p_{jr}\left(u_j\right)$ 表示任务 $J_j$ 排在位置r时的实际加工时间，它是资源消耗量 $u_j$ 的凸函数

$p_{jr}\left(u_j\right)={\left(w_{jr}/u_j\right)}^k,u_j>0,j,r=1,2,\cdots ,n$

其中 $w_{jr}$ 为工件 $J_j$ 的负荷， $u_j$ 是分配给工件 $J_j$ 的资源量，k是正常数。定义 $\pi =\left(J_1,J_2,\cdots ,J_n\right)$ 为在一个资源分配 $u=\left(u_1,u_2,\cdots ,u_n\right)$ 下所确定的工件排序， $C_j=C_j\left(\pi \right)$ 表示 $J_j$ 的完工时间， $C_{\max }=\max \left\{C_j|j=1,\cdots ,n\right\}$ 表示时间表长。

本文研究的第一个问题是在资源总量有上界限制，即 ${\displaystyle {\sum }_{j=1}^n{u}_j}\le U$ 的前提下，决定最优资源分配方案 $u=\left(u_1,u_2,\cdots ,u_n\right)$ 及最优排序 $\pi$ ，使得时间表长

$Z_1=Z_1\left(\pi ,u\right)=C_{\max }\left(\pi ,u\right)$

最小，其中 $U>0$ 是可使用资源总量的上限。用三参数表示法 [6] 表示如下

$1|p_{jr}\left(u_j\right)={\left(w_{jr}/u_j\right)}^k,{\displaystyle {\sum }_{j=1}^n{u}_j}\le U|Z_1$ (1)

在研究的第二个问题中资源总量U没有限制，目标是求出最小资源总量U、任务排序和资源分配方案，使得由时间表长和资源总量确定的目标函数

$Z_2=Z_2\left(\pi ,u\right)=\alpha C_{\max }\left(\pi ,u\right)+\beta U$

取最小，其中 $\alpha ,\beta$ 是已知正常数。用三参数表示法表示如下

$1|p_{jr}\left(u_j\right)={\left(\frac{w_{jr}}{u_j}\right)}^k|Z_2$ (2)

3. 问题(1)的最优解

下述几个重要结论给出了最优解所具有的性质，它们对于得到最优算法是必不可少的。首先，由于 $C_{\max }\left(\pi ,u\right)$ 是完工时间 $C_j$ 的非减函数，从而引理1的结论是显然的。

引理1 存在最优排序，其中首个任务开始加工时间为0，且两个相邻任务之间无空余时间。

引入 $0-1$ 变量 $\left\{x_{jr}:j,r=1,2,\cdots ,n\right\}$ ， $x_{jr}=1$ ，如果工件 $J_j$ 排在位置r上； $x_{jr}=0$ ，如果工件 $J_j$ 没有排在位置r上。给定 $\left\{x_{jr}:j,r=1,2,\cdots ,n\right\}$ 后，任务的排序 $\pi$ 就随之确定了。于是有

$Z_1\left(\pi ,u\right)=C_{\max }\left(\pi ,u\right)={\displaystyle {\sum }_{r=1}^n{\displaystyle {\sum }_{j=1}^n{p}_{jr}\left(u_j\right)x_{jr}}}={\displaystyle {\sum }_{r=1}^n{\displaystyle {\sum }_{j=1}^n{\left(w_{jr}/u_j\right)}^k}}{x}_{jr}$ (3)

引理2 对于固定的 $\left\{x_{jr}:j,r=1,2,\cdots ,n\right\}$ ，最优资源分配方案 $u^{*}=\left(u_1^{*},u_2^{*},\cdots ,u_n^{*}\right)$ 由下式给出

$u_j^{\ast }=\frac{{\left({\displaystyle {\sum }_{r=1}^n{w}_{jr}^k{x}_{jr}}\right)}^{1/\left(k+1\right)}}{{\displaystyle {\sum }_{j=1}^n{\left({\displaystyle {\sum }_{r=1}^n{w}_{jr}^k{x}_{jr}}\right)}^{1/\left(k+1\right)}}}U,j=1,2,\cdots ,n$ (4)

证明 由于(3)式给出的目标函数是关于 $u_j$ 的凸函数，并且约束函数 $g\left(u\right)={\displaystyle {\sum }_{j=1}^n{u}_j-U}$ 也是关于 $u_j$ 的凸函数，利用凸规划理论，可知最优资源 $u$ 必使 ${\displaystyle {\sum }_{j=1}^n{u}_j}=U$ ，从而可使用拉格朗日乘子法求解。对于任意给定排序 $\pi$ ，拉格朗日函数为

$L\left(u,\lambda \right)={\displaystyle {\sum }_{r=1}^n{\displaystyle {\sum }_{j=1}^n{\left(w_{jr}/u_j\right)}^k{x}_{jr}}}+\lambda \left\{{\displaystyle {\sum }_{j=1}^n{u}_j-U}\right\}$ (5)

其中 $\lambda$ 为拉格朗日乘子。对(5)式中的所有变量分别求偏导，并令其为零，得到最优资源 $u$ 满足的充分必要条件

$\partial L\left(u,\lambda \right)/\partial \lambda ={\displaystyle {\sum }_{j=1}^n{u}_j}-U=0$ (6)

$\partial L\left(u,\lambda \right)/\partial u_j=\partial C_{\max }\left(u,\lambda \right)/\partial u_j+\lambda =0,j=1,2,\cdots ,n$ (7)

由(7)可得

$\partial C_{\max }\left(u,\lambda \right)/\partial u_j=\partial C_{\max }\left(u,\lambda \right)/\partial u_1,j=2,3,\cdots ,n$

由此得到

$u_j=u_1\frac{{\left({\displaystyle {\sum }_{r=1}^n{w}_{jr}^k{x}_{jr}}\right)}^{1/\left(k+1\right)}}{{\left({\displaystyle {\sum }_{r=1}^n{w}_{1r}^k{x}_{1r}}\right)}^{1/\left(k+1\right)}},j=2,\cdots ,n$ (8)

将(8)带入(6)，得

$u_1=\frac{{\left({\displaystyle {\sum }_{r=1}^n{w}_{1r}^k{x}_{1r}}\right)}^{1/\left(k+1\right)}}{{\displaystyle {\sum }_{j=1}^n{\left({\displaystyle {\sum }_{r=1}^n{w}_{jr}^k{x}_{jr}}\right)}^{1/\left(k+1\right)}}}U,j=2,\cdots ,n$ (9)

将(9)带入(8)可得(4)。定理证毕。

现在将(4)带入(3)中 $Z_1$ 的表达式，得

$Z_1=U^{-k}{\left({\displaystyle {\sum }_{j=1}^n{\left({\displaystyle {\sum }_{r=1}^n{w}_{jr}^k{x}_{jr}}\right)}^{1/\left(k+1\right)}}\right)}^{k+1}$ (10)

注意到 $U>0,k>0$ 都是已知常数，于是上述问题等价于最小化下述函数

$f={\displaystyle {\sum }_{j=1}^n{\left({\displaystyle {\sum }_{r=1}^n{w}_{jr}^k{x}_{jr}}\right)}^{1/\left(k+1\right)}}={\displaystyle {\sum }_{j=1}^n\left({\displaystyle {\sum }_{r=1}^n{w}_{jr}^{k/\left(k+1\right)}{x}_{jr}}\right)}$

其中最后一个等号是利用 $\left\{x_{jr}:j,r=1,2,\cdots ,n\right\}$ 的性质得到的。于是问题(1)可以转化为下述的指派问题：

$\{\begin{array}{l}\text{Min}{\displaystyle {\sum }_{j=1}^n{\displaystyle {\sum }_{r=1}^n{w}_{jr}^{k/\left(k+1\right)}{x}_{jr}}}(11)\\ \text{s}\text{.t}\text{.}\{\begin{array}{l}{\displaystyle {\sum }_{r=1}^n{x}_{jr}}=1,j=1,\cdots ,n\\ {\displaystyle {\sum }_{j=1}^n{x}_{jr}}=1,r=1,2,\cdots ,n;(12)\\ x_{jr}\in \left\{1,0\right\},j,r=1,2,\cdots ,n\end{array}\end{array}$

因此，对于问题(1)，可以给出如下最优算法。

算法1

第1步 解指派问题(11)~(12)求出最优排序 ${\pi }^{*}$ ；

第2步 根据(4)，求出排序 ${\pi }^{*}$ 下的最优资源分配 $u^{*}=\left(u_1^{*},u_2^{*},\cdots ,u_n^{*}\right)$ ；

第3步 由(10)式，确定最优目标函数值 $Z_1=U^{-k}{\left({\displaystyle {\sum }_{j=1}^n{\left({\displaystyle {\sum }_{r=1}^n{w}_{jr}^k{x}_{jr}}\right)}^{1/\left(k+1\right)}}\right)}^{k+1}$ 。

定理1 对于问题(1)，利用算法1可以通过求解指派问题在 $O\left(n^3\right)$ 时间内求得最优解。

证明 上面的分析保证了定理1结论的正确性。第一步可在 $O\left(n^3\right)$ 时间内完成，第二步可在 $O\left(n\right)$ 时间内完成，第三步需要 $O\left(1\right)$ 时间，因此算法总的时间复杂性为 $O\left(n^3\right)$ 。定理证毕。

4. 问题(2)的最优解

本节中目标是在资源总量不受限制的前提下，确定最优资源总量U及其分配方案 $u=\left(u_1,u_2,\cdots ,u_n\right)$ 、最优排序 $\pi$ ，使得时间表长和总资源消耗量组成的目标函数 $Z_2\left(\pi ,u\right)$ 取最小值。

类似于上一节的推导，我们有

$Z_2\left(\pi ,u\right)=\alpha C_{\max }\left(\pi ,u\right)+\beta U=\alpha U^{-k}{B}^{k+1}+\beta U$ (13)

其中 $B={\displaystyle {\sum }_{j=1}^n\left({\displaystyle {\sum }_{r=1}^n{w}_{jr}^{k/\left(k+1\right)}{x}_{jr}}\right)}$ 与U无关。因此有

引理3 对于固定的 $\left\{x_{jr}:j,r=1,2,\cdots ,n\right\}$ ，最优资源总量U由下式给出

$U^{*}=B{\left(k\alpha /\beta \right)}^{1/\left(k+1\right)}$ (14)

证明 由于对 $U>0$ 无约束，故U满足

$\partial Z_2\left(\pi ,u\right)/\partial U=\beta -k\alpha B^{k+1}/U^{k+1}=0,{\partial }^2{Z}_2\left(\pi ,u\right)/\partial U^2=\alpha k\left(k+1\right)B^{\left(k+1\right)}{U}^{-\left(k+2\right)}>0$

由此可得(14)。引理证毕。

将(14)带入(13)中目标的函数 $Z_2$ ，可得

$Z_2^{\ast }=\left[{\left(\beta {\alpha }^{1/k}/k\right)}^{k/\left(k+1\right)}+{\left(k\alpha {\beta }^k\right)}^{1/\left(k+1\right)}\right]B=LB$

其中 $L={\left(\beta {\alpha }^{1/k}/k\right)}^{k/\left(k+1\right)}+{\left(k\alpha {\beta }^k\right)}^{1/\left(k+1\right)}>0$ 。注意到L是已知常数，因此，对于问题(2)，可以给出如下最优算法。

算法2

第1步 解指派问题(11)~(12)求出最优排序 ${\pi }^{*}$ ；

第2步 根据(14)，求出排序 ${\pi }^{*}$ 下的最优资源总量 $U^{*}$ ；

第3步 根据(4)，求出排序 ${\pi }^{*}$ 下的最优资源分配 $u^{*}=\left(u_1^{*},u_2^{*},\cdots ,u_n^{*}\right)$ 。

定理2 利用算法2可以通过求解指派问题在 $O\left(n^3\right)$ 时间内求得问题(2)的最优解。

证明 上面的分析保证了定理2结论的正确性。因为求解指派问题(11)~(12)需要 $O\left(n^3\right)$ 时间，第2步可在 $O\left(1\right)$ 时间内完成，第3步需要 $O\left(n\right)$ 时间，于是求解问题(2)的时间复杂度为 $O\left(n^3\right)$ 。定理证毕。

基金项目

国家自然科学基金(11171050)。

参考文献