[發明專利]一種基于和聲搜索和模擬退火的多處理機任務調度的方法

無效

• 申請號: 201210382650.8
• 申請日: 2012-10-11
• 公開（公告）號: CN102915355A
• 公開（公告）日: 2013-02-06
• 發明（設計）人: 李英明;姜華;劉彥秀
• 申請（專利權）人: 李英明
• 主分類號: G06F17/30
• 分類號: G06F17/30;G06F9/46
• 代理公司: 暫無信息
• 代理人: 暫無信息

1.一種基于和聲搜索和模擬退火的多處理機任務調度的方法，該方法包括以下步驟：?

(1)?初始化HS相關參數、初始溫度T、降溫系數t；

(2)?初始化和聲庫（HM），利用微調概率PAR，使HS算法產生新解Xnew更新HM，找出最優解Xopt；

（3）以最優解對應的任務序列Sopt作為SA算法的初始解x,?并計算相應的評價函數f(x)的值,評價函數為；????????????????????????????????????????????????；

（4）利用模擬退火算法產生新解x’，計算評價函數f（x’）；根據Metropolis準則進行判斷△E＝f（x’）－f（x）；如果△E<0?則接受x’作為新解，否則以概率min（1，exp(-△E/?T_k?)）接受，如果x’優于和聲庫中最優解，則更新和聲庫HM；T_k?為當前的溫度；

（5）以作為退溫函數進行退溫，t為迭代次數，為退溫系數；

（6）重復執行第4步，直到到達最大迭代次數，算法終止。

2.根據權利要求1中只有任務序列參與了模擬退火過程，退火結束后需要把搜索到的最好任務序列轉化成和聲解，使HS繼續運行；該和聲解要保留退火搜索前的和聲解的信息，還要讓任務符合編碼規則，因此設計了一個任務排序到和聲解的轉化的修正算法，該算法是由模擬退火算法對和聲庫產生的新解進行局部搜索得到一個新解X及相應的任務序列；然后從X內的變量從小到大進行排序，存到另一個數組中tp中，如果數組tp中有重復變量，存到rt中，每個重復變量只存一次，順序檢查各變量，若當前變量在rt中，則將該變量減0.01，最后按公式x[i]=tp[i]循環更新x各變量的值。