[發明專利]基于多色集合層次結構的改進GA求解柔性車間調度的方法

有效

• 申請號: 201310737478.8
• 申請日: 2013-12-26
• 公開（公告）號: CN103729694A
• 公開（公告）日: 2014-04-16
• 發明（設計）人: 欒飛;曹巨江;傅衛平;寶昱彤
• 申請（專利權）人: 陜西科技大學
• 主分類號: G06Q10/04
• 分類號: G06Q10/04;G06Q10/06;G06N3/12
• 代理公司: 西安通大專利代理有限責任公司 61200
• 代理人: 陸萬壽

1.一種基于多色集合層次結構的改進GA求解柔性車間調度的方法，其特征在于，包括以下步驟：

1）建立柔性車間調度問題的數學模型；

2）建立基于PST層次結構的車間調度約束模型；

3）根據工序-基準，基準-設備編號，設備編號-資產編號圍道布爾矩陣，生成工藝-設備實數圍道矩陣，進而產生遺傳隱性編碼序列表，列標對應機床編碼，行標對應隱性基因位；其中，表中內容為工序的加工時間，隱性基因碼位對應工件的工序編號，通過搜索相應的工序-基準，基準-設備編號，設備編號-資產編號圍道布爾矩陣，從而找到對應于特定工序的機床編碼，再根據機床的可用性特征，選擇相應的機床編碼作為染色體的顯性編碼。

2.根據權利要求1所述的基于多色集合層次結構的改進GA求解柔性車間調度的方法，其特征在于：所述的步驟1）中，建立柔性車間調度問題的數學模型的具體方法為：

FJSP能夠被描述為，假設M為加工設備的數量，N為待加工工件數量，P為工序數，I為所有設備的集合；I_eg代表工件e的第g道工序的可用設備集合，J_e為工件e的工序數；X為所有工件的加工次序，S_egk表示工件e的第g道工序在設備k上加工的開始時間；E_egk為工件e的第g道工序在設備k上的加工結束時間；T_egk為工件e的第g道工序在設備k上的持續加工時間，且k∈I_eg則有E_egk=S_egk＋T_egk；E_p表示最后工序的完工時間；MS表示所有工件的最后完工時間；

當工件i的第j道工序和工件e的第g道工序在同一臺設備上執行，若工序j先于工序g加工時，Q_ijeg=1，否則Q_ijeg=0；若工件e的第g道工序在機床k上加工，則X_egk=1，否則X_egk=0；

若某FJSP共有S種可能的加工順序，要求總的作業時間最短的加工排序，先求取每個加工順序x(x∈{1,...,S})對應的作業時間；顯然，順序x中最后加工工序的完工時間即所有工件的最后完工時間，則有

MS=E_p???????????（1）

目標函數F(x)為

F(x)=min(MS_x)=min（(E_p)_x）????????（2）

X=1，…，S

S.T.S_egk－E_e(g－1)n≥0

e=1，…，N;g=1，…，J_e;X_egk=1，X_e(g－1)n=1???????（3）

S_egk－E_igk≥0

e=1，…，N;g=1，…，J_e;X_ijk=1，X_egk=1，Q_ijeg=1????（4）。

3.根據權利要求1所述的基于多色集合層次結構的改進GA求解柔性車間調度的方法，其特征在于：所述的步驟2）中，車間調度約束模型的約束關系為：

首先設置設備基準，每個設備基準包含相似工藝的幾種設備型號，每個設備型號又包含幾臺該種型號的具體設備，每臺具體設備又與對應的資產編號相對應，而工序最終要在具體設備上來完成加工，因此就可以通過工序與基準的約束關系，設備基準與設備型號的約束關系，設備型號與資產編號的約束關系，間接地建立工序與具體設備的約束關系，從而實現將龐大的工序機床圍道矩陣分割為小的關系矩陣，以降低矩陣的規模和數據量，提高算法的求解速度。