[發明專利]一種基于多色集合遺傳算法的多目標車間調度方法

在審

• 申請號: 201710019067.3
• 申請日: 2017-01-11
• 公開（公告）號: CN106875094A
• 公開（公告）日: 2017-06-20
• 發明（設計）人: 欒飛;魏夢珂;李彬彥;傅衛平;王雯;來春為;鄧明明
• 申請（專利權）人: 陜西科技大學
• 主分類號: G06Q10/06
• 分類號: G06Q10/06;G06N3/12
• 代理公司: 西安通大專利代理有限責任公司61200
• 代理人: 陸萬壽

【技術領域】

本發明屬于作業調度技術領域，涉及一種基于多色集合遺傳算法的多目標車間調度方法。

【背景技術】

目前對單目標調度問題的優化求解，很少考慮工藝過程與調度之間的聯系以及如何設計二者之間的關系。在實際生產中，經常會遇到作業調度目標不同的狀況：如有一批加工任務，有些工件必須滿足客戶的交貨期要求，有些工件要求盡快完工，而有些工件要求盡可能低的生產加工成本，因此車間調度必須兼顧所有工件的調度目標。

【發明內容】

本發明的目的在于克服上述現有技術的缺點，提供一種基于多色集合遺傳算法的多目標車間調度方法，在改進遺傳算法中運用帶有偏好信息的隨機權重系數法，將多目標調度問題轉化成單目標問題來求解。

為達到上述目的，本發明采用以下技術方案予以實現：

一種基于多色集合遺傳算法的多目標車間調度方法，包括以下步驟：

1)根據約束條件和目標函數，運用隨機權重系數法將多目標優化轉單目標優化；

2)建立工序-設備圍道矩陣的約束方式，進行染色體編碼，縮小GA的搜索范圍。

本發明進一步的改進在于：

所述步驟1)中，約束條件如下：

FJSP被描述為：設M為加工設備的數量，N為待加工工件數量，P為工序數，I為所有設備的集合；Ieg代表工件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；

所述步驟1)中，目標函數為：

(a)完工時間最小：

(b)生產成本最低：

(c)工序能力指數最大：

所述步驟1)中，運用隨機權重系數法將多目標優化轉單目標優化

1-1)偏好定義：

偏好用二元關系表示，給定一組二元關系P和Q，決策者存在以下偏好關系：

(a)若決策者對P的偏好大于Q，記作P＞Q；

(b)若決策者對P的偏好小于Q，記作P＜Q；

(c)若決策者對P，Q的偏好都差不多，記作P～Q；

(d)若未知決策者對P，Q的偏好，記作P？Q；

1-2)設偏好矩陣確定各個目標的重要程度，得到各個目標函數的重要度排序；

1-3)用偏好信息設置各目標函數的隨機權重系數：

從偏好矩陣中得到的各個目標之間的重要程度排序，根據重要程度排序來設置隨機權重系數；若有n個目標，根據偏好矩陣得到n個目標的偏好排序，比如f₁＞f₂＞...＞f_i＞...＞f_n，利用Matlab軟件中的隨機函數rand(1,n)得到n個隨機數，記為rand₁,rand_i,...,rand_n，將這n個隨機數比較大小后排列，越重要的目標對應的隨機數越大，進而得到各個目標函數相應的隨機權重系數為：

生成權重向量：W＝(w₁,w₂,...,w_i,...,w_n)，進而將多目標函數轉化為單目標函數：

所述步驟2)具體方法如下：

2-1)染色體編碼

首先建立工序-設備的圍道矩陣，然后進行染色體編碼，具體編碼是按照某種工件的某道工序在某個設備上加工的信息進行設備的編碼，每個碼位代表了某種工件的某道工序，每個碼位上的信息是設備信息；

2-2)初始化種群