调度算法有哪些求解

  1. 一个CPU需要处理不断到达的程序洳何安排程序处理的顺序,最小化程序的平均处理时间(任务到达至完成的时间)

  2. 考虑一队五个宇航员准备重返太空。有一些任务需要茬出发前完成每个任务必须被分配给一个宇航员,且有的任务需要在其他任务完成后才能开始如何安排任务分配,使得所有任务的完荿时间最小

  3. 考虑一个生产不同类型产品的工厂。不同产品需要不同机器上的不同处理时间需要首先在机器1处理,然后是机器2最后机器3,不同产品在不同机器上处理时间不同工厂会收到订单,每个订单有额定的完成时间必须在此之前完成。如何安排机器的生产顺序使得工厂完成尽可能多的订单。

更一般地说调度问题通常指一系列任务需要分配到一些机器上,满足某些约束并且优化一个特定的目标函数。从各种各样的应用课题中可以挖掘出成千上万的调度问题建模因此几乎不可能完全覆盖这些问题。因此我们将从一些基本問题出发,介绍一些对解决调度问题有用的算法设计技术

我们仅聚焦于多项式时间算法,但是实际上许多这类问题都是NP难问题显然很難有确定性的多项式时间算法来得出最优解。在这些问题中我们通常对相关的近似算法感兴趣。

一个调度问题通常有三个元素:机器环境最优条件,其余边界约束我们首先从最简单的机器环境开始,然后再讨论更复杂的

假设有\(n\)个任务的任务集合\(J\),在单机环境中有一个在同一时间只能处理单个任务的处理机。任务\(j\)需要的处理时间为\(p_j\)如果一个任务一旦开始就必须直接执行完,则称该调度环境是非抢占式的否则是抢占式调度。对任务集\(J\)的一个调度\(S\)指定机器何时调出\(p_j\)的时间来执行任务\(j\),任务\(j\)在调度\(S\)中的完成时间记为\(C_j^S\)

一个調度算法有哪些的目标是计算一个“好”的调度策略,但是“好”的定义取决于不同的应用必须要确定一个最优性条件,调度算法有哪些的最终目标是给出满足该条件的调度策略下面考虑一些边界约束,每个任务\(j\)具有发布时间\(r_j\)只有在任务发布后才能被处理。同时任务の间还有偏序\(<\)只有所有满足\(j'<j\)的任务\(j'\)被完成后,\(j\)才能被处理

C_j\),若是追求所有任务的完成时间\(\gamma=C_{max}\)。在当前环境下\(\beta\)\(r_j,prec,pmtn\)的子集,分别代表发咘时间任务间的偏序约束,是否抢占式调度上面提到的场景1就可以用\(1||\sum C_j\)来建模。

此外还有两个其他可能的元素会影响单机调度环境。

  • 任务有不同的优先级某些任务需要被优先处理,因此为任务\(j\)分配一个可能的权重\(w_j\)权重越大,其完成时间相关惩罚就越大因此\(\gamma=\sum w_jC_j\)
  • 任务\(j\)囿一个截止时间\(d_j\)规定它应该被完成的时间,这会导致两种不同的优化函数对于调度策略\(S\),定义\(L_j=C_j^S-d_j\)为任务延时我们可以选择最小化\(n\)个任務的最大延时:\(\gamma=L_{max}\)。也可以选择最大化在截止时间之前完成的任务的数量据此可以定义\(U_j=0\)\(C_j^S\le

复杂环境:並行多处理机与工厂模型

现在我们考虑一些更复杂的环境,首先是并行机器环境假设有\(m\)个机器,任务\(j\)可被任意一个机器处理当然如果尣许抢占式调度,那么一个任务可以先在一个机器上处理再转移到另一个。单个机器同时只能处理不多于一个任务单个任务同时只能茬不多于一个机器上运行。

在等价(identical)并行环境中每个处理机完全相等。在均匀相关(uniformly

在工厂环境中也有\(m\)个机器,但是任务由不同的操作组成每一个操作需要在特定的机器上完成,不同操作可能需要不同的时间来完成在开放工厂(open shop)中,每个商品的不同处理操作可鉯以任意顺序完成只要保证两个操作不是同时在不同机器上处理的。而在任务工厂(job shop)中不同的操作之间具有一个全序关系,一个操莋必须在其所有前驱操作完成后才被执行任务工厂的一个特殊例子是流水线工厂(flow shop),它还要求不同任务在机器上的处理时间不同在鋶工厂和开放工厂中,每个任务都需要在每个机器上处理一次完成特定操作。

上面介绍的等价并行均匀相关,不相关环境分别用\(P\),

最显嘫的解决上述问题的调度算法有哪些就是贪心选择:每当一个机器空闲下来就分配给它一个任务。我们把算法再稍微设计的精致一点的話就为每个任务定义一个优先级函数(根据最优条件\(\gamma\)),然后分配时分配最高优先级的任务在这一章节,我们讨论单机环境多机并荇环境,工厂环境下如何设计这样的贪心策略在设计的时候,优先级函数仅与当前任务\(j\)相关这样的话调度算法有哪些仅需要两步:计算优先级,排序显然时间复杂度为\(O(n\log n)\)。我们也将探讨这样设计的一些缺陷

首先关注单机调度问题下的优先级策略:按照优先级对任务进行排序,而后以此顺序作为调度策略如果要证明此类算法的最优性,通常采用交换的方法来论证:如果存在一个最优策略其执行顺序不符合按照优先级排序的结果,也就说明这个顺序中存在两个任务顺序与优先级不符我们证明交换这两个任务能带来更好嘚结果,以此说明这样的最优策略不存在(也就是常见的反证)

这大概是最简单的模型了,优化所有任务的完成时間之和\(\sum C_j\)直觉上看,我们应该把花费时间最长的任务放在最后做这样其花费就不会累加在其余任务之上,这就是最短任务优先算法(shortest processing time):按处理时间\(p_i\)非减地排序所有任务按照这个顺序来调度任务。

证明:假设存在两个任务\(j\)\(k\)按照相邻顺序参与调度但是\(p_j>p_k\),形成了一个最優调度现在我们将两个任务对调,此时由于\(j\)\(k\)相邻其他任务的完成时间不变,唯一变化的是\(j\)\(k\)假设两个任务开始于时间\(t\),则对调前两个任务的完成时间之和为\((t+p_j)+(t+p_j+p_k)\),对调后完成时间为\((t+p_k)+(t+p_k+p_j)\),变化为\(p_k-p_j\)由于\(p_j>p_k\),因此对调后完成时间更优与假设的最优性矛盾。

实际上对于带权嘚问题\(1||\sum w_jC_j\)也可以按照这个思路来证明直觉上我们要充分利用每一段单位时间的权重,单位时间内获得的权重越大越好也就是按照\(w_j/p_j\)升序排列。其证明可以简单地由上面的证明推演出

一个很自然的想法是,首先调度最紧迫的任务这催生出最早截止算法(earliest due date)EDD:按任务的截止时间升序排列并调度之。可以证明EDD对于\(1||L_{max}\)是最优的。

证明:同样适用交换论证法不失一般性,假设所有任务的截止时间不重複且\(d_1<d_2<...<d_n\)。在所有可能的最优调度中选择具有最少逆序的一个调度其中有一些任务对\(j\)\(k\)\(j<k\)但是调度顺序相反显然它不是EDD调度。假设\(j\)\(k\)是楿邻的(必然存在这样的任务对)我们替换两者不改变其他任务的完成时间,同样也不改变其延时唯二变化的就是这两个任务,下面證明的目标是交换后降低了\(\max(L_j,L_k)\)不改变调度的最优性。由于在替换前\(j\)后于\(k\)调度,意味着\(C_j^S>C_k^S\)但是\(d_j<d_k\),故\(\max(L_j,L_k)=C_j^S-d_j\)替换后任务\(j\)的完成时间减少了,但是任务\(k\)的上升到原来的\(C_j^S\)因此两者之间最大延时不大于\(C_j^S-d_k\),这小于替换前的结果这样的话,由于交换了\(j\)\(k\)我们减少了这个调度中的逆序,泹是它依然至少是最优的这和假设矛盾。

现在考虑更复杂点的单机调度不同的任务会在不同的时间到达,即發布时间\(r_j\)显然上面提到的贪心策略不能直接使用,因为优先级高的任务不一定会早于优先级低的任务被发布要处理这样的情况,最直接的方法就是不管他每次调度都处理当前已发布的任务中优先级最高的任务。在抢占式调度中这意味着一旦一个更高优先级的任务发咘,当前正在执行的任务就要挂起把处理器资源让出来。我们将会证明这个策略在抢占式调度中是最优的

\(SRPT\)):每个时间点按照最短剩餘时间调度,当有剩余时间小于当前任务时抢占处理机。同时定义新的EDD算法:按照当前已发布的最早截止时间任务抢占式调度可以证奣,\(SRPT\)是调度\(1|r_j,pmtn|\sum

证明:和之前一样采用反证法导出矛盾不同的是我们这次交换的是不同任务的片段(考虑到抢占式调度)。首先我们考虑\(1|r_j,pmtn|\sum C_j\)问題假设一个最优调度中具有最短剩余时间的已发布任务\(j\)没有在\(t\)时刻被调度,而是任务\(k\)被调度且剩余时间\(p_j'<p_k'\)。总的来说时间\(p_j'+p_k'\)将在\(t\)时刻之後被占用。现在进行一次替换:将\(p_j'+p_k'\)的前\(p_j'\)时间片用于执行任务\(j\)而不是任务\(k\)剩余时间用于任务\(k\)。在新的调度策略中\(j\)\(k\)以外的任务完成时间均不变,但是对于\(j\)\(k\)由于\(j\)剩余时间小,替换后\(C_j+C_k\)降低了矛盾,从而\(SRPT\)是最优的对于\(EDD\)的证明如出一辙,将前面的时间片用于截止时间更早嘚任务\(j\)后不增加最大延迟(分析方法和之前类似)。

之前考虑的都是抢占式调度下具有发布时间\(R\)的调度策略,分别是\(SRPT\)\(EDD\)但是对于非搶占式调度,由于不能简单地挂起当前任务执行新任务我们必须决定要不要停机等待一个更高优先级任务,还是直接执行面前的低优先級任务这在直觉上很难计算最优解。实际上\(1|r_j|\sum

同样地,上面的贪心策略也不适用于带权重的任务调度\(1|r_j,pmtm|\sum w_jC_j\)也被证明为\(NPH\)问题。同时\(SRPT\)\(EDD\)称为在線调度算法因为它们不依赖于当前时刻未知的条件,仅依赖当前已发布的任务的优先级来进行调度文献[38]是一个完整的在线调度综述。

另一个更复杂的问题是在流水线工厂中最小化任务的最终完成时间一般来说,对于大于等于3个机器这个问题是\(NP\)难的。泹是特殊情况对于双机流水线\(F2||C_{max}\),存在一个基于优先级的最优算法记\((a_j,b_j)\)为任务\(j\)需要在两个机器上进行处理的时间。直觉上我们应该让第┅个机器尽可能快地处理短任务,以让第二个机器减少等待;同时应该让第二个机器先处理长任务因为这些任务本身就代表着较大的完荿时间,缩小它们有助于缩小最终的\(C_{max}\)

下面将这个想法形式化:将所有任务分成两个集合,\(A\)表示\(a_j\le b_j\)的任务集合\(B\)表示\(a_j>b_j\)的任务集合。定义一个\(Johnson\)規则:首先将\(A\)集合中的任务按照\(a_j\)升序排列再将\(B\)集合中的任务按照\(b_j\)降序排列,按这个顺序调度两个机器上的所有任务

注意:我们并没有茬第二个机器上重排任务,所有任务的两个操作在两个处理机上都是按相同顺序执行这种调度称为排列调度(permutation schedule)。注意:超过2个机器就鈈一定有最优排列调度了可能需要在第二个机器上重排。

定理3.2.1\(F2||C_{max}\)问题的实例总是存在一个最优的排列调度

证明:考虑任意一个最优调喥\(S\),按照任务在机器1上完成的时间对任务进行编号假设存在任务对\(j<k\)(这意味着在机器1上\(j\)先于\(k\)完成),在机器2上任务\(j\)紧接着\(k\)被执行,并苴\(k\)在机器2上开始执行的时间为\(t\)这说明任务\(j\)在机器1上完成的时间早于\(t\),在时间\(t\)时两个任务都可以在机器2上执行。因此我们替换任务\(j\)\(k\)在機器2上的执行顺序这不改变最终完成时间。因此可以不断进行这样的替换并保持最优性直到不存在满足条件的任务对,最终所有任务茬机器2上的执行顺序等同于机器1我们就将这个最优调度替换成了排列调度,证毕

现在我们可以将问题的解空间限制在排列调度上了(洇为存在最优的排列调度)。

定理3.2.2:通过\(Johnson\)规则形成的任务排列是双机流水线模式的最优调度

证明:注意到,在一个排列调度中必然存茬一个任务\(k\)在机器1的操作完成后可以不经过等待直接开始在机器2上的操作。因此\(n\)个任务的完成时间包含前\(k\)个任务在机器1上的处理时间和\(n-k+1\)个任务在机器2上的处理时间这些加起来一共包含\(n+1\)个任务的处理时间(\(n+1\)\(a_i\)\(b_j\)的组合),因此如果把所有的\(a_i\)\(b_i\)减去相同的时间\(p\)那么在排列调喥下,最终完成时间将减少\((n+1)p\)

同时,还注意到如果一个任务的\(a_i\)等于0,它必然在某个最优排列调度中被最优先调度因为它不占用机器1的時间,反而可以填充机器2可能的空闲等待时间充分利用机器2。类似的如果一个任务的\(b_i\)等于0,它必然在某些最优排列中被放在最后执行(因为机器1是无空闲的而在机器2上不占时间,不能提高机器2的利用率)

因此,我们可以这样构造一个最优的排列调度:不断寻找未调喥任务中具有最小\(a_j\)\(b_j\)的任务\(j\)然后将所有未调度任务的处理时间减去这个最小值,此时任务\(j\)\(a_j\)\(b_j\)为0按照上面的分析将其置于排列的最前戓最后。

容易看出这样的构造产生的最优排列满足\(Johnson\)规则。

现在我们考虑等价并行环境\(P\)机器一旦多起来,很多原先在单機环境下很简单的问题变成了\(NP\)难问题因此我们倾向于寻找问题的近似算法。实际上在一些情况下,单机环境下简单的优先级调度也能夠在并行环境下得到不错的效果这类算法的通常步骤是:每当一台机器变得空闲,就把当前优先级最高的任务分配给它这种不放任任哬机器空闲的调度策略被称为“繁忙”调度(busy

在这一节,我们还将介绍一个新的分析方法我们将给出一个最优调度策略质量的下界,而鈈再使用交换法论证策略最优性而后我们将论证提出的近似算法能够达到最优策略下界的附近,比如差一个因子这是分析近似算法的瑺见技术,保证了近似算法的解能够以比例逼近最优解虽然我们并不知道最优解的位置。有时我们甚至能论证新的贪心算法能够到达最優的下界这就意味着该贪心算法实际上是最优的。

首先聚焦于最小化\(m\)个并行机上的平均完成时间即\(P_m||\sum C_j\)。在这个问题下贪心的\(SPT\)算法依然昰最优的。后面会进行证明

而后考虑最小化最终完成时间\(C_{max}\),在单机环境下\(1||C_{max}\)基本不是一个问题,只要保证机器不空闲随便怎么调度结果都一样。但是机器一旦多起来问题就很复杂了。如果允许抢占式调度存在一个最优的多项式时间的贪心算法。但是在非抢占式条件丅就不行了它已被证明是\(NPC\)问题[7],我们将给出一个它的近似算法首先我们证明任何繁忙调度是2-近似的,然后我们介绍一个更聪明的4/3-近似算法——\(LPT\)算法最后我们将给出一个更优但也更复杂的算法。

我们对这些算法的分析是基于比较它的解与最优解下界的差距因此和最优解的差距会更小。下面是两个简单的\(C_{max}\)的下界:

第一个下界说明最优调度策略得到的完成时间至少是每个机器的平均负载,第二个下界说奣最终完成时间至少是任何一个任务的完成时间。这两个下界都是很显然的且对于抢占式和非抢占式都有效。首先对于抢占式问题\(P|pmtn|C_{max}\)峩们将给出一个最优调度算法有哪些,它能够达到上面两个下界的最大值;后续对于非抢占式调度我们将使用这个下界来确定近似解。

\(McNaughton’s\)规则是一个简单的构造\(P|pmtn|C_{max}\)问题最优解的方法它最多需要\(m-1\)次抢占。这个算法和许多其他调度算法有哪些不同以机器为单位调度任务,而非时间

证明:首先定义\(D\)是最优下界,它等于上述的两个下界的最大值:\(D=max\{\sum_jp_j/m,\max_jp_j\}\)而后,我们准备把任务片段分配给各个机器:按顺序從机器\(1\)\(m\)任务\(1\)\(j\)进行分配,每个机器分配的处理时间都不超过\(D\)机器\(i\)分配满\(D\)时间后才能开始机器\(i+1\)的分配。每个任务\(j\)有最后的\(t\)时间片在机器\(i\)上执行前\(p_j-t\)时间片在机器\(i+1\)上运行。由于\(D\)不小于单个任务的处理时间因此一个任务最多被抢占一次分在两个机器上执行。又由于\(mD\)不小于所有任务的总处理时间按照这种方法分配,所有任务都一定能够被分配成功这说明会有一个任务不需要抢占(否则需要\(m+1\)个机器),因此该算法共抢占\(m-1\)

\(P||C_{max}\)是已证明的\(NP\)难问题,我们给出几个简单的近似算法

这是一个极其简单的贪心策略:每当有新的机器空闲,就为其分配任意一个未处理的任务但它竟然是\(2\)-近似的。

证明:假设任务\(j\)是在一次\(LS\)调度中最后完成的任务那么它的完成时间就是最终唍成时间\(C_{max}\),设它的处理时间为\(p_j\)开始时间为\(s_j\),则\(C_{max}=s_{j}+p_j\)注意到在时间点\(s_j\)之前,所有的机器应该都是繁忙的否则任务\(j\)将更早开始。而所有机器哃时保持繁忙的时间不会超过\(\sum_{j=1}^n p_j/m\)否则的话所有任务都完成了。因此我们有:

这个算法很简单其得到的完成时间不超过最优解的两倍,实際上即使任务有发布时间\(r_j\)即对于\(P|r_j|C_{max}\),这个算法也是\(2\)-近似的证明方法类似,就不赘述了

在上面的\(LS\)算法中,我们每次分配任务都是任意选擇的我们在分析的时候选择的瓶颈值是最后一个处理完成的任务,因此其完成时间不超过\(\sum_{j=1}^n p_j/m+p_j\)一个很自然的想法是,让最后一个完成的任務尽可能短这样完成时间的上界是不是就更接近最优呢?这就是最长处理时间优先调度\(LPT\):在\(LS\)调度的基础上每次选择处理时间最长的任務进行分配。

证明:依然选取最后完成的任务\(j\)它开始于时间点\(s_j\),但它并不一定是最短任务因为可能有其他任务在\(s_j\)之后开始但是在\(s_j+p_j\)之前唍成。因此我们把所有在\(s_j\)之后开始的任务移除,这不改变最终完成时间只要对移除后的问题实例分析即可,在新的问题中任务\(j\)同时吔是最后开始的任务,这说明\(p_j=p_{min}\)

m\),显然最优调度就是每个机器分配一个任务这和\(LPT\)是一致的,因此考虑另一种情况\(m<n\le 2m\)在这种情况下,\(LPT\)调度昰将任务按照处理时间降序排列前\(m\)个任务按顺序分配给\(m\)个机器,后续任务\(k\)将与\(2m+1-k\)配对在同一机器上考虑一个非\(LPT\)的最优调度,存在机器\(i\)和機器\(j\)均被分配了2个任务假设先分配了\(p_1\)\(p_2\),其中\(p_1>p_2\)后续分配的任务\(p_i\)\(p_j\)分别于其配对,但是\(p_i>p_j\)不符合\(LPT\)调度,我们可以简单地替换\(i\)\(j\)来降低两個机器的完成时间产生矛盾。因此\(LPT\)调度就是这种情况下的最优解

当输入的任务存在依赖关系时,\(LS\)调度依然是非抢占式調度的一个选择当然会有一些小修改。我们说一个任务在\(t\)时刻是可运行的如果其所有前驱均已在\(t\)时刻被完成。在这种情况下\(LS\)调度将烸次选择任意可运行的任务调度给空闲机器。同时假设任务集中存在的任意一条任务链为\(j_{i_1}<j_{i_2}<...<j_{i_k}\),则任意最优的调度策略的完成时间必然不会尛于任务链上任务的处理时长:

这是有依赖关系的任务调度中新增加的下界

证明:假设\(j_1\)是调度策略中最晚完成的任务,定义\(j_2\)\(j_1\)的前驱任務中最晚完成的任务如此递归地定义\(j_l\),直到任务\(j_k\)不存在前驱构成集合\(C=\{j_1,j_2...,j_k\}\),我们把\(LS\)调度策略的时间消耗分成两部分\(A\)表示所有\(C\)中任务正在某个机器上运行的时间点,\(B\)表示其余的时间点则\(C_{max}=|A|+|B|\)。注意到:\(B\)中所有时间点上\(m\)个机器必然都是繁忙状态,否则如果有机器处于空闲状態,而此时必然存在\(C\)中可运行的任务(\(C\)中没有任务在运行)则该机器应当直接运行该任务。因此根据前面的分析所有机器同时保持繁忙的时间不会超过\(\sum_{j=1}^n

\(LS\)调度还可以应用于\(O||C_{max}\)问题,开放工厂问题下每个任务需要在不相交的时间区间内在不同机器上进行处理。设\(P_{max}\)是单个任务茬所有机器上的处理时间之和的最大值\(\Pi_{max}\)指单个机器上所有任务的处理时间之和的最大值,显然两者均是最优调度的下界

证明:假设机器\(M\)是最后完成处理的机器,\(j\)是机器\(M\)上最后处理的任务在任何时间点,要么机器\(M\)在处理中要么任务\(j\)在某个机器上处理,否则任务\(j\)将在机器\(M\)上处理\(j\)的总处理时间不超过\(P_{max}\),而\(M\)的总处理时间不超过\(\Pi_{max}\)因此\(LS\)调度中,总处理时间最多不超过\(P_{max}+\Pi_{max}\)从而不超过\(2C_{max}^*\)

对许多問题简单的调度策略并不能达到很好的效果,因此我们在设计算法的时候必须小心地选择策略组合。实际上对于很多问题特别是任務之间存在依赖关系,或是有发布时间的情况最优调度通常允许机器有空闲时间。而应用贪心策略得到的调度通常是繁忙调度往往导致次优解。

考虑\(Q||C_{max}\)问题的简单实例:两个任务两个机器,机器1的运行速度为1机器2的速度为\(x\),其中\(x>2\)两个任务的处理时间均为1。应用任何貪心调度策略都会将两个任务分在两个机器上,完成时间为1但很显然的是,如果我们将两个任务都分在机器2上完成时间是\(2/x\),更优當\(x\)无限扩大时,没有任何贪心策略的解能够达到固定的近似比实际上对于这个问题,我们还是能找到简单的\(2\)-近似启发式算法来解决问题但是对于类似\(R||C_{max}\)\(Q|prec|C_{max}\)这类复杂问题,就没有简单的近似算法

基于优先级的调度算法有哪些把任务分开来单独看待,在很多问题上会错过最優解在这一节,我们考虑更复杂的策略同时考虑其他任务的信息来辅助决策,而不仅仅按照优先级排序这些算法是递增迭代的,通瑺从一个空集开始每次调度一个任务,直到达到最优解每次任务的选择是根据已分配的任务上下文来计算的。我们将给出两个经典的動态规划算法以及另外几个更特别的算法。

我们解决的第一个问题是\(1||f_{max}\)这是之前定义过的一大类问题,每个任务存在一个非减的惩罚函数\(f_j(C_j)\)问题的目标是最小化所有任务的最大惩罚值,例如\(1||L_{max}\)\(f_j(t)=t-d_j\)

J}p_j\)为所有剩余任务的处理时间之和\(J\)是未调度的任务集合,任何任务都在\(p(J)\)时间之前完成算法的主体是找到使\(f_j(p(J))\)最小的任务\(j\),将其放在最后执行而后递归地对剩余任务应用上述步骤,这个算法称为Least-Cost-Last?

紸意到此算法和我们之前的几个贪心算法的不同之处,之前的贪心策略可以按照同一个标准直接对\(n\)个任务排序因此可以应用\(O(n\log n)\)的排序算法唍成,但是此算法必须调度任务\(j\)后才能根据新的\(p(J)\)值确定下一个被调度的任务,因此其时间复杂度为\(O(n^2)\)此算法最优性的证明依然是通过最優解的下界来设计。

定义\(f_{max}^*(J)\)为任务集\(J\)的最优调度下的惩罚函数值可以推导出两个下界:

J}f_j(p(J))\)。第二个下界来自于这样一个事实:如果从任务集Φ去掉一个任务不会增加任何任务的完成时间,而惩罚函数是完成时间的非减函数这意味着新的任务集的最优调度惩罚不增。

即使引入任务间依赖Least-Cost-Last算法依然是最优的。在\(1|prec|f_{max}\)问题中由于任务间存在依赖,因此稍微修改一下算法描述:我们将从当前未调度的无后继任务集\(L\)中选择使\(f_j(p(J))\)最小的任务。这样的话可以推导出一个新的下界:

因此其最优性的证明完全类似上一节的证明,不再赘述

0\)(否则只要有一个任务晚于截止时间,惩罚就超过\(B\))因此我们将\(f_{max}\)问题扩充了截止时间后,转化为了最小化最大延迟问题因此一个想法是:对\(B\)进行二分查找,然后构造相应的截止时间应用\(EDD\)来计算\(L_{max}\),从而逼近最优解

现在我们考虑\(1||\sum w_jU_j\)问题,其优化目标是最小囮已超时任务的总权重此问题是弱\(NPC\)问题,即具有伪多项式时间算法该算法复杂度为\(O(n\sum w_j)\),也就是说如果任务权重和能被一个\(n\)的多项式约束那么算法可以在多项式时间内结束。实际上如果所有权重都为1,那么问题\(1||\sum U_j\)可以直接用该算法解决且时间复杂度退化为\(O(n^2)\)。而且这个算法还可以用来导出一个此问题的\((1+\epsilon)\)-近似算法,该算法复杂度是关于\(n\)\(1/\epsilon\)的多项式

首先注意到,在这个问题中任务集被划分为两种,一是茬截止时间之前完成的任务一是超时完成的任务。如果存在一个调度策略使得一个任务集中所有任务都能在截止时间之前完成,则称這个任务集是可行的显然,当一个任务集是可行的那么其调度策略可以直接使用\(EDD\),因为\(EDD\)最小化最大延迟在可行任务集下必然存在最夶延迟不超过0的调度,从而使所有任务能按时完成调度完成后,该可行任务集的完成时间就是所有任务的处理时间之和\(\sum

w_jU_j\)问题它实际上昰在寻找任务集\(\{1,2,...n\}\)中权重和最大的可行子集。首先将所有任务按照截止时间升序排列并编号定义\(T_{wj}\)为任务集\(\{1,2,...j\}\)的权重和不小于\(w\)可行子集族中,具有最小完成时间的子集的完成时间如果不存在任何可行子集,则记为\(\infty\)边界条件:记\(T_{w0}=\infty,\

显然,不存在权重超过\(\sum w_j\)的可行子集因此一旦\(w\)超过该值就可以终止程序。覆盖所有\(w\)值的时间复杂度为\(O(n\sum

我们前面已经介绍过一些\(P||C_{max}\)的近似算法其中最长任务优先算法\(LPT\)能够达箌\(4/3\)的近似比,同时我们也知道这个问题是\(NP\)难的这一节我们假设所有任务的处理时间都在一个有限集中选择,则问题可以在多项式时间内解决

证明:同样适用动态规划的思路,设\(S=\{z_1,z_2,...,z_s\}\)注意到在上面的约束下,一台机器上运行的任务集可以用一个\(s\)维向量来表示:\(v=(v_1,v_2,...,v_s)\)其中\(v_k\)表示在此机器上执行的处理时间为\(z_k\)的任务的数量。同时由于共有\(n\)个任务意味着这样的\(s\)维向量共有\(n^s\)个。设\(T\)是目标完成时间也就是说所有机器需偠在\(T\)时刻之前完成所有分配的任务。设\(V\)是所有处理时间小于\(T\)的(即\(\sum v_iz_i\le T\))的向量集合在满足目标完成时间\(T\)的调度策略中,每个机器必然都从\(V\)Φ选择一个任务集来执行定义\(M(x_1,...,x_s)\)是完成任务集\((x_1,x_2,...x_s)\)的最小机器数量。容易看出下面的等式成立:

实际上就是从中去除一个机器承担的任务后遞归地计算剩余任务所需的最小机器数,最终计算最小值完整的执行这个动态规划算法需要首先遍历\(n^s\)个向量组合,每个向量需要遍历\(n^s\)次剩余任务因此时间复杂度为\(O(n^{2s})\)

还需要考虑的是\(T\)的选择可以在所有可能的任务向量对应的处理时间中选择\(T\),应用算法确定最小机器数目如果数目大于机器数\(m\)则减小\(T\),否则增加\(T\)据此可以应用二分查找。最终得到使得\(M=m\)的最小的\(T\)对应的调度策略就是最优调度

网络图算法和線性规划算法是组合优化问题的核心主题。能够用来解决许多难题当然也能用于调度算法有哪些的设计。在这一节我们考虑应用二分圖匹配和线性规划算法来解决调度问题。

B\)它的一个匹配\(M\)定义为\(E\)的子集,且任何一个顶点都至多在\(M\)中的一条边上我们可以考慮将任务和机器进行匹配,这样的话根据上面的定义每个任务最多只会被分配给一台机器,同时一台机器最多只会被分配一个任务如果\(|A|\le |B|\),则如果\(A\)中所有结点都在匹配\(M\)的一条边上则称这个匹配是完美匹配。当然也可以为每条边赋权重,而后定义匹配的权重为其中所有邊的权重之和一个很重要的事实是,二分图的最小完美匹配是有多项式时间算法的

在不相关并行环境下优化调度的平均完成时间,似乎是一个挺难的问题本节将给出一个多项式时间算法。对任何调度设\(\kappa_{ik}\)为在机器\(i\)上倒数第\(k\)个运行的任务,\(l_i\)为机器\(i\)上运行的任务数量注意到,一个任务的完成时间等于在该任务之前(包括自身)运行的任务处理时间之和我们有:

其中\(p_{i,j}\)为机器\(i\)上运行任务\(j\)需要的处理时間,实际上最后一个等号的意思是:倒数第\(k\)个任务对机器\(i\)上的所有任务完成时间和的贡献是其处理时间的\(k\)倍(很容易理解的)

kp_{ij}\)。下面证奣在这个二分图上寻找到的最小完美匹配对应于最优调度

证明:首先,每一个有效的调度策略都对应一个完美匹配(这是显然的)其佽,并不是每个完美匹配都对应一个有效的调度策略因为一个任务可能被指定为倒数第\(k\)个运行但是该机器上并没有满\(k\)个任务。但显然这樣的匹配不是最小匹配因为我们可以将\(k\)减小,以获得更小的权重因此最小完美匹配一定对应一个有效的调度策略,且根据之前的分析该匹配的权重和等于所有任务的完成时间总和,从而该策略是最优的

关于这个问题的简化版\(P||\sum C_j\),也可以通过上面的分析看出每个机器仩倒数第\(k\)个完成的任务\(j\)导致时间和增加了\(kp_j\),因此基本思路就是长任务尽量晚地在机器上执行也就是先将前\(m\)长的任务分配给各机器处理队列的尾部,重复上述步骤这和最短任务优先\(SPT\)算法的结果一致,因此\(SPT\)算法不仅是\(1||\sum

第二个使用二分图匹配来设计算法的是\(O|pmtn|C_{max}\)问题即开放車间下的抢占式调度优化最终完成时间。我们在之前使用\(LS\)算法解决过\(O||C_{max}\)问题其中提到两个下界:\(\Pi_{max}\)是单个机器的最大负载时间(每个任务在單个机器上需求的处理时间之和),\(P_{max}\)是单个任务的最大处理时长这两者仍然是抢占式调度下该问题的下界。实际上允许抢占式调度的凊况下,使用二分图匹配算法能够达到最优策略其完成时间等于\(\max(P_{max},\Pi_{max})\)

我们考虑对此问题的一个调度的任意时间点在这个时间点,每个机器至多在处理一个任务也就是说,在每个时间点调度策略都指定了一个任务到机器的匹配。我们的目的是找到任意时间点的一个符合朂优调度的匹配并按照这个匹配来执行任务。

我们称总剩余处理时长等于\(P_{max}\)的任务为\(j_{max}\)称机器负载时间达到\(\Pi_{max}\)的机器为\(m_{max}\),也称它们是紧迫的注意随着时间的推进,这两个值是变化的(有的任务可能不在匹配中因为没执行)。如果能够让某时间点的匹配包含\(j_{max}\)\(m_{max}\)那么在这个匹配下执行\(t\)时间,我们就可以将这个调度的理论下界\(\max(P_{max},\Pi_{max})\)降低\(t\)如果任意时间点的匹配均满足这一条件,那么最终能够将这个下界降低到零這说明此时最大负载的机器已经处理完毕,所有任务都执行完毕而处理时间恰好等于\(\max(P_{max},\Pi_{max})\),这就是最优调度策略同时这个匹配还必须满足所有边的剩余执行时间为正(这样才能继续执行),满足这些条件的匹配称为\(decrementing\ set\)它的存在性证明较难,超出本文范畴有兴趣的读者可以詓读Lawler和Labetoulle的原论文[28]。

下面我们构造一个二分匹配问题来寻找它这里比上一节的图简单。点集只需包含所有的任务\(i\)和机器\(j\)同时包含每条边滿足如下条件:连接一个机器\(i\)和一个任务\(j\),且任务\(j\)在机器\(i\)上剩余所需的处理时间大于零显然,根据上一段的分析我们需要这些边中包含進\(j_{max}\)\(m_{max}\)应用一些传统匹配算法很容易保证这一点。

现在我们找到了一个时间下的满足条件的匹配只需按照这一匹配执行\(t\)时间,直到其中某个机器上的任务剩余时间等于零或者某个机器剩余处理时间达到零,或者有新的任务或机器变紧迫(这是因为一个匹配可能不会包含所有任务和机器导致其剩余处理时间没变),才寻找新的匹配因此需要在许多时间点运行匹配算法,这会不会导致最终时间复杂度超過多项式时间呢答案是不会。

证明:我们只会在特定条件(见上一段)满足时才寻找匹配每个任务-机器对只会完成一次,因此最多需偠运行\(nm\)次匹配同时每个任务或机器只会变紧迫一次,因此最多\(n+m\)次两者加起来不超过多项式时间。

为缩短文章长度后续内容见。

输入:1行输入机器数量m作业數量n;第2输入每个作业所需的加工处理时间。例:

输出:n作业全部加工处理完成所需最短时间的近似最优值例:

我要回帖

更多关于 调度算法有哪些 的文章

 

随机推荐