[發明專利]基于自適應遺傳算法的新工件重調度優化方法

在審

• 申請號: 201910061608.8
• 申請日: 2019-01-23
• 公開（公告）號: CN110059908A
• 公開（公告）日: 2019-07-26
• 發明（設計）人: 郭艷東
• 申請（專利權）人: 渤海大學
• 主分類號: G06Q10/06
• 分類號: G06Q10/06;G06N3/12
• 代理公司: 錦州遼西專利事務所(普通合伙) 21225
• 代理人: 李輝

1.一種基于自適應遺傳算法的新工件重調度優化方法，其特征是：包括如下步驟：

步驟1：建立模型

在具有熱處理工位已知初始工件集J_O＝{1,...,n_O}的初始調度υ，針對一組新到工件J_N＝{n_O+1,...,n_O+n_N}，在滿足實際工藝要求的前提下，對所有工件進行重調度，從而獲得目標為最小化所有工件等待時間和的重調度方案；

數學模型描述如下：

s.t

w_j(σ)≤K,j∈J_O (2)

s_j(σ)≥r_j,j∈J (3)

s_[j](σ)+p_[j]≤s_[j+1](σ)，j∈J (4)

ros(σ)＝ros(υ) (5)

其中式(1)是目標函數，即最小化所有工件的等待時間和，w_i表示工件i等待加工的時間；式(2)中，初始工件在重調度σ中等待加工的時間不能超過K；式(3)保證工件只能在釋放時間之后被調度，即在重調度σ中工件j的開始加工時間s_j(σ)要不小于它的釋放時間r_j；式(4)說明同一時間只能有一個工件被加工，s_[j](σ)表示在第j個位置上被調度的工件開始加工的時間，p_[j]表示在第j個位置上被加工工件的處理時間；式(5)中，重調度后初始工件的相對順序ros(σ)與初始調度中初始工件的相對順序ros(υ)保持不變；

步驟2：基于自適應遺傳算法求解問題

步驟2.1：初始化；

確定種群規模G、交叉率p_c、變異率p_m、替換率p_r，循環次數上限t和局域搜索次數T的初始值；

步驟2.2：生成初始種群；

每一個初始種群中的重調度序列按照如下方式產生：已知初始調度序列J_O＝{1,2,3,...,n_O}，n_O為初始工件總數，而且重調度時初始調度中的初始工件之間的順序保持不變；隨機生成一個新工件的序列J_N＝{n_O+1,...,n_O+n_N}，n_N為新工件總數，依次考慮該序列中每一個新工件n_O+1,...,n_O+n_N，先考慮n_O+1將它插入到初始調度υ之前生成子重調度序列上面橫線表示新工件，等待檢驗；檢驗插入后的調度中最后一個新工件n_O+1之后的初始工件1,2,3,...,n_O是否滿足初始工件等待加工的時間受限的約束條件，即分別檢驗是否滿足w_i≤K,i＝1,...,n_O，如果滿足則該新工件被確定在此位置被調度，子重調度序列被確定，否則將該新工件放在最后一個違背約束條件(w_j＞K)的初始工件j之后調度生成并確定子重調度再考慮n_O+2將它緊接著插入含有一些新工件的子重調度中的最后一個新工件n_O+1之后，生成子調度然后再次等待檢驗；檢驗插入后的調度中最后一個新工件n_O+2之后的初始工件j+1,...,n_O是否滿足w_i≤K,i＝j+1,...,n_O，如果滿足則該新工件被確定在此位置被調度，子重調度序列被確定，否則將該新工件放在最后一個違背約束條件(w_i＞K)的初始工件i之后調度生成并確定子重調度按照以上方法依次確定新工件的調度位置，直到新工件n_O+n_N的調度位置被確定，最終確定一個重調度σ；

然后再隨機生成一個新工件序列按照如上方法產生另一個重調度，直到生成的重調度數G等于預設的種群數；

步驟2.3：判斷是否為最優重調度；如果是則個體即為最優的重調度方案；否則，執行如下步驟：

步驟2.4：順序交叉；根據交叉率p_c，針對父代個體中每對染色體執行順序交叉操作，具體的步驟如下：

a：給定兩個父代染色體，如和

b：列出父代中新工件序列和并選擇準備交叉的兩個交叉點x,y(和)；

c：交換兩個交叉點之間的基因，得到和作為子代個體的部分基因；

d：從b中第二個交叉點的右側開始，依次列出新工件的基因和然后刪除與c中已經確定的子代個體中重復的基因和

e：在c中子代個體的部分基因和的基礎上，從第二個交叉點的右側第一個位置開始按照d中的順序依次調度新工件，形成一個子代中新工件的序列和

f：按照e中新工件的序列順序，將新工件按照步驟2.2的方法插入到初始調度中，最終形成2個子代個體；

步驟2.5：變異操作；根據變異率p_m，對執行交叉操作后的染色體執行變異操作，具體的步驟如下：

已知一個父代個體，例如列出該父代中新工件的調度序列并隨機選擇兩個新工件然j_i和j_j；然后交換兩個被選中的新工件，則新形成一個新到工件的調度序列按照交換后的新工件的調度序列將新工件按照步驟2.2的方法插入到初始調度中進行調度，最終形成一個新的重調度序列，即一個子代個體

步驟2.6：染色體選擇操作；計算適值函數，運用輪盤賭的方法選擇父代個體，被選中的父代個體將被執行遺傳運算；

自適應遺傳算法采用正比選擇策略，即染色體被選擇的概率等于個體的適應值比上種群中所有個體適應值的和；在初始調度之后依次將所有新工件按照處理時間降序排列進行調度，得到一個可行的重調度序列是一個上界，染色體的適值函數為種群中的個體總數為S，則個體i在種群中的適應值為F_i(σ),i＝1,..S.，則個體i被選擇的概率為

自適應遺傳算法采用輪盤賭的方式實施選擇操作，令PP₀＝0，輪盤共旋轉S次；每一次旋轉就會隨機產生一個隨機數ξ_k∈U(0,1)，則當PP_i-1≤ξ_k＜PP_i時個體i被選擇；

步驟2.7：自適應局域搜索；

自適應局域搜索算法采用自適應學習機制結合倒置、轉移和互換三種局域搜索算子；在一個重調度序列中，所有新工件已被劃分成一些新工件塊，選擇塊結構作為鄰域結構；在一個重調度序列中隨機選取兩個新工件塊，然后調整兩個塊之間的新工件順序，即生成一個新的重調度序列，進而應用局域搜索的方法找到優于當前重調度解的新重調度序列；

步驟2.8：更新種群：將初始種群和子代種群中的個體按照目標函數值的非降序排列，選擇前G*p_r個個體替換父代種群中最后G*p_r個個體，即生成下一代種群；

步驟2.9：停止準則

如果循環的總次數達到規定的上限值t時，輸出具有最大適值函數的個體，計算結束；否則繼續執行步驟2.4進化種群。