陳道蓄

說到“調(diào)度”，人們往往會想到交通運(yùn)輸部門的運(yùn)行安排，也會想到企業(yè)中復(fù)雜的生產(chǎn)任務(wù)安排。其實(shí)，日常生活中也經(jīng)常面臨著多個事項(xiàng)需要合理安排;只不過任務(wù)數(shù)不大，也不涉及明顯的經(jīng)濟(jì)指標(biāo)限制，人們憑經(jīng)驗(yàn)就足以應(yīng)付，很少會聯(lián)想到“算法”。當(dāng)需要解決的任務(wù)數(shù)增加，且包含相互依賴關(guān)系時，算法可以幫助我們順利有效地完成任務(wù)。

● 單純依賴關(guān)系約束下的任務(wù)調(diào)度

我們從僅考慮任務(wù)間的依賴約束開始。如果任務(wù)X只能在另外某個任務(wù)Y完成后才能開始，我們就說X依賴Y。下面來看一個簡單的例子。

同學(xué)們打算在教室里組織一場聯(lián)歡活動，還準(zhǔn)備自己動手包餃子。他們擬定了一張準(zhǔn)備工作任務(wù)表，包含所有任務(wù)事項(xiàng)、每項(xiàng)任務(wù)耗時、任務(wù)間依賴關(guān)系（注意：只需列出直接依賴關(guān)系，而間接依賴關(guān)系自然地隱含在其中）。管理上通常將這些任務(wù)的集合稱為一個“項(xiàng)目”。任務(wù)列表見表1。

有些任務(wù)之間沒有依賴關(guān)系，執(zhí)行順序無關(guān)緊要，如果有多個執(zhí)行者，這樣的任務(wù)就可以并行。這里說的“調(diào)度”，就是要給每項(xiàng)任務(wù)分配一個不同的序號，表示它們執(zhí)行的順序，滿足：如果任務(wù)X依賴任務(wù)Y，則X的序號就要大于Y的序號;如果兩個任務(wù)之間沒有依賴關(guān)系，則對它們的序號關(guān)系沒有要求。從數(shù)學(xué)上看，原來所有任務(wù)間的依賴關(guān)系確定了一個“偏序”，即并非任意兩個任務(wù)都必須“有先后”（稱為“可比”）。調(diào)度就是要在此基礎(chǔ)上生成一個“全序”，即任何兩個任務(wù)皆“可比”，對任意兩個原來就“可比”的任務(wù)，新關(guān)系與原關(guān)系保持一致。換句話說，如果按照這個序號串行執(zhí)行，一定滿足原來要求的依賴關(guān)系。這個問題被稱為“拓?fù)渑判颉眴栴}。讀者應(yīng)該注意到，如果只要解決拓?fù)渑判騿栴}，我們并不需要考慮上述例子中每項(xiàng)子任務(wù)的耗時。

我們可以建立一個有向圖模型。圖中每個節(jié)點(diǎn)表示一個任務(wù)，節(jié)點(diǎn)X和Y之間存在從X到Y(jié)的有向邊（X→Y）當(dāng)且僅當(dāng)對應(yīng)的任務(wù)X直接依賴于任務(wù)Y。上述例子的圖模型如下頁圖1所示。圖中節(jié)點(diǎn)名稱采用表1中的任務(wù)名稱。我們暫時不考慮任務(wù)的耗時。

在這個模型上解決拓?fù)渑判騿栴}的思路非常簡單。我們要給每個節(jié)點(diǎn)分配一個序號，這需要遍歷所有節(jié)點(diǎn)。根據(jù)問題要求，如果任務(wù)X依賴任務(wù)Y（無論是直接還是間接），分配給節(jié)點(diǎn)X的序號必須大于Y的序號。在圖模型中存在的任意一個簡單有向通路v1，v2，…，vk表明任務(wù)i-1依賴任務(wù)i（1

圖節(jié)點(diǎn)遍歷常用算法有兩種：深度優(yōu)先與廣度優(yōu)先。我們在本系列文章中前面討論走迷宮算法時介紹過深度優(yōu)先算法（DFS）。它的基本步驟如下（這里假設(shè)從起始點(diǎn)一定可通達(dá)所有節(jié)點(diǎn)）：①選擇一個起始點(diǎn)，并將其作為第一個“當(dāng)前節(jié)點(diǎn)”，設(shè)置狀態(tài)為“已訪問”。②如果當(dāng)前節(jié)點(diǎn)所有的相鄰節(jié)點(diǎn)都是“已訪問”狀態(tài)，結(jié)束從當(dāng)前節(jié)點(diǎn)開始的遍歷子過程，退出（回溯）。如果當(dāng)前節(jié)點(diǎn)就是起始點(diǎn)，則整個遍歷完成。③取當(dāng)前節(jié)點(diǎn)相鄰節(jié)點(diǎn)中的一個尚未訪問過的節(jié)點(diǎn)w作為新的“當(dāng)前節(jié)點(diǎn)”，設(shè)置狀態(tài)為“已訪問”，從w開始遞歸執(zhí)行本過程（即上述第2步）。

在圖1中從L開始執(zhí)行深度優(yōu)先搜索過程，可能產(chǎn)生的一個訪問序列如下：L，K，H，F(xiàn)，C，A（A，回溯）（C，回溯）（F，回溯）（H），E（E，回溯）（H），B（B，回溯）（H，回溯）（K），G，D（D，回溯）（G，回溯）（K回溯）（L），J（J回溯）（L，結(jié)束）。它對應(yīng)表2中的“訪問序”。具體的訪問序列與當(dāng)前節(jié)點(diǎn)的所有相鄰節(jié)點(diǎn)被訪問的次序有關(guān)（由算法實(shí)現(xiàn)決定，即上述算法第3步節(jié)點(diǎn)w的選?。?。這對后面生成的全序有影響，但對滿足問題的約束條件沒有影響。

下面來看“拓?fù)湫颉钡拇_定。在深度優(yōu)先搜索過程中，任一節(jié)點(diǎn)在回溯后就再也不會被訪問了，也就是它所依賴的節(jié)點(diǎn)都已經(jīng)訪問過了，因此如果我們在其即將回溯前給它分配拓?fù)湫蛱?，且號碼值從1開始依次加1，則上述過程給出的拓?fù)湫蛱柵c任務(wù)名稱的對應(yīng)關(guān)系如表2中的第三行所示。讀者容易驗(yàn)證這個次序滿足表1中的任務(wù)依賴要求，即按照這個序號，先做“1”（A），后做“2”（C），……，最后做“11”（L），就不會出現(xiàn)當(dāng)要做一件事的時候，它前面還有該做沒做的事情。

對前述深度優(yōu)先算法稍加修改（在回溯前給節(jié)點(diǎn)編號），即可得一個拓?fù)渑判蛩惴ǎ糇髯x者練習(xí)）。其中有兩點(diǎn)值得注意：第一，起始節(jié)點(diǎn)（將最后編號）應(yīng)該是不被任何其他節(jié)點(diǎn)依賴的，即要選入度為0的節(jié)點(diǎn);第二，對于任意的依賴關(guān)系輸入，拓?fù)渑判騿栴}未必都有解。設(shè)想一下，有兩個任務(wù)X和Y，X依賴于Y，但Y也依賴于X（可能是間接的），這就形成了所謂相互依賴的“死循環(huán)”，無論怎么安排都沒法滿足它們。這種狀況在圖1所示的圖模型中體現(xiàn)為一條有向回路。在算法中判斷這種情況的標(biāo)準(zhǔn)方法是用3個狀態(tài)（通常形象地用顏色白、灰、黑標(biāo)記）來表征一個節(jié)點(diǎn)在深度優(yōu)先搜索過程中不同時間段上的情況。White表示“尚未發(fā)現(xiàn)”，grey表示“已發(fā)現(xiàn)但還未關(guān)閉”（在進(jìn)入DFS時設(shè)置），black表示“已關(guān)閉”（即已回溯，在離開DFS時設(shè)置）。在第2步，發(fā)現(xiàn)了一個灰色節(jié)點(diǎn)，就意味著圖中存在回路（讀者可想想其中的道理）。

這個算法只是在深度優(yōu)先搜索過程中增加了常數(shù)次簡單賦值操作，所以其時間代價與深度優(yōu)先搜索算法一樣，為O（m+n），其中m與n分別是輸入圖的邊數(shù)與節(jié)點(diǎn)數(shù)。

對于不熟悉深度優(yōu)先等遞歸性質(zhì)算法的讀者，還可以有一個概念上較簡單，但時間代價較大一些的拓?fù)渑判蛩惴āＦ湟c(diǎn)是：不斷刪去有向圖中出度為0的節(jié)點(diǎn)。刪除的順序就是節(jié)點(diǎn)的拓?fù)湫颉＿@種思路的程序?qū)崿F(xiàn)十分容易，直接操作鄰接矩陣就可以，不用遞歸，對初學(xué)者有一定教益。

● 執(zhí)行時間與依賴關(guān)系共同約束下的任務(wù)調(diào)度

現(xiàn)在我們來考慮任務(wù)執(zhí)行時間的影響。將表1給出的例子畫出反向依賴圖，并將每個子任務(wù)的耗時標(biāo)注在指向相應(yīng)節(jié)點(diǎn)的邊上，我們就得到圖2。此時，邊A→B的含義是“B必須在A做完了后才可以開始”（即B依賴于A），上面的“30”表示B需要耗時30分鐘。顯然，邊上的數(shù)據(jù)標(biāo)在箭頭末端的節(jié)點(diǎn)上也是可以的。

這樣一個任務(wù)關(guān)系圖中顯示了在人力允許的情況下可以并行執(zhí)行的多條路徑，如在任務(wù)A完成后，可以同時執(zhí)行{任務(wù)B}以及{任務(wù)C，任務(wù)E}，甚至還能同時執(zhí)行{任務(wù)D，任務(wù)G}（大括號內(nèi)的任務(wù)串行執(zhí)行）。圖中粗線顯示，到整個項(xiàng)目執(zhí)行完成最長的一條路徑是A→C→F→H→J→L（圖中用粗線表示）。這條路徑耗時130分鐘。如果不能壓縮這條路上的耗時，其他任務(wù)即使壓縮了耗時也不能將整個項(xiàng)目的完成時間提前。因此，這條路徑稱為“關(guān)鍵路徑”，關(guān)鍵路徑中體現(xiàn)的依賴關(guān)系稱為“關(guān)鍵依賴”。在這個例子中，單項(xiàng)任務(wù)耗時最多的是包餃子（G，80分鐘）。增加一些人手可以將其耗時降下來。但它并不在關(guān)鍵路徑上，因此包餃子提前完成對于整個項(xiàng)目縮短時間并沒有任何意義，只是增加了一些閑著等待的人。

此時，調(diào)度的追求是識別關(guān)鍵路徑，從而得知完成整個工作所需時間的下界。在任務(wù)管理中，找出關(guān)鍵路徑，并通過有針對性地加大資源投入、改進(jìn)技術(shù)等手段壓縮該路徑上的耗時，是提高辦事效率的重要方法。

基于前述深度優(yōu)先搜索算法，適當(dāng)記錄中間結(jié)果，就可以解決這種關(guān)鍵路徑問題。它包括兩個方面，一是關(guān)鍵路徑的長度（時間），二是路徑本身（經(jīng)過的節(jié)點(diǎn)）。在這個意義上，和上一期討論的“投資組合問題”有共通之處，即不僅要得到一個目標(biāo)量值，還要得到構(gòu)成該目標(biāo)量值的具體實(shí)現(xiàn)。這也是計(jì)算機(jī)問題求解中的一種相當(dāng)廣泛的要求，策略大都是通過在追求目標(biāo)量值的過程中記錄某些中間結(jié)果，然后通過它們反演出具體實(shí)現(xiàn)方案。下面來看怎么解決這個問題。

這里的關(guān)鍵是要認(rèn)識到，如果任務(wù)A直接依賴任務(wù)B，則A的最早“開始時間”不可能早于B的最早“完成時間”。進(jìn)而，若A依賴多個任務(wù)，則A的“開始時間”不可能早于它們“完成時間”的最晚者。而一個節(jié)點(diǎn)的完成時間等于它的開始時間加上它的耗時。

這樣，參照圖2，如果我們確定了每個節(jié)點(diǎn)的最早“完成時間”，對應(yīng)最后一個任務(wù)（L）的，就是關(guān)鍵路徑的長度。而在L所依賴的節(jié)點(diǎn)中，誰的完成時間最晚，也就是關(guān)鍵路徑上的前一個節(jié)點(diǎn)。如此繼續(xù)，直到起始節(jié)點(diǎn)A，就反演出了關(guān)鍵路徑的構(gòu)成。鑒于實(shí)現(xiàn)這種思路的程序不長，下面我們將基于圖3中的可執(zhí)行Python函數(shù)予以解釋。

其中用到的幾個數(shù)據(jù)結(jié)構(gòu)是——①neighbor：線性表向量，初化為每個節(jié)點(diǎn)的出向鄰居，基于圖1（而不是圖2）的方向性;②delay：向量，輸入數(shù)據(jù)，記錄每個節(jié)點(diǎn)的耗時;③visited：向量，記錄節(jié)點(diǎn)在深度優(yōu)先過程中是否被訪問過，初始化為全False;④finished_time：向量，記錄節(jié)點(diǎn)的最早完成時間;⑤critical_dependance：向量，記錄關(guān)鍵依賴關(guān)系。

看這段程序，如果沒有行2，8～10，14～17，那就是一個從current_node（當(dāng)前節(jié)點(diǎn)）開始的標(biāo)準(zhǔn)深度優(yōu)先搜索。其中第4行的for語句保證當(dāng)前節(jié)點(diǎn)的每一個依賴關(guān)系（x）都會被考慮到。9～10，14～16行就是我們說的記錄中間數(shù)據(jù)。站在當(dāng)前節(jié)點(diǎn)的角度，把所依賴節(jié)點(diǎn)的完成時間的最大者定為自己的開始時間（my_starting_time），同時也在critical_dependance中記下它。最后再加上自己的耗時，得到自己的完成時間，供依賴自己的節(jié)點(diǎn)后續(xù)參考。

這其中有兩點(diǎn)值得注意，一是為什么要考慮當(dāng)前節(jié)點(diǎn)的所有依賴節(jié)點(diǎn)，而不僅是剛看到的white節(jié)點(diǎn)？這是因?yàn)榍懊嬲f的，當(dāng)前節(jié)點(diǎn)的最早開始時間不得早于所依賴節(jié)點(diǎn)的最晚結(jié)束時間，與訪問順序無關(guān)。二是在最后的critical_dependence中，不僅記錄了從開始任務(wù)到結(jié)束任務(wù)的關(guān)鍵路徑信息，還記錄了從開始任務(wù)到任何任務(wù)的關(guān)鍵路徑信息?；趫D3的程序，運(yùn)行前面的例子，結(jié)果如表3所示。

從中，我們可以反演出整個任務(wù)圖的關(guān)鍵路徑：A→C→F→H→J→L。

從上述討論中能看出，這個算法只是根據(jù)特定問題的需要，在深度優(yōu)先搜索算法中加入適當(dāng)代碼保留一些中間數(shù)據(jù)，就實(shí)現(xiàn)了我們期望的問題求解目標(biāo)。這樣，我們就能夠?qū)FS過程當(dāng)作一個“算法框架”，可以用它拓展出針對不同問題的許多算法。

關(guān)于關(guān)鍵路徑問題的求解，最后需要提請讀者注意的是，它所面對的圖不僅應(yīng)該是有一個有向無環(huán)圖，還應(yīng)該是有唯一“起始節(jié)點(diǎn)”（入度為0）和唯一“結(jié)束節(jié)點(diǎn)”（出度為0）。每個節(jié)點(diǎn)都可達(dá)結(jié)束節(jié)點(diǎn)，都可被起始節(jié)點(diǎn)到達(dá)。為此，在實(shí)際應(yīng)用中有時需要添加虛擬的起始節(jié)點(diǎn)和結(jié)束節(jié)點(diǎn)，算法方可正確運(yùn)行。

● 負(fù)載均衡調(diào)度問題

本文開始就提到調(diào)度問題最大的應(yīng)用背景應(yīng)該是生產(chǎn)活動，具體應(yīng)用與限制條件的不同發(fā)展出了大量的調(diào)度問題，與我們前面的拓?fù)渑判騿栴}有很大差別，生產(chǎn)實(shí)踐中產(chǎn)生的調(diào)度問題大多屬于“難”問題。對于計(jì)算機(jī)科學(xué)家而言，“難”問題通常指這樣的問題：問題輸入規(guī)模增加到足夠大時，我們傾向于相信全世界的計(jì)算資源都不足以支撐我們獲得問題的最優(yōu)解。但調(diào)度問題的解往往涉及巨大的經(jīng)濟(jì)效益，這就促使人們設(shè)法尋求可接受的解決途徑。放棄對最優(yōu)解的追求，轉(zhuǎn)而滿足于質(zhì)量有一定保證的近似解就是目前遵循的最重要的途徑之一。令人驚喜的是，這往往會帶來非常簡單但可以滿足實(shí)踐需要的算法。下面用一個最容易表述的例子來讓讀者形成一些初步的認(rèn)識。

考慮需要在m臺完全相同的機(jī)器上執(zhí)行n項(xiàng)沒有依賴關(guān)系的任務(wù)，pi（i=1，2，…，n）為任務(wù)i的耗時，在任何一臺機(jī)器上執(zhí)行都一樣。假設(shè)每項(xiàng)任務(wù)不可分割，如何將n項(xiàng)任務(wù)分配給m臺機(jī)器，使得項(xiàng)目總執(zhí)行時間最短？這個問題稱為“（多臺相同機(jī)器上的）工期問題”。稍微想一想，不難認(rèn)識到這里就是要追求讓n個任務(wù)盡量“均勻地”（以時間為衡量）在m臺機(jī)器上分配，而最優(yōu)解不可能小于S=∑ipi/m。

顯然，如果機(jī)器數(shù)m大于等于任務(wù)數(shù)n，因?yàn)槿蝿?wù)不可分割，則最大任務(wù)耗時就是整個項(xiàng)目最小完成時間。我們下面約定n>m?？梢宰C明工期問題是上面所說的“難”問題。按照最直觀的貪心策略我們就可以找到一個結(jié)果“可控”的近似算法。

一個自然的想法是：先把m個最大的任務(wù)安排給每臺機(jī)器，剩下來的再逐個往不同的機(jī)器上“塞”?！叭钡脑瓌t很簡單，當(dāng)前哪臺機(jī)器負(fù)載最小（即完成已分配任務(wù)所需的時間最短）就給它加任務(wù)。為此，我們先對所有任務(wù)按時間降序排序[時間復(fù)雜度為O（nlogn）]，然后一一安排。整個算法過程如圖4所示。其中的關(guān)鍵數(shù)據(jù)包括：①一組集合Ti，1≤i≤m，Ti的元素為已分配給第i臺機(jī)器的任務(wù)下標(biāo)，算法終止時輸出Ti;②數(shù)組Time：Time[i]的值為第i臺機(jī)器當(dāng)前總負(fù)載，算法終止時，Time[i]（i=1，2，…，m）的最大值即為算法計(jì)算的結(jié)果。

強(qiáng)烈建議讀者用自己熟悉的語言實(shí)現(xiàn)這個算法，特別是用盡可能簡單的方法實(shí)現(xiàn)其中“找出負(fù)載最小的機(jī)器”。作為一個例子，假設(shè)n=10，m=3，任務(wù)的負(fù)載為80，40，40，30，30，20，20，10，10，5。按照算法，運(yùn)行結(jié)果如表4所示。

前面我們說這個近似算法是“可控”的，這是什么意思呢？我們希望確定算法的輸出與最優(yōu)解差距有多大？這似乎提出一個“悖論”：如果我們知道最優(yōu)解，根本不必費(fèi)心去找近似解;但如果不知道最優(yōu)解，怎么能知道差距有多大呢？奧妙在于利用數(shù)學(xué)知識與算法本身的特性，我們可以試圖估計(jì)出差距的“上界”。這個問題是求最小值問題，因此算法輸出的近似解一定大于最優(yōu)解。如果能確定“最壞情況下”大多少，使用者心中就“有底了”。

這里的關(guān)鍵在于能否估計(jì)最優(yōu)解的值的“下界”，即最優(yōu)解至少得多大。前面已經(jīng)提到，最優(yōu)解不可能小于均值S=∑ipi/m，即它就是一個下界。

現(xiàn)在來考慮算法本身的行為。假設(shè)整個項(xiàng)目中最遲完成的任務(wù)下標(biāo)為k，則安排任務(wù)k時的場景示意如圖5所示。

假定任務(wù)k被分配給機(jī)器l，則當(dāng)時機(jī)器l是負(fù)載最小的，因此Time[l]一定不大于前面k-1個已安排任務(wù)的平均耗時。而這只是所有任務(wù)中的一部分，所以一定不大于∑ipi/m，因此也不大于最優(yōu)解?？紤]到pk是最小的負(fù)載，因此不可能大于平均值（最優(yōu)解的下界），算法輸出的值，就是這兩項(xiàng)的和，一定不大于最優(yōu)解的2倍。在表4所示的例子中，總時間為80+40+40+30+30+20+20+10+10+5=285，因而在3臺機(jī)器并行條件下，最短時間不會少于285/3=95。剛才的結(jié)果是max（100，95，90）=100，相當(dāng)不錯了。

這種保證得到的解不大于最優(yōu)解2倍的算法也稱為2-近似算法。至于實(shí)際應(yīng)用場景能否容忍這樣的誤差就得由用戶自己決定了。采用更復(fù)雜的技術(shù)可以進(jìn)一步降低工期問題算法的誤差，甚至可以做到“任意小”（當(dāng)然效率成本會迅速提高）。

參考文獻(xiàn)：

[1]Sara Baase.計(jì)算機(jī)算法——設(shè)計(jì)與分析導(dǎo)論（第3版）[M].北京：高等教育出版社，2001.

[2]Juraj Hromkovic.Algorithmics for Hard Problems（2nd ed）[M].Berlin：Springer-Verlag， 2004.

[3]陳道蓄.迷宮問題中的算法[J].中小學(xué)教材教學(xué)，2019（10）：76-80.

注：作者系南京大學(xué)軟件學(xué)院原院長，計(jì)算機(jī)系原系主任。