通过非线性规划调度有时间资源权衡的并行工作英文文献翻译数学.doc

通过非线性规划调度有时间-资源权衡的并行工作
Alexander Grigoriev, Marc Uetz
马斯特里赫特大学、数量经济学,P.O.Box 616， 6200 MD Maastricht,荷兰
{ },
我们考虑到一个调度问题的任何工作的加工时间是依赖于使用离散的可再生资源,例如:人员。一定数量的k单位资源分派到在任何时候的工作,分派给一份工作的资源越多,解决时间越小。这样做的目的是找到一种资源配置和时间表,最大限度地减少了最大竣工时间。我们的确需要简洁地未编码的时间-资源权衡函数,它需要的是未被使用过数学规划技术。运用一种(非线性)整数数学程式,我们用性能约束(3 + ɛ), ɛ > 0为调度问题取得第一个多项式时间的近似算法。我们的方法依赖于一个完全多项式时间近似方案来解决数学规划松弛。这一结果自身是令人感爱好的,由于我们同时也表白,潜在的数学规划是一个np难问题来解决。我们也获得的近似下界。
关键词:调度;数学规划;近似算法,计算复杂度
概述:
1、简介和相关工作
考虑一个调度问题n个工作j∈V需要在m个并行机器上解决。每个工作致力于得到解决一个确切的机器。有一个可再生资源,如离散人员,可以分派到工作以减少他们的加工规定。我们假设之间的利弊权衡使用的资源和由此产生的加工规定的工作j都可以描述为一些非负时间-资源权衡功能(·)意味着,当x资源分派工作j,其加工规定成为(x)。在任何时间点,只有k单位资源是可用的。
我们可以推断时间-资源权衡 (·):{ 0,1,…,k} !一方面得到是产生积极的作用。一旦资源已经被分派到工作, 假如它不消耗更多的比目前k单位的资源在任何时间,时间表被称为可行的。目的是找到一个资源配置和相应的可行的时间表,最大限度地减少了最大竣工时间,也就是说,这工作的完毕时间,完毕交货。这个问题描述典型情况,在那里额外生产的物流资源,如人员,可以被运用,以减少生产周期时间。
作为一个事实,一个不可再生资源调度问题,如全面预算约束, 在文学界作为time-cost权衡问题受到了很多人的注意,例如,[2、12、13、22条、23条]。令人惊讶的是,在相应的问题,一种可再生资源,如人员的约束, 虽然从一个实际的观点他们不是缺少吸引力,但受到的关注少。我们将把它们认为是时间-资源权衡问题,在类推到前者。
相关工作
文献[8]中,我们考虑过的更普遍的问题是不相干的机器排序问题和受资源约束的解决时间。在那里,工作都可以在任何机器加工,并且假如一个工作是原定于机器i,用s的机器的k可用资源的单位,解决时间是。假设解决时间在资源的非增长性, 文献[8]证明了3.75-近似算法的存在性。该方法提出了基于线性规划松弛,使用nk变量。在本文中,然而,我们明确地允许时间-资源权衡功能(·)可以被更简洁的编码。比如,假如这些函数是线性的,这个问题本质上是由输入的O(n)数字组成: 每个工作,我们必须指定其机器i和两个整数系数和,这样就时间-资源权衡功能等式 (x)=−x。因此, 在文献[8]中的算法提出了一般不是多项式时间算法。
在Grigoriev et al.的一份受限制的版本的手边问题的演讲手稿[7]。他们假设额外资源是二进制的,那就是,任何工作都可以要么有或没有使用解决资源,减少了加工时间若资源被使用。最后, 在论文中机器的数量m被认为是固定的,不是部分输入的。在那个问题上,他们衍生出一个近似(3 + ɛ),并对这个问题和m = 2个机器,他们获得NP-hardness和一个完全多项式时间近似方案[7]。受资源约束的解决时间的调度工作也被称为可锻铸或可平行任务调度;例[11、18、19日,24]。在这些模型中,独立,对其采用非中断的工作可以被解决在一个或多个平行解决器,并且他们在解决器使用数量上用了更少的进程时间。任何解决器只能解决一个工作,目的是最小化最大竣工时间的时间表。Turek et al [24]介绍了这个问题,他们获得2 -近似算法。事实上, [24]中的模型与本文有联系但不同于本文。假如[24]中并行解决器作为一个通用的必须分派工作的“资源”, 当被限制用线性时间-资源权衡函数,[24]中的问题是这篇文章的问题的一个特例: 所相应的是这样的情形,n个工作被m = n个机器,而不是m < n个机器解决。Mounie et al.[18]考虑[24]中问题的另一个限制,该解决器分派必须连续，工作函数在s中是非递减的。,因此在[18]中导出了 ( +ɛ )–近似。未发表期刊论文的版本(19),提出了一种改善的性能界主张(3/2 +ɛ”)。Jansen给出了渐近完全多项式近似方案 [11]。
在Blazewicz et al. [1]中，当我们进一步限制,假设决定资源配置是固定的事先做自己的工作,我们回到了在资源约束条件下的(机器)调度。最近Kellerer and Strusevich讨论了假设工作视线被分派在机器上 [第14条、第15条]。他们使用术语专用机器排序问题。我们参考这些复杂的文献结果, 同时也注意到了NP-hardness机排序和一种二进制资源在[14]中被介绍。更准确的说,对固定数量的机器是弱的NP-hardness,对任意数量的机器强烈的NP-hardness。
结果和方法。我们得到一个多项式时间(3 +ɛ)-近似最大竣工时间最小化的算法具有任意时间-资源并行工作的权衡取舍。更具体地说,我们的结果合用于任意m个机器、任意k个单位可运用资源, 多项式时间可计算任意时间-资源权衡函数(x),j ∈ V, x是分派到工作j的多个资源。作为特殊例子,我们的方法涉及线性时间-资源权衡函数,其中 (x)=−x,是线性时间-资源权衡函数的斜率,是错误解决时间。注意到我们的结果在多方面推广了以前的(3+ɛ)-近似 [7]: 他们认为特殊情况下k = 1,可以理解为线性时间-资源权衡函数,他们认为一个常数m个机器。虽然我们获得相同的性能约束,我们强调我们的结果依赖于一种完全不同的方法。也注意到我们用简洁地未编码时间-资源权衡函数得到第一个多项式时间近似算法,如同以前的方法,如[8]通常不亚于多项式时间算法。
除了在调度方面提高以前的结果,我们想强调的是文章的重要奉献是方法方面。事实上,我们通过使用一个数学规划模型得到我们想要的结果,构成一个松弛问题。无论是在目的和约束的条件下，这种数学程序包含任意多项式时间可计算功能。当限于线性时间-资源权衡函数,例如,这种数学程序是线性约束的凹规划问题。我们的分析表白, 甚至对特殊情况的线性时间-资源权衡函数，这个数学问题的求解也是一个难题。然而,总的来说它可以用自己的方法解决任意精度多项式时间。
此外, 通过对资源配置的数学计算程序的确可以提供的“错”的回答，我们提供了参数化的例子来说明即使用线性时间-资源权衡函数我们的分析也不能比1.46因素更好,。同样的例子表白, 基于资源的配置提出的数学程序的调度算法离最优化差2个因素。
2、问题定义
用V = { 1,…,n }表达一系列工作。工作必须在m个并行机器中非抢险的解决,这样做的目的是找到一个最小化最大竣工时间表,Cmax,也就是说,上次的工作完毕的时间。每个工作j被指派给一个确切的机器，Vi指示该套指派给机器i的任务,这样V = 形成一个分区上的工作。在其加工过程中一份工作j也许会分派给一组离散的资源x∈{ 0,1,…,k},例如人员,这可以加快其加工。分派给一个工作的资源必须不断加工并限制在最多k个。假如x资源分派给工作j, 那份工作的解决时间是,x = 0,…,k。全球资源约束的事实是, 时间表在一种可行的解决方案,在任何时候所消耗的资源都不超过k单位。很明显, 既然问题是微局限性道的我们可以假设k≥1。
工作的实际加工时间是通过时间计算资源交易函数(·):{ 0、1,…,k}→。我们假设(没有损失的一般性)所有时间-资源权衡函数(·) 在他们的领地是非增的,这意味着更多的资源分派到一个工作,缩短了加工时间,:= (0)是默认的解决时间,j∈V。我们此外假设这些函数在多项式时间内是可计算的,也就是说,有一种算法,对于任意给定的值x∈ { 0,1,…,k},返回时间多项式的值(x)到函数 (·)和的编码长度。根据定义,我们对所有j ∈2和x∈{ 0,1,…,k}有 = (x)。我们做出了 和 (x)之间看似人工的区别只是凸显不同的编码长度: 所有工作的所有也许的加工时间都由x给出j∈V，x = 0,…,k。这些值的编码长度明显是Ω(nk)。但是所有的时间资源权衡函数(.),j∈V,可以被编码的更简洁明了。让p = ,A是任何时间-资源权衡函数的最大长度编码，这个问题的编码长度是O(n +nA+).例如,假如我们假设线性时间-资源权衡函数在(x)=−x的编码长度是O(n +n+),a= 。
3、计算复杂度
作为专用机器调度问题的一个推广, Strusevich和Kellerer[14]认为,手边问题是强np。我们下次得出了更强的结果,即一个不近似结果。
定理1：除非P = NP,用一份履约保函小于用时间-资源权衡调度并行工作1.5没有近似算法。
证明：为了适应 [8]中的证明观点,我们用一个从NP-complete问题区分的变形: 我们给k整数a1,…,ak,= 2B,我们决定是否存在一个子集S⊆{1,…..,k} =B.我们为每项定义一项工作j,为了使其在个人机(所以m = n)上及时得到解决，时间-资源权衡函数如下：
(x)=
此外,让可用性的资源为k = b .显然,任何时间-资源函数的编码长度是O(),于是这种转变是多项式的。现在很容易看到,存在一个隔断,当且仅当调度问题的最优解具有最大竣工时间2: 每个工作j分派给资源的个单元,因而具有解决时间1,工作被分割成两个集合, 分区的每个总资源规定为B。
因此极小化最大竣工时间为2。相反地,假如没有分区存在,任何计划必须至少有最大竣工时间3。规定的非相似界也紧随其后。
4、数学规划松弛
[8]中的方法可以获得手边问题的3.75-相似算法。然而,这个方法是基于一个明确的整数线性规划模型,规定(nk)二进制变量代表工作的所有不同的加工时间。很明显,当时间-资源权衡函数编码简朴,一般不会导出一个多项式时间算法。
为了在函数的编码长度上独立的解决这一问题,我们可以建立起一个多项式数学规划的制定、大小,使用O(n)整数变量{ 0,…,k }其指示的是分派各工作j的资源数量,jV。假如有一个最大竣工时间C的可行的时间表，下面的整数数学规划会有一个解决办法 。
()C i=1,…,m, (1)
()C, (2)
0k, , (3)
, . (4)
这背后的逻辑程序是以下;(1)条规定:“每台机器的总解决是最大竣工时间的一个低约束;(2)条规定:“日程安排的资源消耗总量不得超过最大值kC。我们的目的是为项目(1)-(4)计算一个整数可行解(,),这样,是最优时间表的最大竣工时间的一个低约束。的一个候选是最小整数值,是说是可行的。但由于我们不知道如何准确计算,我们将计算近似。
为了为项目(1)-(4)决定可行性计划,我们不妨解决以下最小化问题。
min. () , (5)
s.t. ()C i=1,…,m, (6)
0k, , (7)
, . (8)
很明显,(1)-(4)是可行的,当且仅当客观值最多是kC时问题(5)-(8)有一个解决办法。
在我们描述解决问题(5)-(8)这个算法前,让我们简要的叙述这个问题的复杂度。例如,假如时间-资源权衡函数是线性的，问题(5)-(8)是一个约束二次优化问题。众所周知,约束二次规划是一个np难问题[20],即使没有完整性约束。更具体地说,对线性时间-资源权衡函数我们有一个约束凹问题,通常被叫做的np-hard[10]。我们下面将说明问题(5)-(8)是一个np-hard。
定理2、 整数数学规划问题(5)-(8),以及它的线性松弛(5)-(7)对于解决最优化是np-hard,即使所有时间-资源权衡函数(.),jV,是线性的。
证明：我们又一次使用从NP-complete问题隔断的减少.我们给非负整数a1,…,,= 2B,我们被规定去决定是否存在一个子集, S⊆{1,…..,} =B。定义m = 3台机器。对于任何j = 1，…,我们介绍了三个相同的工作,其中的每一个都是被安排在其中的一个,每一种都用一个线性时间-资源权衡函数(x)= 2−x,x{ 0,1 }。因此总的来说n:= 3个工作或者在加工时间2以默认模式或者在加工时间以快速模式被解决。只有一个单位的资源是可行的,因此k = 1。使用默认加工时间的极小化最大竣工时间对每台机器是4B。我们规定最大竣工时间最多为3B。对于这一问题,线性松弛(5)-(7)变成
min. ,
s.t. , i=1,2,3,
01 ,
现在,并不难看到有分区,当且仅当最优解决方案,使这个凹二次计划等于3B: 假如存在由S⊆{1,…..,}产生的分区，假如j,让=1否则=0.i=1,2,3.相反,假设一个解决方案具有值3B。我们说任何最优解一定是在。一方面注 i = 1、2、3,否则至少一个变量可以减少,因此,减少也是客观值。现在假设有一分形变量0 << 1,然后由以前的观测必须有另一个分形变量0 << 1,并且为了客观值能彼此互换。另一方面,为了实现约束设立,必须有所有i = 1、2、3。现在假如对于某些i ,会产生=的完整性。这样对所有i=1,2,3,为所有i = 1、2、3、因此存在分区。
我们接下来表白(整数)数学程式(5)-(8)可以在多项式时间内以任意精度解决。
引理1：对任何0 << 1,我们可以在及时多项式输入的大小和1/找到离最优解不超过因子(1+) 的数学规划(5)-(8)的解决办法 。
换句话说,(5)-(8)认可FPTAS,一个全多项式时间近似方案。这个引理证明是行得通的。我们一方面展示如何减少规划到一个特定的单机排序问题,然后证明该调度问题采用FPTAS，它运用Pruhs 和Woeginger的理论 [21]。
证明：[引理1]一方面假设(5)-(8)可以分解为m个独立的被约束的规划,每台机器i分派一个：
Min . () , (9)
s.t.() (10)
0k, , (11)
, . (12)
我们现在考虑更严格的限制问题(1 +) 圆形的权力, 我们限制了资源消耗量,j 而不是约束(11)-(12)。更精确的来讲，设
,
。我们认为只要在项目(9)-(12)中值X存在答案x，受限项目中存在值,其中。看到这一解决方案,我们考虑客观评价值X的一个答案x。我们简朴的把j的值集合起来为最接近的整数定义一个新的解决方案。这样所有的资源消耗集合起来,我们，所有j,从而满足约束(10)。因此,所得到的解是规划(9)-(12)的一个整数可行解。对所有j
现在,考虑任意的j 相应的这样。由于是一个整数,我们有
.
假如

我们直接得到

假如

得到

这样

因此
，j
因此,从上面的观测和时间-资源权衡函数的单调性,我们有
()
我们接下来说明问题(9)-(12)j是一个FPTAS。为达此目的,观测到这个问题事实上是一个单机排序问题,其中每个工作有最多h也许加工时间, 需要相关费用。因此问题(9)-(12)规定最大竣工时间最多C和最低限度的总成本的时间表。就其输入大小而言，这个问题的是FPTAS的证明在引理2中提及.每个工作的输入大小不超过加工时间和成本,因此就1 / 和原问题的大小而言它是多项式约束。因此, 对所有0 < < 1和 >0我们可以计算原输入大小的时间多项式、1 /和1 /,一个离最优解不大于因素(1 + 3) (1 + ) 的解决方案。让= / 6和=/ 3,我们得到(1 + 3) (1 + ),完毕了证明。
引理2：考虑一个单机排序问题,在那里我们有规定日期C，n个工作,每个都有h 种也许的模式s = 1,…,h其中它的加工时间是,费用是,s = 1,…,h。问题是为每个工作找到一个模式s, ,这样的总成本最小。这个问题认可完全多项式时间近似方案(FPTAS)。
证明：运用Pruhs和Woeginger的结论[21],这充足表白这个问题认可一种算法，即用一个就nh而言是多项式约束的计算时间解决最优性问题和问题的输入规模,W=。然后[21]的定理1说明这个问题是FPTAS。
下面的动态程序做这个工作。q = 1,…,n ,z = 0,…,W,由P[q,z]表达q个工作的最小总加工时间 这样总重量等于z。更准确的说, P[q,z]是最小的数，这样存在q个工作的一个进程时间是花费是的子集Q, P[q,z],。P[1,z]的初始化对任何值z = 0,…,W,来说很小。
P[q+1,z]=min{P[q,z-w]+p|(p,w)=()对一些s和未计划的j}.
一旦我们完毕了这个动态规划表格,我们发现最优值是
max{z|P[n,z]}.
在nh中运营动态规划的总规定期间是多项式约束和问题的输入大小，W=。
现在,再回到本来的问题上, 为了(1)-(4)有一个可行的解决方案我们可以用引理1的FPTAS来获得最小整数值的一个近似。由如下取得。对固定的> 0,我们发现为了让引理1的FPTAS产生一个对(5)-(8)具有值
(13)
的解，可以通过二叉搜索最小整数值。其中C:=。通过定义是满足(13)的最小的整数，FPTAS在值C上产生的解,通过引理1，(5)-(8)的最优解大于kC,因此(1)-(4)对C是不可行的。因此, ,(1)-(4)的最小整数值至少有一种可行解是 = C + 1,或。因此,是的一个下界,一个最优解的最大竣工时间。此外,运用引理1的FPTAS和(13),对
() (14)
我们有一个对于(1)-(4)具有约束条件(2)的整体解()。
因此,我们能得出结论——可以导出(1)-(4)的一种近似解法。
引理3：对任何> 0,我们可认为工作的资源消耗在多项式时间内找到一个整数值 使,一个整数解=(),
(15)
(16)
5、贪心算法
下面我们将介绍为获得调度问题的一个连续近似因素的方法。为了决定分派给每个工作j的资源数量，我们一方面运用上一节数学规划松弛的解。更准确的说,工作j必须用个独立资源解决 .然后工作以任意顺序根据Graham 的(改编的)贪心列表调度算法计算。
MP-Greedy算法:让资源分派是固定的以拟定数学规划的解。该算法反复时间周期t,开始是t = 0。我们做到以下几点直到所有工作都安排好了。
检查是否有一些没有违反了资源约束的尚未安排的工作可以在时间t在空闲的机器上开始。假如是,安排工作在时刻t开始；关系可以被任意打破。
假如没有工作在时刻t可以在任何一台机器上被安排,更新t到下一个最小的工作完毕时间> t。
很明显,该算法可以在多项式时间内实行。现在我们规定如下。
定理3：任意算法MP-Greedy对时间-资源函数的调度并行工作是一个(3 +)-近似算法。该算法的计算时间是在输入大小和精度1 /的多项式。
注意、到引理3的结果很大限度上改善了[8] 中3.75的性能约束。此外,还记得,方法[8]没有产生简明的编码时间-资源权衡函数的多项式时间算法。
证明：为了在数学规划松弛(1)-(4)中做二进制搜索的整数值,我们一方面使用引理1的FPTAS，让/ 2。如前面描述的同样，这在最优的时间表的最大竣工时间上产生了一个下界,在(1),(3),(4)和(14)中产生了一个整数解。我们再按解和贪心算法固定给每个工作分派资源。贪婪算法的分析自身是基于前面提到的[8]中相同的基本理念。为了方便,我们在这里完整证明。
考虑一些计划S由算法MP-Greedy所产生,并由表达相应的最大竣工时间。由表达最优解的最大竣工时间。对于计划S，让t()是时间上最早的点，这个时间之后，只有大工作被安排 ,资源消耗大于k/2的工作被定义为大工作。此外,让=−t()是只有大工作被解决的周期的长度。 (可以= 0)。
接下来,我们固定机器,机器i在时间t()上完毕的工作不是大工作。由于t()的定义,这样一台电脑必须存在，否则所有机器在t()之前是闲置的，阐述了贪心算法的定义。注意到, 在时间0和t()之间，机器i空闲的时间是存在的。定义为在时间0和t()之间机器i运转的总长度，表达在时间0和t()之间机器i空闲的时间的总长度。我们有
. (17)
由(15),我们得到机器i
(18)
下一步是的一个上界, 在机器i中只有大的工作正在解决的最后阶段,连同闲置时期的长度。我们定义
. (19)
看到这,得届时间表S的资源消耗总量至少是。这是由于,一方面,时间t()之后的所有工作都是大工作需要至少k/2资源。另一方面, 在时间0和t()之间机器i的空闲时间内，至少也应当有k/2的资源被占用。假设相反,在机器i上有一段空闲的时间所占用的资源至少是k/2。但是在那空闲时间之后,由于t()和机器i的选择,在机器i上运营的有些工作不是大任务。根据贪心算法的定义，这个工作本应当在空闲时间里被进行。下一步，根据(16)，定义(1+)k是工作的总消耗资源的上界。因此，我们得到
(1+)k.

除2 / k得到所要的界。
现在我们已经准备好证明定理3的性能界。一方面,用(17)连同(18)和(19)获得
(1+)=(3+).
最后,由于是的下界，由于选择/ 2，产生了3+=3+的MP-Greedy 性能界。
由于贪心算法明运营在多项式时间内，多项式计算时间服从引理1中的FPTAS。
6、下界
定理1表白,手边问题不允许性能约束小于1.5的近似算法。我们接下来表白,我们的方法可以给出一个离最优解相差2-的解。任何> 0。
例如1。考虑一个实例m = 3台机器和k = 2个单元的附加资源、线性时间-资源权衡函数。让一个整数是固定的。开始的两台机器被对称的分派两份工作。其中的一个工作有一个连续的加工时间(x)=-3,任意x=0,1,2.另一个工作有一个加工时间(x)=3+-假如被分派了x个单元的资源，这样唯一使这个工作尽也许小的方法是都分派这两个单元，这样(2)=3.。在第三个机器上我们有三份工作。两个相同短工作的加工时间是(x) = 3−x,和一段工作的加工时间(x) =-3x,x = 0,…,2。参见图1。

图1:黑色工作消耗2资源，灰色工作1资源，白色工作0资源。

命题1：存在一个具体的例子,在任何调度算法产生一个因数离最优化至少19/131.46的解的意义上，按数学规划松弛的解所提出的给工作分派的资源是错误的。此外,对于任何> 0,有例子证明算法MP-Greedy也许长生一个因数离最优解2-的解。
证明：考虑到例1中定义的参数例子，有参数。对任意可行最优解，由例子自身的性质，分派给工作的资源在开始的两台机器上是固定的(例如,小于2): 具有高压缩率的两个工作消耗两个单位资源，产生总得加工时间。在最优解中，由指派2资源给在第三的机器的长期工作,没有资源给小的工作得到最大竣工时间是。相应的时间表是如图1(a)。这样数学规划松弛(1)-(4)是可行的假如最小值C=。我们得到数学规划松弛的解是分派大的和小的工作各一个单元，分派给正在运营的小工作两个单元。这是由于在解决MP时,我们最小化了时间表的资源消耗总量,导致每台机器上的加工时间受C=的约束。在第三台机器上，最少资源消耗,导致最大竣工时间的条件是最多被实现，产生一个总的资源消耗量+1.。所有分派给第三台机器上的工作的资源或者违反了最大竣工时间约束或者需要更多的资源。（事实上最少要2()+1）。
由于没有两项资源的工作可以平行解决，就说明这个资源分派的任何时间表将提供一个最大竣工时间至少为3 + 3 +( −3)+ 1 + 2 = ' + 6的解。图1(b)描绘了这样一个时间表。由于将是最优解，当=13时，将产生所谓的比例19/13。另一方面,假如调度算法无法计算这种特殊解,极小化最大竣工时间变成2 −3,如图1(c)所描述。得到一个比率(2 −3)/,任意接近2。
是否存在这个问题的例子使算法MP-Greedy产生一个性能比比2差的解，目前还不清楚。
7、讨论
我们证明了存在计算表问题的(3+)-近似算法，这个算法中，工作的加工时间可以通过引进新的表，分散资源减小，如额外的个人。这个结果的好处和先前在[8]中的方法相比是我们明确的允许任何简朴形式的未编码时间-资源权衡函数。这涉及重要的特殊情况,如(分段)线性时间-资源权衡函数。对于这样的问题,没有多项式时间(近似)算法。除了这个结果,我们看到我们的重要奉献在方法论的方面,我们相信,也许尚有更多的应用, 解决NP-hard (整数) 的FPTAS数学规划会有用。进一步研究这个结果的肯能概念似乎是未来的研究方向；例[16]也是。

致谢
我们感谢Gerhard Woeginger几个有用的建议。特别是, Gerhard在文章[21]中指出,并且提出了在引理2的单个机器时间表问题中的FPTAS的证据。我们也感谢Frits Spieksma的评论，和匿名者对初期版本所提的建设性意见。

参考文献
[1] J. Blazewicz, J. K. Lenstra and A. H. G. Rinnooy Kan, Scheduling subject
to resource constraints: Classification and complexity, Discr. Appl. Math. 5 (1983),pp. 11–24.
[2] Z.-L. Chen, Simultaneous Job Scheduling and Resource Allocation on Parallel Machines,
Ann. Oper. Res. 129 (2023), pp. 135-153.
[3] M. R. Garey and D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completenes, W. H. Freeman, New York, 1979.
[4] R. L. Graham, Bounds for certain multiprocessing anomalies, Bell System Technical Journal 45 (1966), pp. 1563–1581. See also [5].
[5] R. L. Graham, Bounds on multiprocessing timing anomalies, SIAM J. Applied Math. 17 (1969), pp. 416–429.
[6] R. L. Graham, E. L. Lawler, J. K. Lenstra, and A. H. G. Rinnooy Kan, Optimization and approximation in deterministic sequencing and scheduling: A survey, Ann. Discr. Math. 5 (1979), pp. 287–326.
[7] A. Grigoriev, H. Kellerer, and V. A. Strusevich, Scheduling parallel dedicated machines with the speeding-up resource, manuscript (2023). Extended abstract in: Proceedings of the 6th Workshop on Models and Algorithms for Planning and Scheduling Problems, Aussois, France, 2023, pp. 131–132.
[8] A. Grigoriev, M. Sviridenko, and M. Uetz, Machine Scheduling with Resource Dependent Processing Times, Math. Prog. 110 (2023), pp. 209–228.
[9] A. Grigoriev and M. Uetz, Scheduling Parallel Jobs with Linear Speedup, in: Approximation and Online ALgorithms, T. Erlebach and P. Persiano (eds.), Lecture Notes in Computer Science 3879, Springer, 2023, pp. 203–215.
[10] R. Horst and P. M. Pardalos, Editors, Handbook of Global Optimization, volume 2 of Nonconvex Optimization and Its Applications, Springer, 1995.
[11] K. Jansen, Scheduling Malleable Parallel Tasks: An Asymptotic Fully Polynomial Time Approximation Scheme, Algorithmica 39 (2023), pp. 59-81.
[12] K. Jansen, M. Mastrolilli and R. Solis-Oba, Approximation Schemes for Job Shop Scheduling Problems with Controllable Processing Times, European Journal of Operational Research 167 (2023), pp. 297-319.
[13] J. E. Kelley and M. R. Walker, Critical path planning and scheduling: An introduction, Mauchly Associates, Ambler (PA), 1959.
[14] H. Kellerer and V. A. Strusevich, Scheduling parallel dedicated machines under a single non-shared resource, Europ. J. Oper. Res. 147 (2023), pp. 345–364.
[15] H. Kellerer and V. A. Strusevich, Scheduling problems for parallel dedicated machines under multiple resource constraints, Discr. Appl. Math. 133 (2023), pp. 45– 68.
[16] W. Kern and G. Woeginger, Quadratic programming and combinatorial minimum weight product problems, Math. Prog. 110 (2023), pp. 641–649.
[17] J. K. Lenstra, D. B. Shmoys and E. Tardos, Approximation algorithms for scheduling unrelated parallel machines, Math. Prog. 46 (1990), pp. 259–271.
[18] G. Mounie, C. Rapine, and D. Trystram, Efficient Approximation Algorithms for Scheduling Malleable Tasks, Proceedings of the 11th Annual ACM Symposium on Parallel Algorithms and Architectures, 1999, pp. 23–32.
[19] G. Mounie, C. Rapine, and D. Trystram, A 3/2-Dual Approximation Algorithm for Scheduling Independent Monotonic Malleable Tasks, Manuscript, Retrieved from
[20] P. M. Pardalos and G. Schnitger, Checking Local Optimality in Constrained Quadratic Programming is NP-hard, Oper. Res. Lett. 7 (1988), pp. 33–35.
[21] K. Pruhs and G. J. Woeginger, Approximation Schemes for a Class of Subset Selection Problems, Proceedings of the 6th Latin American Symposium on Theoretical Informatics, M. Farach-Colton (ed.), Lecture Notes in Computer Science 2976, Springer, 2023, pp. 203–211.
[22] D. B. Shmoys and E. Tardos, An approximation algorithm for the generalized assignment problem, Math. Prog. 62 (1993), pp. 461–474.
[23] M. Skutella, Approxim