基于遺傳算法的紡紗車間計劃調度優化策略研究

章國政

（經緯紡織機械股份有限公司中央研究院，北京 100176）

紡紗生產車間計劃調度就是根據需求，合理分配產線及相應的生產制造資源，達到合理利用產品制造資源、提高企業經濟效益的目的。當前，大部分紡紗企業在制作生產計劃時，主要還是依靠人工計算的方式來進行，存在工作強度大、應對變化的能力弱且調度結果不一定最優的問題。研究發現，大部分紡紗企業的車間生產過程有以下特點：（1）所有的生產都是以訂單為驅動；（2）工序之間存在定臺供應的情況，可以生產線的形式來表示；（3）對于細紗工序，以翻改品種次數最少為優選策略；（4）整體車間生產計劃需要以所有訂單都能準時交付為目標。考慮以上因素，可以制作出紡紗車間生產計劃調度模型，利用遺傳算法求解，得到訂單排產計劃的優化方案。

1 計劃調度優化算法介紹

1.1 遺傳算法原理概述

遺傳算法是模擬達爾文進化論自然選擇和遺傳學機理的生物進化過程的計算模型，是一種通過模擬自然進化過程搜索最優解的方法。遺傳算法是從代表問題可能潛在的解集的一個種群開始的，而一個種群則由經過基因編碼的一定數目的個體組成。在初代種群產生之后，按照適者生存和優勝劣汰的原理，逐代演化，產生越來越好的近似解，在每一代，根據問題中個體的適應度大小選擇個體，并借助自然遺傳學的遺傳算子，進行組合交叉和變異，產生代表新解集的種群。這個過程將導致種群像自然進化一樣的后生代種群，比前代更適應環境，末代種群中的最優個體，對應作為問題近似的最優解。遺傳算法的具體流程如圖1所示。

圖1 遺傳算法流程

1.2 計劃調度優化算法流程

1.2.1 訂單元素與遺傳算法元素的對應關系

模擬自然界優勝劣汰的進化現象，將搜索問題轉化為遺傳問題，把可能的解轉為一個向量—染色體，向量的每個元素稱為基因。通過不斷計算各染色體的適應值，選擇最好的染色體，獲得最優解[1]。訂單元素與遺傳算法元素的對應關系如表1所示。

表1 訂單元素與遺傳算法元素的對應關系

1.2.2 算法步驟

第一步：構造目標函數GeneticAlgorithm，確定輸入、輸出變量。輸入變量為：遺傳進化迭代次數M、種群規模N、變異概率Pm、每一代中保持不變的數目Parent、批次信息List、設備配置信息；輸出變量為：最優完工時間Zp、各批次分配的生產線BatchLine、各批次各工序的開始時間Begin、各批次各工序的結束時間End、各批次各工序的輸入次數Input、各批次各工序的輸出次數Output。

第二步：隨機產生初始種群farm并計算適應度函數[2]。在群體farm中，每一個染色體為隨機產生的一組生產調度方案。

第三步：將染色體根據適應度函數進行排序，保留最優的Parent個解。

第四步：交叉。在種群中，選擇兩個父代染色體進行交叉方式和交叉點的隨機選擇，產生兩個新的子代染色體，并將新舊染色體組合成新的種群，即在隨機產生的眾多生產調度方案中，選擇兩個父代方案進行交叉。交叉的具體操作是將兩個調度方案中的工件和工序相關信息進行交換，然后產生兩個新的子代方案[3]。

第五步：變異。在種群中，隨機選擇要變異的基因，產生新的染色體，以避免局部收斂的情況發生，即通過隨機的方法，產生新的生產調度方案。

第六步：重復第三步到第五步，直到適應度函數收斂，產生最優解。

1.3 計劃調度優化模型構建

紡織企業的生產任務是以訂單為基礎，因此，研究從訂單出發構建模型的方法，并設計相應算法[4]。

首先，當紡織企業在短期內接到不同訂單時，要對訂單的加工需求進行分類，按照不同訂單中相同的加工種類進行生產，訂單中的每一個品種即為一個任務單。例如，紡織車間有3條生產線。企業在短期內收到3條訂單：訂單一包括A、B、C 3種類型的紡織品，訂單二包含A、C兩種紡織品，訂單三包含B、C兩種紡織品。在生產時，將所有訂單的各種紡織品隨機分配生產線，并隨機確定同一生產線上各批次加工的先后順序。不同任務單的加工順序需要服從生產計劃的安排[5]。

其次，結合紡織廠現行的生產方式，將每一“任務單”分解成不同“批次”進行生產安排。

最后，算法將以滿足生產最晚交付時間情況下的最小化完成時間為目標進行優化計算。

具體數學語言描述為：在企業收到的某個訂單當中，有i種紗織品（細紗），這i種紗織品分為i批次進行生產，各種批次的總量為Ni，這里的總量以細紗機的最后輸出為標準。i批次的紡織品依次經過7道工序，分別為清梳聯、預并條、條并卷、精梳、末并、粗紗、細紗[6]。調度的目標是最小化最長完工時間，目標函數為：

約束條件：

（1）工序約束。在前一道工序完成一定的產出量以后才能開始在后一道工序上加工：

（2）機器約束。同一生產線，上一個加工任務完成之后才能開始下一個加工任務：

（3）完成時間約束。

其中，第i個批次在第j條生產線上，第（k+1）道工序完成的時間Cij(k+1)滿足如下約束：

式中，Ci為第i個批次的完工時間；STijk表示第i個批次在第j條生產線上生產時第k道工序開始時間；Cijk表示第i個批次在第j條生產線上生產時第k道工序結束時間；Pijk表示第i個批次在第j條生產線上生產時第k道工序的加工時間。

（4）加工開始時，所有的原料都已準備就緒。

每個批次按照7道工序的順序依次加工，并且僅加工一次。

2 實例計算

以某10萬錠規模企業為例，車間的基礎數據情況如下。

2.1 生產線配置

生產線配置如表2所示。

表2 生產線配置

2.2 各工序制成率、設備運轉率、設備運行時間

各工序制成率、設備運轉率、設備運行時間如表3所示。

表3 各工序制成率、設備運轉率、設備運行時間

2.3 產品干濕重

各個產品干濕重如表4所示。

2.4 訂單信息情況

訂單信息情況如表5所示。

表4 各個產品干濕重

表5 訂單信息

遺傳算法參數選取：遺傳進化迭代次數M=10；種群規模N=40；變異概率Pm=0.5；每一代中保持不變的數目Parent_N=20。

通過遺傳算法計算產生的訂單號1的最優排產方案如表6所示。

表6 訂單號1的最優排序方案