[發明專利]一種應用在生產排程系統的基于訂單結構的遺傳操作算子

無效

• 申請號: 200810035774.2
• 申請日: 2008-04-09
• 公開（公告）號: CN101256648A
• 公開（公告）日: 2008-09-03
• 發明（設計）人: 顧永明;陳杰
• 申請（專利權）人: 永凱軟件技術（上海）有限公司
• 主分類號: G06Q10/00
• 分類號: G06Q10/00;G06N3/12
• 代理公司: 上海新天專利代理有限公司
• 代理人: 王敏杰

技術領域

本發明涉及一種應用在生產排程系統中的遺傳操作算子，用于處理多層次BOM結構的復雜工藝的訂單排程問題。

背景技術

遺傳算法是一種基于基因學和遺傳學機理產生的直接搜索優化方法，它通過基因串的選擇、交叉、變異，來尋求最佳解決方案。近年來，這種算法作為一種通用的優化算法，因其編碼技術和遺傳操作比較簡單、優化不受限制性條件的約束、尤其是具有并行計算能力和全局解空間搜索能力，被廣泛的應用在各行各業。生產排程問題——即如何合理利用有限的資源達到預期的生產目標，也可以通過這種算法進行優化解決。

應用遺傳算法來解決生產排程問題可以通過以下步驟來實現：首先，對參與排程的工單進行置換編碼，生成初始化種群；然后，選擇優秀個體作為父代種群，進行交叉、變異，生成子代種群，再對子代種群進行解碼操作，得到排程方案；再對排程方案進行約束條件檢驗，保留優秀個體；重復進行以上選擇、交叉、變異操作和約束條件檢驗兩個步驟，直至最優個體達到優化目標。

在此過程中應用遺傳算法來解決生產排程問題實質上是通過遺傳操作，即選擇、交叉、變異操作，來不斷產生新的基因，并淘汰劣等基因、保持優良基因，逐步優化完善方案的。因此遺傳操作的設計成為能否得到高質量優化排程方案的關鍵。

Job?Shop(車間)調度問題是許多實際生產調度問題的簡化模型，是一個典型的NP-hard問題，是目前研究的最廣泛的一類典型調度問題。但針對傳統Job?Shop調度問題設計的遺傳算法，尤其是遺傳操作的設計，在處理具有多層次BOM(Bill?of?Material，物料清單)結構的工藝復雜的訂單時具有一定的局限性。

發明內容

本發明的目的在于提供一種應用在生產排程系統的基于訂單結構的遺傳操作算子，對可行解池和不可行解池內的解選擇性進行選擇、交叉、變異操作，得到各種遺傳解，為之后的排程優化，提供一個基礎。

在具體應用遺傳算法解決排程問題時，遺傳操作是針對已有的遺傳基因串，即排程方案解，進行的。已生成的解可以根據是否符合約束條件，分作可行解和不可行解，分別存入可行解池和不可行解池。為了避免無解狀況和增強多樣性，遺傳算方法在這兩個解池的基礎上選擇優秀個體，選擇性進行交叉、變異操作，生成下一代基因串，為排程方案解的優勝劣汰提供基礎，選擇、交叉、變異操作包括以下特征：

1.選擇是通過設置選擇率κ為閾值來實現的：若可行解池中個體數目與種群規模的比值小于κ，則可行解池中全部個體作為父代種群；若可行解池中解的數目與種群規模的比值大于κ，則從可行解池中選擇種群規模的κ倍的個體作為父代種群，并從不可行解池中選擇部分個體補足所需種群規模，即使得不可行解池中選擇的個體數目與之前在可行解池選擇的個體數目之和達到種群規模；此處種群規模為計算前預定義的父代種群的大??；

2.交叉是從父代種群中選取一對代表排程方案的基因串個體，并選擇交叉操作算子進行交叉操作生成一對新的個體，存入子代種群，直至子代個數達到交叉率所規定的足夠數目；

3.變異是從父代種群中選取一個代表排程方案的基因串個體，并選擇變異操作算子進行變異操作生成一個新的個體，存入子代種群，直至子代個數達到變異率所規定的足夠數目；

所述1中的選擇率κ閾值設置的范圍為

所述1中可行解池中解的數目與種群規模的比值大于κ情況下對可行解池中解的選擇，是通過按解適應度值的高低作為其被選擇到的概率，由輪盤賭方式來實現的。

所述1中不可行解池中解的選擇，是按解的適應度值由高至低的次序來選擇的。

所述2中的交叉操作算子，為三種交叉操作算子：a.兩段式交叉操作算子：一父代基因串分兩段和另一父代基因串進行比較、刪除、替換，生成子代基因串；b.訂單位置不變交叉操作算子：一父代基因串保留同一訂單所涉及工單或工序的基因位，其他基因位由另一父代基因串的非所述訂單所涉及工單或工序的基因位進行補充，生成子代基因串；c.訂單加工順序改變交叉操作算子：一父代基因串中同一訂單所涉及工單或工序的基因位由另一父代基因串的所述訂單所涉及工單或工序的基因位進行替換，生成子代基因串。其中，兩段式交叉操作算子包括三種子算子：保留父代基因串前段、或保留父代基因串后段、或保留父代基因串較長段。