姜松巖，廖曉鵑，陳光柱

（成都理工大學 計算機與網絡安全學院，成都 610059）

0 引言

計算機系統中日常要處理的任務越來越復雜，任務量也日益龐大，同時計算機系統本身的處理器數量也在逐步增加，并行計算的重要性也越來越明顯。任務調度問題作為并行計算的關鍵問題一直受到廣泛關注。具有通信延遲的任務圖在一組相同處理器上調度是任務調度問題中的一個經典問題，該問題在經典的α|β|γ［1］描述中可以表示為Pm|pred|Cmax，其中：α域為Pm，表示機器環(huán)境為m個相同機器；β域為pred，表示約束限制中包含優(yōu)先約束；γ域為Cmax，表示優(yōu)化的目標為完工時間。在該問題形式化過程中，通常會以帶有權值的有向無環(huán)圖（Directed Acyclic Graph，DAG）作為任務圖表示在并行系統中要執(zhí)行的程序，程序中的任務以DAG 中的節(jié)點表示，任務間的依賴關系使用DAG 中的邊表示，任務的執(zhí)行時間與任務間的通信延遲分別以節(jié)點和邊的權重表示。Sarkar［2］已經證明，求解并行處理器上帶有通信延遲的任務圖上的最小的完成時間的調度問題是NP（Nondeterministic Polynomial）困難問題。

目前的國內外研究中，解決這類調度問題的方法主要可以分為啟發(fā)式算法和精準算法兩類。由于并行處理器上任務圖調度問題的難度會隨著任務數量的增加呈指數增長［3］，因此通過犧牲一定精度來獲取更快求解速度的啟發(fā)式算法十分受歡迎。例如，張架鵬等［4］通過優(yōu)化蜂群搜索策略來解決同類機調度的問題；翟文正等［5］以任務高度和粒子位置構造優(yōu)先級列表的思想，提出一種面向DAG 任務模型的微粒群優(yōu)化調度算法；馬曉梅等［6］使用改進后的遺傳算法對印刷生產過程中的調度問題進行了抽象并求解；楊小東等［7］提出了一種以帝國競爭算法為基礎，并在同化操作中融入遺傳算法中的雜交算子和變異算子的混合的啟發(fā)式算法來解決車間調度問題。這類啟發(fā)式算法能在較短時間內獲得問題的近似解，從而滿足許多實時應用場景的需求。但不可否認的是，在某些應用場景中，獲得問題的最優(yōu)解有著十分重要的意義，比如在評價啟發(fā)式算法優(yōu)劣時需要利用最優(yōu)解來計算啟發(fā)式算法獲得的近似解的準確率和誤差，以及在某些對于時間精度要求較高的實際問題中，啟發(fā)式算法獲得的近似解往往不能滿足要求，既無法保證解的全局最優(yōu)性，也很難保證求解的質量［3］。

在精準算法的方向上有以下幾種方法較為常見：一種是基于混合整數線性規(guī)劃（Mixed Integer Linear Programming，MILP）的方法，首先將求解問題抽象為MILP 公式，然后使用求解器在公式的解空間內進行搜索，從而獲得最優(yōu)解［8-10］。另一種是基于布爾可滿足性（Boolean Satisfiability，SAT）的方法，將調度問題抽象為命題邏輯公式的可滿足性問題，通過循環(huán)調用SAT 求解器來確定使命題邏輯式可滿足的最優(yōu)解，展示出了SAT 求解器強大的計算能力［11-12］；但由于SAT求解器只能處理由布爾邏輯運算與、或、非連接布爾變量所構成的布爾邏輯公式，在描述調度問題特征和約束條件時的編碼較為困難。目前還有一種常見的方法是基于可滿足性模理論（Satisfiability Modulo Theory，SMT）的方法［13-15］。SMT方法與SAT 方法類似，都是將問題抽象為邏輯公式，通過驗證其可滿足性來搜索最優(yōu)解，兩者主要區(qū)別在于：SAT 方法只能使用布爾集合上的邏輯運算（邏輯與、或、非），而SMT方法支持更豐富的變量類型和運算，能有效處理由變量、量詞、函數、謂詞符號和邏輯運算構成的一階邏輯公式，因此可以更加便捷高效地描述問題特征和約束條件。Malik 等［13］提出了一種SMT 約束公式，利用SMT 求解器對公式的可滿足性進行判斷，通過二分搜索法確定帶延遲的任務圖調度問題的最優(yōu)解，并證實在帶延遲的任務圖最優(yōu)調度上，SMT 方法比MILP 方法更具優(yōu)勢，但該優(yōu)勢僅在處理器數量較少時表現明顯，隨著處理器數量的增加，SMT 和MILP 方法的效率十分接近。這是因為Malik 等［13］引入布爾變量來描述任務和處理器的映射關系，當處理器數量增加時，布爾變量的數目急劇上升，帶來編碼規(guī)模膨脹問題。除此之外，我們注意到，Malik 等［13］提出的SMT 方法在循環(huán)調用求解器進行最優(yōu)解查找時沒有優(yōu)化搜索空間，導致搜索空間中存在無效解，浪費了求解器的計算資源。本文在Malik 等［13］提出的SMT 方法（即原始SMT 方法）的基礎上進行優(yōu)化，提出了改進的SMT方法。與原始SMT 方法相比，改進的SMT 方法主要有以下優(yōu)勢：1）改進的SMT 方法使用整型變量來表達任務節(jié)點與處理器的映射關系，減少了約束編碼所需的變量數目；2）為具有相互獨立關系的任務增加新的約束條件，從而限制任務在處理器上的分配位置，達到優(yōu)化求解器搜索空間的目的。

實驗結果表明，在20 s 超時實驗中，對于超時數量，改進SMT 算法與原始SMT 方法相比減少了11.4%，與兩種MILP方法相比分別減少25.3%和26.5%；對于限時完成的任務求解時間，改進的SMT 算法與原始SMT 方法和MILP 方法的相比，平均求解時間均減少了65%以上，并且隨著處理器數量的增加，改進的SMT 算法的優(yōu)勢會愈加明顯，這提高了SMT方法在求解帶通信延遲的任務圖調度問題上的優(yōu)勢地位。

1 問題模型

任務圖G(V，E)以帶權的有向無環(huán)圖（DAG）表示，其中V={v1，v2，…，vn}是任務節(jié)點的集合；E?V×V是任務節(jié)點之間依賴關系與通信關系的集合。任務間的關系分為獨立關系和依賴關系，獨立關系指兩個任務之間無法連通，依賴關系又分為直接依賴關系和間接依賴關系。直接依賴關系指兩個任務節(jié)點被一條有向邊相連，其中有向邊指向的任務被稱為另一個任務的后置任務，而另一個任務稱為前者的前置任務；間接依賴關系指兩個任務之間可以連通但不直接相連。任務圖中任務節(jié)點出邊的條數稱為該節(jié)點的出度，入邊的條數稱為該節(jié)點的入度。多處理器平臺P={p1，p2，…，pm}由m個互相可以通信的相同處理器組成，其中每個處理器均可以與其他處理相互通信。在任務圖調度過程中，具有依賴關系的一對任務必須按照其先后順序進行調度，任務在執(zhí)行過程中不會發(fā)生搶占，每個任務都可以在任何一個處理器上運行，且只會被安排到唯一的一個處理器上。任務v∈V的執(zhí)行時間表示為t(v)，具有直接依賴關系的任務對(vi，vj) ∈E的通信延遲表示為c(vi，vj)。如果一對具有直接依賴關系的任務被分配到了同一個處理器，則它們可以通過共享本地內存中的數據完成通信，因此不會產生通信延遲；如果它們被分配到了不同的處理器，則需要進行處理器間的通信完成數據傳輸，從而產生通信延遲c(vi，vj)。

在這個問題中，所有的任務運行時間、通信時間以及任務關系和處理數量都是已知的。調度的目標是獲得任務圖G(V，E)在P上的完成時間m(G)的最小值，同時還要獲得在min(m(G))時任務節(jié)點與處理器的映射關系，以及每個任務節(jié)點開始的時間s(v)。

2 改進的SMT方法

SMT 問題指在特定理論下判定一階邏輯公式可滿足性的問題，針對這類問題的判定算法被稱為SMT 求解器。SMT的應用領域廣泛，例如：多核問題、程序缺陷檢測驗證、優(yōu)化問題求解、程序驗證等［16-18］。這些領域中待解決的實際問題都可以建模為約束可滿足問題，SMT 在這類問題的表述和求解上有突出優(yōu)勢。

2.1 方法描述

本文提出一種改進SMT 方法來解決帶通信延遲的任務圖的調度問題。為了刻畫任務與處理器間的映射關系，引入整型變量q(v)（q(v) ∈{1，2，…，m}）表示執(zhí)行任務v的處理器編號，調度目標為獲得任務圖G的最小的完成時間min(m(G))。

SMT 約束公式的定義如下，G+=(V，E+)為任務圖G的傳遞閉包，其中E+包含了任務圖中所有的傳遞關系，t(v)為任務節(jié)點的權重即執(zhí)行時間，c(vi，vj)為邊的權重即通信延遲時間，?表示邏輯運算中的蘊含運算。

C1 所有任務都會被分配在唯一的處理器上。

1 ≤q(v) ≤m；?v∈V

C2 所有入度為0 的任務（沒有前置任務的任務）的開始時間不小于0。

C3 如果兩個任務被分配到不同的處理器上，則后置任務的開始執(zhí)行時間一定不早于前置任務的完成時間加上兩個處理器之間的通信延遲（c(vi，vj)）。

C4 如果兩個任務被分配到相同的處理器上執(zhí)行，則后置任務可以在前置任務完成后立即執(zhí)行。

約束C3 和C4 共同約束了具有直接依賴關系的兩個任務的執(zhí)行順序即在一對具有直接依賴關系的任務中，后置任務必須在前置任務執(zhí)行完成后才能開始執(zhí)行。

C5 如果兩個相互獨立的任務被分配到相同處理器上，則一方需要等待另一方完成后才能開始執(zhí)行。

C6 所有任務都在時間m(G)內執(zhí)行完畢。

上述的約束公式只與任務圖和處理器數量有關，在調度問題的求解過程中不會改變。通過將所有約束條件輸入SMT 求解器（如Z3 求解器）就能判斷對于一個給定的時間m(G)，是否所有的約束條件都能被滿足。如果求解器在計算后輸出一個非空模型，則表明所有任務都能在m(G)時間內完成；如果求解器輸出的模型為空，則表明當前設定的m(G)值過小，不能在該時間內完成所有任務。為了找到使SMT 求解器輸出非空模型的最小m(G)，本文使用二分搜索法在可行解的范圍內進行查找，其中搜索的初始上界(Tup)為假設所有任務在同一個處理上順序執(zhí)行的總時間：

初始下界(Tdown)為在假設所有任務并行執(zhí)行的時間：

為了減少搜索空間，引入一個新約束C7，定義如下：

約束C7 表示對于兩個相互獨立的任務，如果它們的執(zhí)行時間之和大于本次搜索設定的完成時間m(G)，則這兩個任務必須分配在不同的處理器，否則SMT 求解器輸出的模型必定為空。在二分搜索的過程中，如果某次求解的模型結果不為空（即模型為可滿足的），則在之后的搜索過程中保留約束C7；如果某次求解的模型結果為空（即不可滿足），則刪除約束C7，不會影響之后的搜索過程。

二分搜索的算法流程如下，其中Assert（）函數用于獲得SMT 約束集合，以任務圖為輸入，返回根據SMT 約束公式C1～C7 生成的約束集合；CallSMTSolver（）函數用于調用SMT求解器，以約束集合為輸入，返回求解器的求解模型，如果輸出的模型非空，表示輸入求解器的所有約束條件都是可滿足的，否則，表示不存在滿足所有約束條件的模型；add（）與delete（）函數分別用于向約束集中添加和刪除約束。

在上述算法中，首先將任務圖的信息進行編碼作為約束添加到求解器中，之后根據搜索的上下界確定中值，并根據本次搜索的中值添加約束C7。此后對求解器進行求解，如果求解的結果為可滿足，則繼續(xù)判斷是否搜索結束，如果沒有結束，則修改搜索上界為中值；如果求解結果為不可滿足，則更新下界為中值。同時由于C7 只有在模型可滿足時才可以保證成立，因此要將此次添加的C7 刪除。

通過上述的二分搜索的過程就可以獲得m(G)的最小值與取得最小值時的調度模型，m(G)的最小值為Tup=Tdown時的值。

為了更加直觀地展示改進SMT 方法，本文以圖1 所示的任務圖為例，展示如何利用改進SMT 方法求解在兩個處理器上的任務調度問題。

圖1 任務圖示例Fig.1 Task graph example

對于圖1 所示任務圖在兩個處理器上的調度問題，使用本文所提出的SMT 公式描述結果如下：

將上述約束添加到SMT 求解器中之后將進行二分求解。二分求解的具體過程如表1 所示，具體過程如下：

表1 任務圖的二分求解流程Tab.1 Binary solution process of task graph

第1 輪次中，Tup=16，Tdown=9，Tmid=12，向求解器添加約束m(G)=12，因為t(v2)+t(v3)=13 ＞Tmid，向求解器中添加約束q(v2) ≠q(v3)。求解得到結果為模型可滿足，將Tup修改為12 并將約束m(G)=12 刪除后繼續(xù)下一次求解。

第2 輪次中，Tup=12，Tdown=9，Tmid=10，向模型添加約束m(G)=10，因為t(v2)+t(v3)=13 ＞Tmid，向模型中添加約束q(v2) ≠q(v3)。對模型進行求解得到結果為模型不可滿足，將Tdown修改為11 并將約束m(G)=10 與本次求解中添加的q(v2) ≠q(v3)刪除，繼續(xù)下一次求解。

第3 輪次中，Tup=12，Tdown=11，Tmid=11，向模型添加約束m(G)=11，因為t(v2)+t(v3)=13 ＞Tmid，向模型中添加約束q(v2) ≠q(v3)。求解模型得到的結果為模型不可滿足，將Tdown修改為12 并將約束m(G)=11 與本次求解中添加的q(v2) ≠q(v3)刪除，繼續(xù)下一次求解。

第4 輪次中，Tup=12，Tdown=12，Tmid=12，向模型添加約束m(G)=12，因為t(v2)+t(v3)=13 ＞Tmid，向模型中添加約束q(v2) ≠q(v3)。進行求解得到結果為模型可滿足，此時Tup=Tdown，二分搜索結束，獲得最小的任務完成時間為12。該任務圖的最優(yōu)的調度通過本次求解結果模型中變量q(v)與s(v)的值獲得。

2.2 理論分析

本文提出的SMT 方法與原始SMT 方法相比主要作出了以下的改進：

1）原始SMT 中使用一組布爾型變量b(v，p)作為決策變量，b(v，p)=1 表示任務(v)由處理器(p)執(zhí)行，b(v，p)=0 表示任務v不在處理器p上執(zhí)行。顯然，當處理器數目為m時，每個任務需要m個布爾變量來表達該任務和處理器的映射關系。改進的SMT 方法使用整型變量q(v)來表達這一映射關系，顯著減少了變量的數量。與此同時，在表達一組符合條件的任務的C3、C4、C5 時原始SMT 因為使用布爾變量的原因表達C3 需要m× (m-1)條約束，表達C4 與C5 需要m條約束。改進的SMT 方法因為使用整型變量，因此在表達C3、C4、C5 時都只需要1 條約束，顯著減少了約束數量。

2）與原始SMT 方法相比，改進的SMT 方法在二分搜索過程中增加了一個新約束C7，C7 通過比較兩個相互獨立的任務執(zhí)行時間和與m(G)的關系，對相互獨立的任務的分配情況進行約束，將待搜索空間中的無效解去除，從而達到減少求解器搜索空間、提高求解效率的目的。

3 實驗與結果分析

本章將使用Malik 等［13］提出的原始SMT 方法以及Venugopalan 等［19］提出的兩種MILP 方法（MILP-BASIC 方法和MILP-RELAXED 方法）作為對照與本文提出的SMT 方法進行比較。實驗使用的SMT 方法的求解器為4.8.10 版本的Z3［20］，使用的MILP 方法的求解器為9.1.1 版本的Gurobi［21］求解器。所有實驗均在具有2 GB 內存的Ubuntu 64 位系統的虛擬機中進行。為了消除兩種求解器對于多CPU 資源利用效率不同的影響，虛擬機設定為單CPU。

3.1 數據集

本節(jié)實驗中使用到的527 幅任務圖，均為加權的有向無環(huán)圖，這些任務圖全部來自于文獻［13］中所使用過的數據集，這些任務圖的結構包含有：Independent、ForkJoin、Pipeline、SeriesParale、Random 等10 種結構，具體結構分布情況如表2 所示。這些任務圖中包含10 任務、21 任務、30 任務三種不同任務數量任務圖。本節(jié)實驗將這527 幅任務圖分別設定在2、4、8、16 處理器上進行調度，即每種方法將會得到527 × 4=2 108 個運行結果。

表2 任務圖結構分布情況Tab.2 Distribution of task graph structure

3.2 MILP方法對比

混合整數線性規(guī)劃（MILP）是解決組合優(yōu)化問題中常用的方法。為了更為廣泛評價所提改進SMT 方法的性能，將使用了MILP 的方法與本文方法進行比較。文獻［19］和文獻［13］中總共涉及6 種不同的MILP 方法，其中有三種通過去除自反解來減少求解時間的方法，在文獻［13］中已經被證明在求解時間方面整體效果更差，因此在另外效果較好的三種方法中，本文選取了其中比較有代表性的兩種方法（MILPBASIC 方法［19］和MILP-RELAXED 方法［19］）與改進SMT 方 法進行比較。

MILP 方法的求解過程主要如下：首先將調度問題抽象為MILP 公式；然后，將根據問題抽象出的MILP 公式添加到相應的求解器中；最后，使用求解器求解。與SMT 方法的求解器不同，使用MILP 的求解器Gurobi 能自動求解Min-Max問題，因此不需要二分搜索的過程就可以求出最優(yōu)解。

3.3 結果與分析

首先對四種方法在20 s 超時時間內能成功求解的任務圖數量進行比較。如果任務圖在某個數量的處理器上能夠完成求解過程則稱這幅任務圖在某個數量處理器上限時完成。527 張圖在4 種處理器數量的設定下20 s 限時完成任務圖數量如表3 所示。

表3 20 s超時時間內限時完成任務圖數量對比Tab.3 Comparison of number of task graphs completed within 20 seconds timeout

通過表3 中限時完成數量的對比可以看出，改進后的SMT 方法限時完成的數量明顯多于另外三種方法，即改進后的SMT 在20 s 超時時間的限定下可以獲得更多任務圖的最優(yōu)解。

在統計并對比了各方法限時數量的基礎上，對四種方法在限時20 s 內完成的任務的求解時間的分布進行統計，結果如圖2 所示。橫坐標表示完成任務的時間區(qū)間，縱坐標表示在該區(qū)間時間內完成任務的數量。

圖2 限時完成任務求解時間分布Fig.2 Time distribution of task graphs completed within time limit

通過圖2 可以看出，改進SMT 方法所需的求解時間分布整體比其他三種方法靠前。例如，在求解時間不超過0.5 s的區(qū)間內，改進SMT 方法成功求解超過1 000 幅任務圖，而兩種MILP 方法能求解的任務圖數量不超過800，原始SMT 方法的求解數量最少，約500 幅任務圖。這表明改進SMT 方法在簡單問題上所需要的求解時間更少。另一方面，在超過10 s 的時間區(qū)間內，改進SMT 方法完成的任務圖數量較另三種方法明顯更少。這表明，在求解相對復雜的任務圖時，改進SMT 方法與另外三種方法相比更具優(yōu)勢。

表4 是四種方法在超時時間20 s 內完成任務圖的平均求解時間，每種方法的平均求解時間計算公式為：Tavg=Ttotal/N，其中Ttotal為某方法在限時20 s 內完成任務圖的求解時間的總和，N為該方法在限時完成的任務圖數量。從表4可以看出，改進的SMT 方法在超時時間內完成的任務數量最多，因此在統計平均求解時間時改進的SMT 方法中包含了更多相對不易求解的復雜的任務圖的運行時間。盡管如此，改進的SMT 方法在平均求解時間上仍具有巨大優(yōu)勢，與原始SMT 方法相比平均求解時間減少了65.9%，與MILP-BASIC方法相比減少了69.2%，與MILP-RELAXED 方法相比減少了69.1%。這表明在平均求解時間上改進的SMT 方法與另外三種方法相比具有極大的優(yōu)勢。

表4 20 s超時時間內完成任務的平均求解時間 單位：sTab.4 Average solving time of task graphs completed within 20 seconds timeout unit：s

為了更加充分地驗證這幾種方法在數據集上的表現，將超時時間擴大到了1 min 再次進行了實驗，獲得了20 s 超時時間相似的結果，具體的限時完成數量與平均求解時間如表5 所示。

表5 1 min超時時間內完成任務的平均求解時間Tab.5 Average solving time of task graphs completed within one minute timeout

由表4 和表5 對比可以看出在擴大限時時限到1 min 之后四種方法的表現基本與20 s 的限時實驗中的表現相似，改進SMT 方法在完成數量與求解時間上均具有一定優(yōu)勢。

圖3 統計了在20 s 超時時間內，每種方法在四種不同處理器數量上的表現，由于在該數據集較大且超時數量較少，為了更加直觀對比隨處理器變化情況這里采用了對比超時任務對數量來評估在不同數量的處理器的表現。

圖3 超時任務數量隨處理器數量變化比較Fig.3 Comparison of number of timeout tasks varying with number of processors

從圖3 可以直觀地看出，隨著處理器數量的增長，所有方法的超時任務圖數量均呈現下降趨勢，說明處理器越多，越容易在規(guī)定時間內獲得最優(yōu)解。這是因為這兩類方法都是使用單純形（simplex）求解器去求解數值方程，隨著處理器數量的增加，單純形中有更多的松弛空間［13］。

圖3 也清晰地反映出隨著處理器數量的增加，改進SMT方法優(yōu)勢愈加明顯。當處理器數量為2 時，改進SMT 的超時任務數量比原始SMT 減少4.02%，比MILP-BASIC 減少了15.66%，比MILP-RELAXED 減少了17.33%；當處理器個數為16 時，改進SMT 方法的超時數量比原始SMT 減少了41.67%，比MILP-BASIC 與MILP-RELAXED 均減少了約54.35%。這一現象表明，隨著處理器數量的增加，改進SMT方法更具優(yōu)勢。這一優(yōu)勢主要來自于對問題模型進行約束編碼過程中變量數量與約束數量的減少。在變量數量方面，改進SMT 方法引入整型變量q(v)來表達任務-處理器映射關系，隨著處理器增加，該變量的取值范圍發(fā)生改變，但是并不會改變此類變量的數量；而原始SMT 方法采用布爾變量b(v，p)作為決策變量來表示是否將任務v調度至處理器p上執(zhí)行，因此對于包含n個任務節(jié)點的任務圖在m個處理器上調度的問題，共需要m×n個布爾型變量才能完成任務，隨著m數值的增加，這一變量的數量也在快速增加。因此，在處理器數目增多時，與兩種MILP 方法相比，原始SMT 方法的性能優(yōu)勢不再明顯，而改進SMT 方法始終能保持求解效率的巨大優(yōu)勢。在約束條件的數量方面，對兩種SMT 方法對問題模型進行編碼過程中的約束數量統計如表6 所示。

表6 兩種SMT方法不同處理器數量時的平均約束數量對比Tab.6 Comparison of average number of constraints of two SMT methods with different numbers of processors

通過表6 可以看出，改進的SMT 方法的約束數量不會隨處理器數量變化而變化，而原始SMT 方法的約束數量會隨處理器數量增長而快速增長。這是因為對于每一對符合要求的任務，改進后的SMT 方法在描述C3、C4 與C5 時都只需要1條約束。原始的SMT 方法中，實現C3 需要m× (m-1)條約束，實現C4 和C5 分別需要m條約束。因此，隨著m數值的增加，相關的約束條件數量也在快速增長，從而導致問題規(guī)模膨脹，造成求解器的搜索空間擴增。

由于本文提出的改進SMT 方法中包含了變量優(yōu)化和添加新約束兩個方面的改進，下面進行消融實驗來確定求解性能優(yōu)化與這兩者的關系。20 s 超時的消融實驗結果如表7 所示。其中，“添加約束”指與原始SMT 方法相比只在二分求解過程添加新約束，“改進變量”指與原始SMT 方法相比只將變量變更為整型，“改進SMT 方法”為兩者皆有。

表7 改進變量與添加約束的有效性對比Tab.7 Comparison of effectiveness of improving variables and adding constraints

從表7 中可以看出本文中針對SMT 方法的兩處改進都是有效的，其中在二分求解過程中添加新約束的改進效果較為一般；而將變量更改為整型所帶來的改進效果比較明顯，這也是改進SMT 方法優(yōu)勢的主要來源，這一結論同時反映在限時完成數量以及平均求解時間兩個方面。

4 結語

本文在研究了帶有通信延遲的任務圖在一組相同處理器上的調度問題?；谇叭说腟MT 的方法設計，本文使用新的決策變量來表達任務節(jié)點與處理器的映射關系，并引入了新的約束公式來描述問題中相互獨立的任務之間的調度約束條件。實驗結果表明，與原始SMT 方法和MILP 方法相比，改進的SMT 方法在限時完成數量和平均完成時間等性能指標上均有顯著優(yōu)勢；隨著處理器數量增長，改進的SMT 方法在求解效率方面的優(yōu)勢更加明顯；但在問題規(guī)模擴大時求解模型規(guī)模仍然會快速膨脹，導致很難在短時間內求得大規(guī)模問題的最優(yōu)解。

未來的研究工作將聚焦于更加符合生產實際條件的智能制造車間調度等問題上，在多約束、多目標的車間調度問題上，SMT 方法的應用尚有待開發(fā)，具有廣闊的研究前景。