章國政

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

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

1 計劃調(diào)度優(yōu)化算法介紹

1.1 遺傳算法原理概述

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

圖1 遺傳算法流程

1.2 計劃調(diào)度優(yōu)化算法流程

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

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

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

1.2.2 算法步驟

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

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

第三步：將染色體根據(jù)適應度函數(shù)進行排序，保留最優(yōu)的Parent個解。

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

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

第六步：重復第三步到第五步，直到適應度函數(shù)收斂，產(chǎn)生最優(yōu)解。

1.3 計劃調(diào)度優(yōu)化模型構建

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

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

其次，結(jié)合紡織廠現(xiàn)行的生產(chǎn)方式，將每一“任務單”分解成不同“批次”進行生產(chǎn)安排。

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

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

約束條件：

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

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

（3）完成時間約束。

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

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

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

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

2 實例計算

以某10萬錠規(guī)模企業(yè)為例，車間的基礎數(shù)據(jù)情況如下。

2.1 生產(chǎn)線配置

生產(chǎn)線配置如表2所示。

表2 生產(chǎn)線配置

2.2 各工序制成率、設備運轉(zhuǎn)率、設備運行時間

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

表3 各工序制成率、設備運轉(zhuǎn)率、設備運行時間

2.3 產(chǎn)品干濕重

各個產(chǎn)品干濕重如表4所示。

2.4 訂單信息情況

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

表4 各個產(chǎn)品干濕重

表5 訂單信息

遺傳算法參數(shù)選?。哼z傳進化迭代次數(shù)M=10；種群規(guī)模N=40；變異概率Pm=0.5；每一代中保持不變的數(shù)目Parent_N=20。

通過遺傳算法計算產(chǎn)生的訂單號1的最優(yōu)排產(chǎn)方案如表6所示。

表6 訂單號1的最優(yōu)排序方案