TW200816063A - Matching method for interdependent scheduling - Google Patents

Description

200816063 七、指定代表圖： (一） 本案指定代表圖為：第（二）圖。 (二） 本代表圖之元件符號簡單說明： S21〜S29 :流程步驟。 八、 本案若有化學式時，請揭示最能顯示發明特徵的化學 式: 九、 發明說明： 【發明所屬之技術領域】 本發明係提供一種相依排程之派工方法，特別是關於 由共識因子獲得新世代母體，由求解出演化後之排程序 列，以縮短任務排程完成的時程。 【先前技術】 隨著電子資訊科技的快速發展，各種電子資訊產品如 個人電腦、筆記型電腦、伺服器或工作站等裝置或系統， 其功能不但愈來愈強大，相較於以往，其價格亦更加的平 易近人。因此，無論是擁有成千上萬員工的大企業或是其 他員工人數較少之中小業，均相繼將電子資訊裝置或系統 200816063 t其企業之營運及管理流程中，其中可包括諸如透過電 =料研發、電子文件或樓案之傳送與簽核、企举資 敫，之辅助製造、自動化之產品測試以:企 管理等。透過上述之電子資訊裝置或系統 及其理之：ί:供企業更有效率的執行設計、生產、製造 及官理之作業流程。 h.、任務之間具有相依關係（dependent aticnshxp), ,Ma M f ^ # ^ ## ^ 田以（irected acyclic graph，DAG) 〇 旦右H閱第Γ圖’係為任務排程之有向非循環圖。圖中， ::㈣:=(task)’任務間有㈣ 二二％ “要任務排程6與任務排程^都執行完畢， 方此執仃’當任務排程6需要任務排程6執行 方处 執行^當任務排程4要任務排^執行完畢，方能執^ 第二、任務的執行具有共用資源的特性，即此 戶 源是有限數量的機器，每個任務都可用任 P而上述任務排程問題可發生在各種領域，如研發專案 排私、生產系統排程、計算機系統排程。 x ^ =,排程序列的演化-般是以基因演算法，利用交 「二子、(c聰over operator)和突變因子一ati〇n operator)來產生新染色體的排程序列。 孜 限制的相依性，交配因子和突變因子可能產生兩^問題： 6 200816063 (1)易產生不合理解；（2)產生品質不佳的解。 因此’為解決上述所提出的問題。本發明人基於多年 k事研究與諸多貫務經驗，經多方研究設計與專題探討， 遂於本發明提出一種相依排程之派工方法以作為前述期望 一實現方式與依據。 ' 【發明内容】 有鐘於上述課題，本發明之目的為提供—種相依者m 求寺別是關於由共識因子獲得新世代母體，E 化後之排程序列，簡短任務排程完成的時程 法，提二土f目的’依本發明之相依排程之派工; 個處=備=具有相依性的複數個㈣ 對產生一處理時：，排私及處理設備的酉 及傳輪時間產生你敦姑 專輸蚪間，再由處理時間矩㈣ 任務排程之—排除之各別優先值，依據優先值排歹^ 生多個該排程序歹^，歹卜且由處理時間矩陣及傳輸時間J 樣自母體之排程]^成母體，I續，由共識因子將拍 藉由共識因子重德的斜仃’貝化，以產生新世代母體，同樣 直到新產生_、世新母產生㈣世代母體抽樣進行演 即停止演化，最後，體相演化服或演化代數， 識固子使得具有:::月之相依排程之派工方法中的共 組的任務排程經此產生品質優排程序 200816063 列’以縮短任務排程完成的時程。 茲為使貴審查委員對本發明之枯# # 功效有更進-步之瞭解與認識，下=特徵及所達成之 及相關圖式以為齡之用，並叫=供較佳之實施例 如後。 之呢明文字配合說明 【實施方式】 為讓本發明之上述目的、特徵 下文依本發明之相依排程之派卫方;^能更明顯易懂， 配合所附相關式’作詳細說明 =μ實施例’並 以相同的元件符號加以說明。’’、中相同的元件將 請參閱第二圖，係為本發明松 流程圖。此方法之流程步驟如後：&排程之派工方法之 步驟S21 :提供複數個任務排 任務排程具有相依性； 壬，邠份或全部前述 步驟S22 :提供複數個處理設備，處理前述任務排程； 理時= 排程及處理設備的配對產生-處 拂程由處理時間矩陣及傳輸時間’產 列^ S25 : _優先_列前述任務排程之-排程序 ’由處理時間_及傳輪時間產生乡侧轉列，以形 200816063 成一母體； 、雜Y驟S26 :經由母體產生至少一共識因子，將抽樣自 母脰之排程序列進行演化，以產生一新世代母體； ^驟S27 :經由新世代母體產生共識因子，對新產生 的新世代母體抽樣進行演化，並重複演化，直到新產生的 新世代母體達到一演化門檻或一演化代數，即停止演化； 步驟S28:由所獲得最終的新世代母體求解出一演化 後之排程序列；以及 /、 步驟S29 ··將所獲得的演化後之排程序列投入於任務 排程的執行。 上述之處理設備一般可為電腦設備或生產設備等，而 處理設備可具有不同的處理能力，傳輸時間為具相依性的 任務排程的中間產物於處理設備間的傳遞所花費的時間， 且共識因子至少包含有一經演化後該排程序列中固定不變 的優先關係、一經演化後談排程序列中產生新的優先關係 或一共識因子權重等。 請參閱第三圖，係為本發明之任務排程及處理設備配 對之處理時間矩陣。此例，提供三個具有不同的處理能力 的處理設備mi、m2及脱，當第一圖中任兩個任務排程指派 給同一個處理設備時，傳輸成本設定為0，代表並不需要 傳輸資料，且設定任兩個處理設備的頻寬使任兩個任務排 程之間的傳輸成本相等於其資料傳輸量，指派給不同處理 設備不會影響傳輸時間。因為是具有不同的處理能力的處 200816063

理設備，同一任務排程在不同處理設備的期望執行時間 (expected execution time)會不同；再者任務排程不能再 拆解，亦即設每一個任務排程只能指派給一部處理設備執 行。其中，任務排程ti於處理設備mi、in2及脱執行的處理 時間分別為2、3及1 ;任務排程仪於處理設備mi、胞及 ms執行的處理時間分別為3、4及5;任務排程t3於處理設 備m、in2及ms執行的處理時間分別為3、2及2 ;任務排程 t4於處理設備mi、m2及1〇3執行的處理時間分別為3、1及2; 任務排程t5於處理設備mi、m2及ms執行的處理時間分別為 3、3及3，任務排程t6於處理設備mi、in2及ms執行的處理 時間分別為1、2及3。 由處理時間矩陣及傳輸時間，產生任務排程之各別優 先值，首先，產生b-ievei，為每一任務排程到最後一個 任務排程的最長路徑長度，因此每個任務排程的關鍵路徑 被相依性所限制，因此越前面的任務排程所需的路徑越 長，其b-level通常較高。每個任務排程的b-levei ^算 為在各處理設備的平均處理時間加上與最長（1〇n狀紂）的 子任務排程（child task)的b-level和傳輸時間。再者， ^每個任務排程的卜leve卜此可以觸任務排程的最 早開始時間。卜1evel的計算為父任務排程（parent task、 &Γ1和父任務的傳輸時間加上父任務排務的平均處 經上述計算，請參㈣四圖係為本發 派工方法一優弁佶夕而丨± ^ 1欠无值之列表。因此，依據此表產生一妯 列’首先’依據b-level姐中★ + + avei排出匕、匕、心、6、&及七 200816063 參照t-level調整優先序， 優先於以Μ憂先於f 由卜levei中得知順序中& 列為/另5又優先於匕。故，獲得排程序 L2 L5 t3：8L t4。 列中固定不變的優先關係成= 新的優先關係或一共識因子權口 ==程序列中產生

進行演化，以產生新世代母體，同樣I =產Ϊ:新世，達到演化==:停 序列，夢的新世代母體求解出演化後之排程 糾縮短任務排程完成的時程。 變的優先關i識因=為—、_化後該排程序列中固定不 子權重等，請參閱第五圖所顯示本發= 5日 生方去之流程圖，其流程步驟如後： “ 建立i:隹巧’自欲演化之母體隨機抽取多個排程序列， 定之/門=^所抽取個數較料母體半數紐用者所設 S52 · 4异共識集合中所有排程序列各自的優先 =係矩陣，意即產生與排程序列對應之複數個優先關係矩 口步驟S521 :提供一零矩陣及單一個排程序列，依排 王列中任兩個任務排程的先後順序以決定所對應的矩陣 11 200816063 元為0或1 ’以產生前述之優先_矩陣； 步驟S53 .加總所有優先關係矩陣，形成一對偶優先 矩陣； 步驟S54:標準化上述之對偶優先矩陣，其中演化後 為0或1之矩陣tl於演化前即為0或i者，兩任務排程即 固定不變的優先關係，演化後為G或1之矩陣元於演化 前不為0或1者’兩任務排程即為新產生的優先關係；以 及

步驟S55 .依據可插入的任務排程間的對偶優先矩陣 的比例’產生共識因子權重’用以調整排程序列。 不』因子則包括為經演化後該排程序列中固定 係或共顧子權重。 排㈣列中產生新的優先關 綜上所述，本發明之減轉 子嶋有相依性的任務排程經此產生品^， 以縮短任務排程完成的時程。 、炎王 以上所述僅為舉例性，而非卜 本發明之精神與範疇，而對其進行者。任何未用 應包含於後社申請專·圍中。之4效修改或變更， 【圖式簡單說明】 第-圖係為任務排程之有向非循環圖 12 200816063 第二圖係為本發明之相依排程之派工方法之流程圖； 第三圖係為本發明之任務排程及處理設備配對之處理時 間矩陣； 第四圖係為本發明之相依排程之派工方法一優先值之列 表，以及 第五圖係為本發明之共識因子的產生方法之流程圖。 •【主要元件符號說明】 匕、66及6 :任務排程； S21〜S29 :流程步驟； mi、m2及m3 :處理設備；以及 S51〜S55及S521 :流程步驟。 13

Claims (1)

1. 200816063 十 、申請專利範園： 卜一種相依排程之派工方法，至少包含： 具個任務排程，且部份或全部該些任務排程 理設傷，處理該些任務排程; 處理時門:睡力排耘及該些處理設備的配對產生一 处里日守間矩陣及一傳輸時間； 二 =矩陣及該傳輪時間，產生該些任務 二=::二務排程之-排程序 序列，《形成車及轉輪時間產生多個該排程 經由該母體產生至少一丑 之該些排程序列進行演化樣自該母體 經由該新世代母體重新乂產生-新世代你 生的該新世代母體抽樣^些”因子，對新產 新產生的钤如I b 丁，，、化，亚重稷演化，直到 數，即停：化:ΓΓ達到一演她 排以最終的該新世代母體求解出-演化後之 排i:成=化後之排程序列，以縮短該些任務 ^相依排程之派工方 處理設備。 y、電知没備或一生產設備作為該 2 3、 如申請專利範圍第1項所述之相依排程之派工方 法，其中所提供的該處理設備具有不同的處理能力。 4、 如申請專利範圍第1項所述之相依排程之派工方 法，其中所產生的該傳輸時間係為具相依性的該些任 務排程的中間產物於該些處理設備間的傳遞所花費 的時間。 5、 如申請專利範圍第1項所述之相依排程之派工方 法，其中該些共識因子包括為一經演化後該排程序列 中固定不變的優先關係、一經演化後談排程序列中產 生新的優先關係或一共識因子權重。 6、 如申請專利範圍第1項所述之相依排程之派工方 法，其中該些共識因子之形成步驟包含: 自該母體隨機抽取多個該些排程序列，建立一共識 集合； 計算該共識集合中該些排程序列，以產生對應該些 排程序列之複數個優先關係矩陣； 提供一零矩陣及該排程序列，依據該排程序列中任 兩個該任務排程的先後順序以決定所對應的矩陣元 為0或1，以產生該優先關係矩陣； 加總該些優先關係矩陣，形成一對偶優先矩陣；以 及 標準化該對偶優先矩陣，獲得一經演化後該排程序 列中固定不變的優先關係或一經演化後該排程序列 中產生新的優先關係，以及 依據可插入的該些任務排程間之該對偶優先矩陣 .200816063 之比例，產生一共識因子權重； 其中，該些共識因子包括為該經演化後該排程序列 中固定不變的優先關係、該經演化後該排程序列中產 生新的優先關係或該共識因子權重。