[發明專利]一種基于改進遺傳算法的在制狀態人員調度方法

有效

• 申請號: 201711381996.5
• 申請日: 2017-12-20
• 公開（公告）號: CN108182518B
• 公開（公告）日: 2021-12-10
• 發明（設計）人: 盧治兵
• 申請（專利權）人: 北京遙感設備研究所
• 主分類號: G06Q10/06
• 分類號: G06Q10/06;G06N3/12
• 代理公司: 中國航天科工集團公司專利中心 11024
• 代理人: 姜中英

1.一種基于改進遺傳算法的在制狀態人員調度方法，其特征在于具體步驟為：

步驟1、基于在制狀態的人員調度問題建模，人員的在制狀態指在進行人員調度時，人員已被安排部分任務；基于在制狀態的人員調度是在不影響人員原有任務作業的基礎上，為新建任務安排作業人員；基于在制狀態的人員調度是實現任務與人員協同調度技術的關鍵，根據于當前工人狀態對任務進行人員安排，確定任務在制造中的起止時間；

步驟2、利用改進遺傳算法，實現在制狀態人員調度的最優解的求解，

其中，所述步驟1中進行問題數學建模具體為：

步驟11、基于在制狀態的人員調度問題描述：作業現場共有w個工人{W₁,W₂,...,W_w}，在不影響工人原有任務作業的前提下為b個新任務{B₁,B₂,...,B_b}安排作業人員；每個任務工藝路線預先確定，由一道或者多道序組成，每道工序有固定的工時在同一時刻選擇多個對應工種和工人進行加工，每個工人掌握一種作業技能；通過確定最佳的工序作業順序，并為每道工序選擇最佳的人員組合，在滿足所有工序對人員需求的條件下，獲得最佳性能指標，是基于在制狀態下人員調度的目標；

步驟12、基于在制狀態的人員調度約束：

在人員調度過程中對人員提出如下約束：

①人員的初始狀態為已安排部分作業任務；

②每個作業人員擁有獨立的加工日歷；

③每個人員在同一時刻只能加工一個任務的一道序；

④當確定作業人員的加工工序，其加工過程不能停止直至工序完成；

⑤每個人員掌握一種作業技能；

⑥忽略作業人員在任務間的流轉時間；

對任務提出如下約束：

①任務的工藝路線約束：每個任務對應一道或者多道工序，工序的工藝路線預先確定；

②每道工序對應至少一個工種，工種至少一個工人；

③每道工序有固定的工時；

④工序可作業的條件為，工序對應的工種和工人數量同時滿足需求；

⑤不考慮任務移出和移入車間的時間；

步驟13、基于在制狀態的人員調度數學建模：

(1)基礎數據定義

P_i,j表示任務B_i的第j道序；

[tpid¹,tpid²,...,tpid^k]表示所有工人工種的集合，tpid是工人工種對應功能種類的唯一標示符且tpid≠0，k表示種類的總數；

表示工人W_m的作業工種為tpid^k；

表示工序P_i,j所需工種的數量，取值為0到該種類資源數量的最大值，當取值為0時表示P_i,j不需要該種類資源；

表示P_ij作業開始時間，設每個任務由時刻0開始加工，因此

表示P_ij作業工時；

表示P_ij作業結束時間；

表示工序P_ij調度時工人的可用時間窗集合，其中表示在時刻與時刻之間對工序P_ij連續可用；

表示工序P_ij調度時工人的被占用的時間窗集合，其中表示在時刻與時刻之間連續被工序P_ij占用；

表示的工作日歷

表示在工序P_ij調度時刻工人被占用時間與空閑時間的合集為工人的工作日歷；

表示工序P_ij調度時刻工人被占用時間與空閑時間不重疊；

表示時間窗集合在時間段[ST,ET]之間的作業工時；

(2)工藝約束

表示工序必須滿足加工工藝約束；

表示工序加工過程不允許中斷；

(3)作業能力約束

工序P_ij加工需要一種或幾種數量不為0的瓶頸資源；

為工序P_ij的可加工資源的充要條件為

設為工序P_ij選擇的工人集合，對于集合中的任意元素在工序作業起止時間段內作業工時大于等于工序作業工時即

(3)目標函數

最大完工時間最短：

人力資源平均負荷：

適應度函數：

F＝ω₁f₁+ω₂f₂ (3)

其中ω₁,ω₂為f₁,f₂的加權值，

并且其中，所述步驟2包括：

步驟21、確定參數；包括種群規模、迭代次數、初始化、交叉概率、變異概率；

步驟22、初始種群；利用禁忌搜索思想，基于工藝約束與作業能力約束，建立候選工序集SP與人員集[S₁,S₂,...,S_K]，利用平衡人員之間負荷的偽隨機方法生成初始種群；

步驟23、解碼；利用基于啟發式規則的解碼算法對染色體進行解碼生成面向人員調度的可行解；

步驟24、適應度值：評價種群中每個染色體個體的適應度值即目標值，本次種群中最優解為

步驟25、如果滿足結束條件輸出最優解或者近似最優解，并且結束運行；否則執行步驟26；

步驟26、SA局部搜索；設初始化溫度為T₀，k＝0

While T_k＞T_endcount＝0

Whilecount＜L_max

在隨機選取一道工序，利用基于啟發式規則的解碼算法重新選擇作業資源，按照染色體中基因順序重新排成計算新的適應度值f^new；

采用Metropolis準則決定是否接受新解；

If接受新解

以新解取代舊解轉溫度更新；

Else count＝count+1；

END

溫度更新：T_k+1＝T_kα^k，其中α^k為溫度衰減率；

k＝k+1

END

返回最終

步驟27：如果滿足結束條件輸出最優解或者近似最優解，并且結束運行，否則執行步驟28；

步驟28：對種群中滿足交叉概率的染色體個體按照交叉策略進行交叉，對交叉得到的種群滿足變異概率的染色體個體按照變異策略進行變異，利用扇形分割法選取得到新一代種群，返回步驟24；

終止條件為達到設定的迭代次數。