广东科技学院，通识教育学院，广东 东莞

收稿日期：2020年10月25日；录用日期：2020年11月11日；发布日期：2020年11月18日

摘要

本文研究具有公共工期指派的凸资源单机排序问题。任务的实际加工时间是所获得的资源量的凸函数，目标函数是所有任务费用中的最大值。考虑两个问题。在第一个问题中，假设可用资源总数量有限，决策者需要寻找任务的最优排序、公共工期和资源分配方案，使得最大费用最小。第二个问题与第一个问题互补，资源总量没有限制，目标是在最大费用有上界限制条件下，求出最小资源总量、任务排序和公共工期及资源分配方案，使得资源总量最小。分别将上述问题转化为非线性凸规划问题加以处理。证明了两个问题均可以在多项式时间内求出最优解，提供了求解上述问题的多项式时间最优算法。分别给出实例说明算法的运算过程和有效性。

关键词

排序，单机，公共工期，最大费用，资源分配

Minmax Single Machine Scheduling Problem with Common Due-Date and Controllable Processing Time and Resource Restriction

Chengxin Luo

College of General Education, Guangdong University of Science and Technology, Dongguan Guangdong

Received: Oct. 25^th, 2020; accepted: Nov. 11^th, 2020; published: Nov. 18^th, 2020

ABSTRACT

This paper studies a common due-date assignment and scheduling problem. The objective function is the maximal cost among all jobs. The processing time of a job is a convex function of a resource allocated to it. Two problems are considered. In the first problem, the aim is to find imultaneously the job sequence and common due-date, as well as the resource allocation policy to optimilty that minimize the maximal cost among all jobs, subject to an upper bound on resourse amount. The second problem is complementary with the first one. The objective is to find imultaneously the optimal job sequence and due-date that minimize the resource amount of all jobs, subject to an upper bound on maximal cost among all jobs. The problems are converted to nolinear convex programmings. We present optimal algorithms that can be used to solve the above problems, respectively. Two examples are given to show how to realize the algorithms.

Keywords:Scheduling, Single Machine, Common Due-Date, Maximal Cost, Resource Allocation

Copyright © 2020 by author(s) and Hans Publishers Inc.

This work is licensed under the Creative Commons Attribution International License (CC BY 4.0).

http://creativecommons.org/licenses/by/4.0/

1. 引言

作为典型的离散优化问题之一，排序问题在工业生产加工和各种涉及企业管理机制范围内，处处可见其用武之处。准时(Just-in-Time)排序生产原则在过去的三十年里引起了众多研究者高度重视，产生了丰富的研究成果。在准时排序生产方针框架下，每个任务都有一个工期，工期经过协议由消费者决定，或者是决策变量。工期有三种形式：(1) 所有任务具有相同的工期(公共工期：common due-date)；(2) 每个任务具有不同的工期(不同工期：different due-date)；(3) 每个任务的工期是处理时间的线性函数(松弛工期：slack due-date)。文献 [1] [2] 分别最先提出上诉三种工期，并分别给出了多项式时间最优解。文献 [3] 进一步把公共工期推广到工期窗口(due-date window)，在窗口内完工的任务没有费用，而在窗口前或窗口后完工的任务分别有提前或延误费用。工期窗口(位置及大小)是决策变量，目标函数是由提前、延误和推迟窗口开始时间及窗口大小共同构成的费用之和。

在传统排序所研究的问题中，一般假定任务的处理时间是固定不变的，排在任何位置进行处理都取恒定常数。随着科技发展和技术的不断完善、企业实力的增强，管理者可以通过增加各类资源来缩短任务的处理时间。这种管理模式在文献中称为具有资源分配的可控处理时间问题。具有资源分配的排序问题在企业的生产加工中等实际环境中有广泛应用，最近二十多年来得到了学者们的大量研究，取得了丰富的研究成果。一般资源消费函数有两种：线性资源消费函数和凸资源消费函数。后者能够很好地反映边际效益递减这一广泛存在的经济规律，因而受到学者的重视。文献 [4] 比较全面地介绍了关于可控处理时间的研究论文。

在上面工期或工期窗口和各种机器及处理时间约定条件下，研究者取得了丰富的成果。文献 [5] 讨论工期指派排序问题，处理时间含学习效应和资源分配；文献 [6] 考虑单机工期窗口指派和资源分配问题，前提条件是具有公共流以及学习效应；文献 [7] 考虑带有公共交货期窗口和加工时间可控的单机排序问题；文献 [8] 在可控加工时间条件下研究具有退化效应的单机排序问题；文献 [9] 研究的单机窗口排序问题中，假设条件是与任务有关的截断学习效应以及凸资源共同决定处理时间；文献 [10] 在带有学习和退化效应假设下研究相同工期指派问题。得到了相应的最优算法。

在上面众多文献中，目标函数几乎都集中在与提前和延误等费用总和最小化方面。然而对于一种排序，所有任务费用中有一个最大费用，对最大费用最小化问题的研究有重要意理论意义。最大费用最小化对于评估生产系统的效率、对与生产管理过程中最坏情形度量和控制，以及平等对待所有代理商都有现实意义。

在文献中，将目标函数取作最大费用始于文献 [11]。文献 [12] 在松弛工期假设下讨论最大费用最小化问题，得到了简单最优算法。文献 [13] 在松弛工期假设下讨论两个竞争代理商最小化最大费用问题，给出了简单的多项式时间最优算法。 [14] [15] 分别考虑工期窗口指派最大费用最小化单机排序问题，得到了相应的多项式时间算法。

本文研究最大费用最小化的工期指派单机排序问题，其中任务处理时间是可控的。通过分配给任务一定的资源来缩短加工时间，使得生产系统获得最大效益。由于资源是有费用的，决策者同时还要考率控制使用资源的成本，这样一来会使得问题变得更加复杂化。与以往多数论文不同，我们同时考虑最大费用最小化，任务具有可控处理时间，任务的实际加工时间是所获得的资源量的凸函数，并且可利用的资源总量有上界限制。侧重考虑两个问题。第一个问题是在资源总量有上界的条件下，确定最优任务排序、最优公共工期以及资源分配方案，使得任务中最大费用最小化。第二个问题与第一个问题互补，其中资源总量没有限制，目的是在最大费用有上界限制条件下，求出最小资源总量、任务排序和公共工期及资源分配方案，使得资源总量最小。解决方法是将原问题转化为非线性凸规划问题进行处理，最后得到求解各自问题的最优算法。

2. 问题描述

假设管理者使用一台机器(处理机)用来处理n个不相关的任务(工件) $J=\left\{J_1,J_2,\cdots ,J_n\right\}$，所有任务在处理前均已到位等待处理。机器一次处理一个任务，并且要连续处理完，中间不允许中断。所有任务都有一个公共工期 $d_j=d\left(j=1,\cdots ,n\right)$，d是决策变量。任务如果在工期d之前或在之后完工，则分别有相应提前或延误费用；在时刻 $t=d$ 完工则没有费用。用 $p_j\left(u_j\right)$ 表示任务 $J_j$ 的实际加工时间，它是资源消耗量 $u_j$ 的凸函给数，由下式给出

$p_j\left(u_j\right)={\left(w_j/u_j\right)}^k,u_j>0,j=1,2,\cdots ,n$ (1)

其中 $w_j$ 为工件 $J_j$ 的负荷， $u_j$ 是分配给工件 $J_j$ 的资源数量， $k>0$ 是给定常数。定义 $\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$ 的完工时间， $E_j=\max \left\{0,d-C_j\right\}$，$T_j=\max \left\{0,C_j-d\right\}$ 分别表示工件 $J_j$ 的提前量和延迟量。以下用 $J_{\left(j\right)}$ 表示排在位置j的工件， $C_{\left(j\right)},E_{\left(j\right)},T_{\left(j\right)},u_{\left(j\right)}$ 分别表示 $J_{\left(j\right)}$ 的完工时间、提前量和延迟量及获得的资源数量。

在确定的工件排序后，每个任务或者提前，或者延误，或者准时完工(这时没有费用)，三者必居其一，其费用为 $E_j=\max \left\{\alpha E_j+\gamma d,\beta T_j+\gamma d\right\},j=1,2,\cdots ,n$。总费用定义为

$Z={\max }_{1\le j\le n}\left\{Z_j\right\}={\max }_{1\le j\le n}\max \left\{\alpha E_j+\gamma d,\beta T_j+\gamma d\right\}$

这里，提前、延误和推迟工期单位时间的费用分别记为 $\alpha ,\beta ,\gamma$，均为给定的正数。

研究的第一个问题中，假设资源总量有上界限制，即在满足 ${\displaystyle {\sum }_{j=1}^n{u}_j}\le U$ 的前提下，决定最优资源分配方案 $u=\left(u_1,u_2,\cdots ,u_n\right)$ 、任务的最优排序 $\pi$ 和最优工期d使得总费用 $Z=Z\left(\pi ,u\right)$ 最小，其中 $U>0$ 是可使用资源总量的上限。使用三参数表示法 [16] 可以表示如下

$\text{P}1:1|d_j=d,p_j\left(u_j\right)={\left(w_j/u_j\right)}^k,{\displaystyle {\sum }_{j=1}^n{u}_j}\le U|Z$ (2)

第二个问题与第一个问题互补，其中对资源总量U没有限制，目标是在最大费用有上界限制(即 $Z\le Q$ )条件下(其中 $Q>0$ 是给定的常数)，求出最小资源总量U、任务排序和公共工期及资源分配方案，使得资源总量U最小。用三参数表示法可表示如下

$\text{P}2:1|d_j=d,p_j\left(u_j\right)={\left(w_j/u_j\right)}^k,Z\le Q|{\displaystyle {\sum }_{j=1}^n{u}_j}$ (3)

3. 问题P1的最优解

本节中给出问题P1的最优解。为此首先给出下述重要结论。这对得到最优算法是必要的。

引理1 [11] 对于给定的任务排序 $\pi =\left(J_{\left(1\right)},\cdots ,J_{\left(n\right)}\right)$ 和资源分配方案 $u=\left(u_{\left(1\right)},\cdots ,u_{\left(n\right)}\right)$ 最优工期d和目标函数Z分别为

$d^{*}=d\left(\pi ,u\right)=\{\begin{array}{l}0,\gamma >\beta \\ C_{\left(1\right)}+\beta /\left(\alpha +\beta \right)\left[C_{\left(n\right)}-C_{\left(1\right)}\right],\gamma \le \beta \end{array}$ (4)

$Z^{*}=Z\left(\pi ,u\right)=\{\begin{array}{l}\beta C_{\left(n\right)},\gamma >\beta \\ \gamma C_{\left(1\right)}+\epsilon \left[C_{\left(n\right)}-C_{\left(1\right)}\right],\gamma \le \beta \end{array}$ (5)

其中 $\epsilon =\beta \left(\alpha +\gamma \right)/\left(\alpha +\beta \right)$。

根据引理1，利用(1)的表达式 $p_j\left(u_j\right)={\left(w_j/u_j\right)}^k,u_j>0,j=1,2,\cdots ,n$，问题P1转化为下述的非线性规划

$\text{NPL}1:\{\begin{array}{l}\min Z=\beta {\displaystyle {\sum }_{j=1}^n{\left(w_{\left(j\right)}/u_{\left(j\right)}\right)}^k}\\ \text{s}\text{.t}\text{.}{\displaystyle {\sum }_{j=1}^n{u}_{\left(j\right)}\le U},u_{\left(j\right)}>0,j=1,2,\cdots ,n\end{array}\left(\gamma >\beta \right)$ (6)

$\text{NPL}2:\{\begin{array}{l}\min Z=\gamma {\left(w_{\left(1\right)}/u_{\left(1\right)}\right)}^k+\epsilon {\displaystyle {\sum }_{j=2}^n{\left(w_{\left(j\right)}/u_{\left(j\right)}\right)}^k}\\ \text{s}\text{.t}\text{.}{\displaystyle {\sum }_{j=1}^n{u}_{\left(j\right)}\le U},u_{\left(j\right)}>0,j=1,2,\cdots ,n\end{array}\left(\gamma \le \beta \right)$ (7)

引理2 对于给定的任务排序 $\pi =\left(J_{\left(1\right)},\cdots ,J_{\left(n\right)}\right)$，NPL1和NPL2的最优解 $u^{*}=\left(u_{\left(1\right)}^{*},\cdots ,u_{\left(n\right)}^{*}\right)$ 和最优目标函数值 $Z^{*}$ 分别为

$u_{\left(j\right)}^{*}=\{\begin{array}{l}\left(U/V\right)w_{\left(j\right)}^{k/\left(k+1\right)},j=1,2,\cdots ,n,\beta <\gamma \\ \{\begin{array}{l}\left(U/L\right){\left(\gamma /\epsilon \right)}^{1/\left(k+1\right)}{w}_{\left(1\right)}^{k/\left(k+1\right)},j=1\\ \left(U/L\right)w_{\left(j\right)}^{k/\left(k+1\right)},j=2,\cdots ,n,\end{array}\beta \ge \gamma \end{array}$ (8)

$Z^{*}=Z\left(\pi ,u^{*}\right)=\{\begin{array}{l}\beta U^{-k}{V}^{k+1},\text{}\gamma >\beta \\ \epsilon U^{-k}{L}^{k+1},\gamma \le \beta \end{array}$ (9)

其中

$V={\displaystyle {\sum }_{j=1}^n{w}_{\left(j\right)}^{k/\left(k+1\right)}}={\displaystyle {\sum }_{j=1}^n{w}_j^{k/\left(k+1\right)}}$，$L={\left(\gamma /\epsilon \right)}^{1/\left(k+1\right)}{w}_{\left(1\right)}^{k/\left(k+1\right)}+{\displaystyle {\sum }_{j=2}^n{w}_{\left(j\right)}^{k/\left(k+1\right)}}$

证明 以 $\gamma \le \beta$ 为例加以证明， $\gamma >\beta$ 时证明方法类似。由于(7)式给出的目标函数是关于决策变量 $u_{\left(j\right)}$ 的凸函数，并且约束函数 $g\left(u\right)={\displaystyle {\sum }_{j=1}^n{u}_{\left(j\right)}-U}$ 也是关于 $u_{\left(j\right)}$ 的凸函数，利用凸规划理论，可知最优资源 $u^{*}$ 必使 $g\left(u\right)=0$，于是可使用Lagrange乘子法求解上述问题。假定任务排序 $\pi$ 给定，则Lagrange函数表达式为

$L_1\left(u,\lambda \right)=\gamma {\left(w_{\left(1\right)}/u_{\left(1\right)}\right)}^k+\epsilon {\displaystyle {\sum }_{j=2}^n{\left(w_{\left(j\right)}/u_{\left(j\right)}\right)}^k}+\lambda \left\{{\displaystyle {\sum }_{j=1}^n{u}_{\left(j\right)}-U}\right\}$ (10)

这里 $\lambda$ 表示Lagrange乘子。在(10)中，分别计算 $L_1\left(u,\lambda \right)$ 对所有决策变量的一阶偏导数，再令它们为零，便可得到最优资源 $u^{*}$ 所满足的必要条件如下

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

$\partial L_1\left(u,\lambda \right)/\partial u_{\left(1\right)}=-\gamma k\left(w_{\left(1\right)}^k/u_{\left(1\right)}^{k+1}\right)+\lambda =0$ (12)

$\partial L_1\left(u,\lambda \right)/\partial u_{\left(j\right)}=-\epsilon k\left(w_{\left(j\right)}^k/u_{\left(j\right)}^{k+1}\right)+\lambda =0,j=1,2,\cdots ,n$ (13)

注意到是凸规划问题，因此上述条件也是充分条件。由(12)，(13)得

$\gamma \left(w_{\left(1\right)}^k/u_{\left(1\right)}^{k+1}\right)=\epsilon \left(w_{\left(j\right)}^k/u_{\left(j\right)}^{k+1}\right),j=2,\cdots ,n$ (14)

由(14)得到

$u_{\left(j\right)}=u_{\left(1\right)}{\left(w_{\left(j\right)}/w_{\left(1\right)}\right)}^{k/\left(k+1\right)}{\left(\epsilon /\gamma \right)}^{1/\left(k+1\right)},j=2,\cdots ,n$ (15)

将(15)带入(11)，得

$u_{\left(1\right)}=\left(U/L\right){\left(\gamma /\epsilon \right)}^{1/\left(k+1\right)}{w}_{\left(1\right)}^{k/\left(k+1\right)}$ (16)

将(16)带入(15)可得(8)。其中

$V={\displaystyle {\sum }_{j=1}^n{w}_{\left(j\right)}^{k/\left(k+1\right)}}$，$L={\left(\gamma /\epsilon \right)}^{1/\left(k+1\right)}{w}_{\left(1\right)}^{k/\left(k+1\right)}+{\displaystyle {\sum }_{j=2}^n{w}_{\left(j\right)}^{k/\left(k+1\right)}}$

最后将(8)中后两式带入NPL2中目标函数Z得到(9)式。引理证毕。

引理3 [17] 给定两个正数列 $\left\{x_j\right\}$ 和 $\left\{y_j\right\}$，$j=1,2,\cdots ,n$。把 $\left\{x_j\right\}$ 按不减顺序排列，再把 $\left\{y_j\right\}$ 按不增顺序排列，可使得对应项乘积的和 ${\displaystyle {\sum }_{j=1}^n{x}_j{y}_j}$ 达到最小值。

根据上面分析和引理2、引理3，问题P1可由下述算法求解。

算法1 输入数据 $\alpha ,\beta ,\gamma ,k,U$

第一步 计算 $l=\arg {\max }_{1\le j\le n}\left\{w_j\right\}$，根据引理3，将任务 $J_l$ 排在首位，其余任务顺序任意，得到最优任务排序 ${\pi }^{*}=\left\{J_l,J_{\left(2\right)},\cdots ,J_{\left(n\right)}\right\}$

第二步 由(8)计算出最优资源分配 $u^{*}=\left(u_{\left(1\right)}^{*},u_{\left(2\right)}^{*},\cdots ,u_{\left(n\right)}^{*}\right)$

第三步 由(4)计算最优公共工期

$d^{*}=d\left(\pi ,u\right)=\{\begin{array}{l}0,\gamma >\beta \\ \gamma {\left(w_l/u_l\right)}^k+\left(\beta /\left(\alpha +\beta \right)\right){\displaystyle {\sum }_{j=2}^n{\left(w_{\left(j\right)}/u_{\left(j\right)}\right)}^k},\gamma \le \beta \end{array}$

第四步 由(9)计算出最优目标值 $Z^{*}$。

定理1 使用算法1可以在 $O\left(n\right)$ 时间内求出问题P1的最优解。

证明 上面一系列分析可以保证定理1结论的正确性。第一步时间复杂性为 $O\left(n\right)$，第二步的时间复杂性同为 $O\left(n\right)$，第三、四步需要 $O\left(1\right)$ 时间。于是求解问题P1的总的时间复杂性是 $O\left(n\right)$。定理证毕。

以下算例1说明算法1的运算过程。

算例1 给定问题参数 $k=1,\text{}U=121,\text{}n=5$，任务负荷 $\left\{w_1,w_2,w_3,w_4,w_5\right\}=\left\{1,1,4,9,16\right\}$。

第一步计算 $l=\arg {\max }_{1\le j\le n}\left\{w_j\right\}=5$，根据引理3得到最优任务排序 ${\pi }^{*}=\left\{J_5,J_1,J_2,J_3,J_4\right\}$。。

情形1 取 $\alpha =1,\beta =2,\gamma =3$。由于 $\beta <\gamma$，故利用(8)求出最优资源分配

$u^{*}=\left(u_{\left(1\right)}^{*},u_{\left(2\right)}^{*},u_{\left(3\right)}^{*},u_{\left(4\right)}^{*},u_{\left(5\right)}^{*}\right)=\left(u_5^{*},u_1^{*},u_2^{*},u_3^{*},u_4^{*}\right)=\left(44,11,11,22,33\right)$。由(9)求出最优目标函数值

$Z^{*}=\beta U^{-k}{V}^{k+1}=2$，其中 $V={\displaystyle {\sum }_{j=1}^5{w}_j^{k/\left(k+1\right)}}=11$。由(4)求出最优 $d^{*}=0$。

情形2 取 $\alpha =1,\beta =4,\gamma =2$。由于 $\beta \ge \gamma$，$\epsilon =\beta \left(\alpha +\gamma \right)/\left(\alpha +\beta \right)=2.4$，最优任务排序还是

${\pi }^{*}=\left\{J_5,J_1,J_2,J_3,J_4\right\}$ 不变， $L={\left(\gamma /\epsilon \right)}^{1/\left(k+1\right)}{w}_5^{k/\left(k+1\right)}+{\displaystyle {\sum }_{j=1}^4{w}_j^{k/\left(k+1\right)}}=7+\left(2/3\right)\sqrt{30}=10.65$。由(8)求出最优资

源分配 $u^{*}=\left(u_{\left(1\right)}^{*},u_{\left(2\right)}^{*},u_{\left(3\right)}^{*},u_{\left(4\right)}^{*},u_{\left(5\right)}^{*}\right)=\left(u_5^{*},u_1^{*},u_2^{*},u_3^{*},u_4^{*}\right)=\left(41.47,11.36,11.36,22.72,34.08\right)$。由(9)求出最优目标

函数值 $Z^{*}=\epsilon U^{-k}{L}^{k+1}=2.25$。由(4)求出最优 $d^{*}=\gamma {\left(w_5/u_5\right)}^k+\left(\beta /\left(\alpha +\beta \right)\right){\displaystyle {\sum }_{j=1}^4{\left(w_j/u_j\right)}^k}=1.3610$。

4. 问题P2的最优解

本节中给出问题P2的最优解，在最大费用有上界条件 $Z\le Q$ 下展开。首先，利用上一节的相应结果，问题P2可以转换为下述两个非线性规划。

$\text{NLP}3\left(\beta <\gamma \right):\{\begin{array}{l}\min U={\displaystyle {\sum }_{j=1}^n{u}_{\left(j\right)}}\\ \text{s}\text{.t}\text{.}\{\begin{array}{l}\beta {\displaystyle {\sum }_{j=1}^n{\left(w_{\left(j\right)}/u_{\left(j\right)}\right)}^k\le Q}\\ u_{\left(j\right)}>0,j=1,2,\cdots ,n\end{array}\end{array}$ (17)

$\text{NLP}4\left(\beta \ge \gamma \right):\{\begin{array}{l}\min U={\displaystyle {\sum }_{j=1}^n{u}_{\left(j\right)}}\\ \text{s}\text{.t}\text{.}\{\begin{array}{l}\gamma {\left(w_{\left(1\right)}/u_{\left(1\right)}\right)}^k+\epsilon {\displaystyle {\sum }_{j=2}^n{\left(w_{\left(j\right)}/u_{\left(j\right)}\right)}^k}\le Q\\ u_{\left(j\right)}>0,j=1,2,\cdots ,n\end{array}\end{array}$ (18)

引理4 对于给定的任务排序 $\pi =\left(J_{\left(1\right)},\cdots ,J_{\left(n\right)}\right)$，非线性规划NLP3，NLP4的最优解 $u^{*}=\left(u_{\left(1\right)}^{*},\cdots ,u_{\left(n\right)}^{*}\right)$ 和最优目标函数值 $U^{*}$ 分别为

$u_{\left(j\right)}^{*}=\{\begin{array}{l}{\left(V\beta /Q\right)}^{1/k}{w}_{\left(j\right)}^{k/\left(k+1\right)},j=1,2,\cdots ,n\left(\beta <\gamma \right)\\ \{\begin{array}{l}{\left(L\epsilon /Q\right)}^{1/k}{\left(\gamma /\epsilon \right)}^{1/\left(k+1\right)}{w}_{\left(1\right)}^{k/\left(k+1\right)},j=1\\ {\left(L\epsilon /Q\right)}^{1/k}{w}_{\left(j\right)}^{k/\left(k+1\right)},j=2,\cdots ,n\end{array}\left(\beta \ge \gamma \right)\end{array}$ (19)

$U^{*}=\{\begin{array}{l}{\left(\beta /Q\right)}^{1/k}{V}^{\left(k+1\right)/k},\beta <\gamma \\ {\left(\epsilon /Q\right)}^{1/k}{L}^{\left(1/k\right)+1},\beta \ge \gamma \end{array}$ (20)

证明 以 $\gamma \le \beta$ 为例加以证明， $\gamma >\beta$ 时证明方法类似。由于(18)式给出的目标函数 $U={\displaystyle {\sum }_{j=1}^n{u}_{\left(j\right)}}$ 是关

于 $u_{\left(j\right)}$ 的凸函数，并且约束函数 $f\left(u\right)=\gamma {\left(w_{\left(1\right)}/u_{\left(1\right)}\right)}^k+\epsilon {\displaystyle {\sum }_{j=1}^n{\left(w_{\left(j\right)}/u_{\left(j\right)}\right)}^k-Q}$ 也是关于 $u_{\left(j\right)}$ 的凸函数，利用

凸规划理论，可知最优资源 $u^{*}$ 必在边界 $f\left(u\right)=0$ 上取得，于是可使用Lagrange乘子法求解。假定任务排序 $\pi$ 已经给定，则Lagrange函数为

$L_2\left(u,\eta \right)={\displaystyle {\sum }_{j=1}^n{u}_{\left(j\right)}}+\eta \left[\gamma {\left(w_{\left(1\right)}/u_{\left(1\right)}\right)}^k+\epsilon {\displaystyle {\sum }_{j=2}^n{\left(w_{\left(j\right)}/u_{\left(j\right)}\right)}^k-Q}\right]$ (21)

这里 $\eta$ 表示Lagrange乘子。在(21)中，分别计算 $L_2\left(u,\eta \right)$ 对所有决策变量的一阶偏导数，再令它们等于零，便可得到最优资源 $u^{*}$ 所满足的必要条件如下

$\partial L_2\left(u,\lambda \right)/\partial \eta =\gamma {\left(w_{\left(1\right)}/u_{\left(1\right)}\right)}^k+\epsilon {\displaystyle {\sum }_{j=2}^n{\left(w_{\left(j\right)}/u_{\left(j\right)}\right)}^k-Q}=0$ (22)

$\partial L_2\left(u,\lambda \right)/\partial u_{\left(1\right)}=1-\eta \gamma k\left(w_{\left(1\right)}^k/u_{\left(1\right)}^{k+1}\right)=0$ (23)

$\partial L_2\left(u,\lambda \right)/\partial u_{\left(j\right)}=1-\eta \epsilon k\left(w_{\left(j\right)}^k/u_{\left(j\right)}^{k+1}\right)=0,j=2,\cdots ,n$ (24)

注意到是凸规划问题，因此上述条件也是充分条件。由(23)，(24)可得

$\gamma \left(w_{\left(1\right)}^k/u_{\left(1\right)}^{k+1}\right)=\epsilon \left(w_{\left(j\right)}^k/u_{\left(j\right)}^{k+1}\right),j=2,\cdots ,n$ (25)

由(25)得到

$u_{\left(j\right)}=u_{\left(1\right)}{\left(w_{\left(j\right)}/w_{\left(1\right)}\right)}^{k/\left(k+1\right)}{\left(\epsilon /\gamma \right)}^{1/\left(k+1\right)},j=2,\cdots ,n$ (26)

将(26)带入(22)，得

$u_{\left(1\right)}={\left(L\epsilon /Q\right)}^{1/k}{\left(\gamma /\epsilon \right)}^{1/\left(k+1\right)}{w}_{\left(1\right)}^{k/\left(k+1\right)}$ (27)

将(27)带入(26)可得(19)后两行。将(19)带入 $U={\displaystyle {\sum }_{j=1}^n{u}_{\left(j\right)}}$ 可得(20)。引理证毕。

根据引理3、引理4，我们有如下结论：如果 $\gamma >\beta$，由于 $V={\displaystyle {\sum }_{j=1}^n{w}_j^{k/\left(k+1\right)}}$ 是与任务排序无关的常数，因此任意排序都是最优的。如果 $\gamma \le \beta$，注意到 $k,Q,\epsilon$ 皆为常数，因此只需最小化 $L={\left(\gamma /\epsilon \right)}^{1/\left(k+1\right)}{w}_{\left(1\right)}^{k/\left(k+1\right)}+{\displaystyle {\sum }_{j=2}^n{w}_{\left(j\right)}^{k/\left(k+1\right)}}$。注意到 $\gamma /\epsilon \le 1$，根据引理3可知将最大的 $w_{\left(j\right)}$ 对应的任务排在首位，其余任务顺序任意，可得最优排序。根据上面分析可得问题P2如下算法。

算法2 输入数据 $\alpha ,\beta ,\gamma ,k,Q$

第一步 计算 $l=\arg {\max }_{1\le j\le n}\left\{w_j\right\}$，根据引理3，将任务 $J_l$ 排在首位，其余任务顺序任意，得到最优任务排序 ${\pi }^{*}=\left\{J_l,J_{\left(2\right)},\cdots ,J_{\left(n\right)}\right\}$

第二步 由(19)计算出最优资源分配 $u^{*}=\left(u_{\left(1\right)}^{*},u_{\left(2\right)}^{*},\cdots ,u_{\left(n\right)}^{*}\right)$

第三步 由(4)计算最优公共工期

$d^{*}=d\left(\pi ,u\right)=\{\begin{array}{l}0,\gamma >\beta \\ \gamma {\left(w_l/u_l\right)}^k+\left(\beta /\left(\alpha +\beta \right)\right){\displaystyle {\sum }_{j=2}^n{\left(w_{\left(j\right)}/u_{\left(j\right)}\right)}^k},\gamma \le \beta \end{array}$

第四步 由(20)计算出最优目标值 $U^{*}$。

定理2 使用算法2可以在 $O\left(n\right)$ 时间内得到问题P2的最优解。

证明 上述全面的分析保证定理2结论的正确性。其中第一、二步所需时间都是 $O\left(n\right)$，第三、四步的计算时间同为 $O\left(1\right)$。因此求解问题P2的总时间为 $O\left(n\right)$。定理证毕。

以下算例2说明算法2的运算过程。

算例2 给定问题参数 $k=1,\text{}Q=100,n=5$，任务负荷为 $\left\{w_1,w_2,w_3,w_4,w_5\right\}=\left\{1,1,4,9,16\right\}$。

计算 $l=\arg {\max }_{1\le j\le n}\left\{w_j\right\}=5$，根据引理3，得到最优任务排序 ${\pi }^{*}=\left\{J_5,J_1,J_2,J_3,J_4\right\}$。

情形1 取 $\alpha =1,\beta =2,\gamma =3$。由于 $\beta <\gamma$，故利用(19)求出最优资源分配

$u^{*}=\left(u_{\left(1\right)}^{*},u_{\left(2\right)}^{*},u_{\left(3\right)}^{*},u_{\left(4\right)}^{*},u_{\left(5\right)}^{*}\right)=\left(u_5^{*},u_1^{*},u_2^{*},u_3^{*},u_4^{*}\right)=\left(0.88,0.22,0.22,0.44,0.66\right)$。由(20)求出最优目标函数值

$U^{*}={\left(\beta /Q\right)}^{1/k}{V}^{\left(k+1\right)/k}=\left(2/100\right)\times {11}^2=2.42$，其中 $V=11$。由(4)求出最优 $d^{*}=0$。

情形2 取 $\alpha =1,\beta =4,\gamma =2$，由于 $\beta \ge \gamma$，$\epsilon =\beta \left(\alpha +\gamma \right)/\left(\alpha +\beta \right)=2.4$，最优任务排序 ${\pi }^{*}=\left\{J_5,J_1,J_2,J_3,J_4\right\}$ 不变， $L=10.65$。利用(19)求出最优资源分配

$u^{*}=\left(u_{\left(1\right)}^{*},u_{\left(2\right)}^{*},u_{\left(3\right)}^{*},u_{\left(4\right)}^{*},u_{\left(5\right)}^{*}\right)=\left(u_5^{*},u_1^{*},u_2^{*},u_3^{*},u_4^{*}\right)=\left(0.9329,0.2556,0.2556,0.5112,0.7668\right)$。由(20)求出最优目标

函数值 $U^{*}={\left(\epsilon /Q\right)}^{1/k}{L}^{\left(1/k\right)+1}=\left(2.4/100\right)\times {10.65}^2=2.7221$。由(4)求出最优

$d^{*}=\gamma {\left(w_5/u_5\right)}^k+\left(\beta /\left(\alpha +\beta \right)\right){\displaystyle {\sum }_{j=1}^4{\left(w_j/u_j\right)}^k}=56.2109$。

5. 结论

本文研究最大费用最小化的工期指派单机排序问题，其中任务处理时间是可控的。目标是分别在资源总量有限和总费用受限的条件下确定，确定最优任务排序、最优公共工期以及资源分配方案，使得任务中最大费用最小化。解决本问题方法分为两步：首先把研究的问题转化为非线性凸规划问题，运用凸优化理论进行处理；其次利用匹配算法求得最优任务排序，进一步得到最优工期、最优资源分配方案等。作为总结提供了最优算法。用两个实例分别说明算法的运算过程和有效性。

未来研究可以考虑将本文问题推广到工期窗口情形，或者任务处理时间是与位置有关的凸函数情形。新问题将会更复杂，从而具有挑战性和实际应用意义。

基金项目

国家自然科学基金项目(11171050)资助。

文章引用

罗成新. 公共工期指派和可控处理时间资源约束下最大费用最小化单机排序问题
Minmax Single Machine Scheduling Problem with Common Due-Date and Controllable Processing Time and Resource Restriction[J]. 应用数学进展, 2020, 09(11): 1945-1953. https://doi.org/10.12677/AAM.2020.911224

参考文献