基于多目標(biāo)多約束的生產(chǎn)制造業(yè)的計(jì)劃排產(chǎn)問(wèn)題研究

解云龍，袁魯平，朱寧帥

（山東聯(lián)誠(chéng)精密制造股份有限公司，濟(jì)寧272100）

隨著市場(chǎng)競(jìng)爭(zhēng)的加劇，保證交期是生產(chǎn)制造業(yè)生產(chǎn)制造過(guò)程中的核心競(jìng)爭(zhēng)力之一。中國(guó)很多生產(chǎn)制造企業(yè)開(kāi)始轉(zhuǎn)向按訂單生產(chǎn)（MTO），甚至按訂單設(shè)計(jì)（ETO）的制造模式[1-2]，這種情況下，通過(guò)計(jì)劃排程控制產(chǎn)品最終的交期，變得越發(fā)重要。保證產(chǎn)品最終交期，在生產(chǎn)制造過(guò)程中體現(xiàn)為最小化生產(chǎn)完成時(shí)間。最小化生產(chǎn)完成時(shí)間基本上涉及兩個(gè)目標(biāo)，即最小化機(jī)器閑置時(shí)間和最小化訂單提前率/延遲率。必須通過(guò)考慮所有約束條件（例如優(yōu)先級(jí)、可用機(jī)器、機(jī)器轉(zhuǎn)換、機(jī)器設(shè)置、機(jī)器容量、大量庫(kù)存等）來(lái)實(shí)現(xiàn)這兩個(gè)目標(biāo)的最小化。這需要通過(guò)高級(jí)計(jì)劃和排程（APS）來(lái)實(shí)現(xiàn)。APS 本質(zhì)是實(shí)現(xiàn)有限資源的優(yōu)化配置和調(diào)度，需要依靠強(qiáng)大的計(jì)劃和排程算法驅(qū)動(dòng)，很多學(xué)者在這些方面做了大量的研究。文獻(xiàn)[3]給出了基于常規(guī)遺傳算法和基于混合遺傳算法的車(chē)間作業(yè)調(diào)度問(wèn)題的有效解法，文中表明混合遺傳算法在比常規(guī)遺傳算法效果更好，在更短的時(shí)間內(nèi)找到最佳結(jié)果；文獻(xiàn)[4]和文獻(xiàn)[5]提出的基于多階段的多目標(biāo)遺傳算法（moGA）可以有效求解生產(chǎn)車(chē)間計(jì)劃調(diào)度（JSP）過(guò)程中多目標(biāo)多約束的問(wèn)題，并引出懲罰系數(shù)解決遺傳算法陷入局部最優(yōu)解的問(wèn)題；文獻(xiàn)[6]和文獻(xiàn)[7]解釋了自適應(yīng)遺傳算法的概念，該算法以最佳適應(yīng)性自適應(yīng)地生成染色體，實(shí)現(xiàn)了在n 個(gè)工序（job）的m 臺(tái)設(shè)備/工作中心（machine）上進(jìn)行計(jì)劃調(diào)度，該過(guò)程是一個(gè)典型的NP-Hard 問(wèn)題，求解及其復(fù)雜。因此，為了解決這個(gè)問(wèn)題，給出了一種具有基于禁忌搜索的遺傳算法，即GATS[8]。GATS 的主要方法是最小化制造時(shí)間、處理時(shí)間和迭代次數(shù)，從而獲得更好的結(jié)果[9-10]。文獻(xiàn)[11]針對(duì)多目標(biāo)高級(jí)計(jì)劃和調(diào)度問(wèn)題的基于偏好的自適應(yīng)遺傳算法研究中心中給出了數(shù)值實(shí)驗(yàn)，以說(shuō)明所開(kāi)發(fā)算法的有效性和效率。

綜上所述，本文提出了一種基于迭代搜索技術(shù)的遺傳算法，以實(shí)現(xiàn)生產(chǎn)制造生產(chǎn)車(chē)間的多目標(biāo)多約束條件下的計(jì)劃調(diào)度問(wèn)題。本算法采用通用編程模型的形式，可以滿足所有優(yōu)先級(jí)和替代機(jī)器容量的限制。基于迭代搜索技術(shù)的遺傳算法主要考慮3個(gè)步驟，即染色體編碼、確定適應(yīng)度函數(shù)以及將遺傳算子用作選擇、交叉和變異3 個(gè)步驟，以最小化目標(biāo)函數(shù)并提供更優(yōu)化的解決方案。

1 車(chē)間調(diào)度模型

本節(jié)描述了典型的裝配車(chē)間生產(chǎn)計(jì)劃和排產(chǎn)數(shù)學(xué)模型，該模型已經(jīng)在大多數(shù)研究中應(yīng)用[3-7]。

車(chē)間調(diào)度數(shù)學(xué)模型的變量列舉如下：

K：訂單數(shù)量

D：位置數(shù)量

N：資源數(shù)量

Ok：訂單K 一組工序

JK：訂單K 的工序數(shù)

Mm：第M 項(xiàng)資源

Pd：第d 處位置

qk：訂單K 的批量

Am：在Mm上資源加工的工序

Pkim：機(jī)器m 上的Oki操作的單位處理時(shí)間

Lm：設(shè)備m 上的產(chǎn)能

tkilj：從Oki操作到Okj操作的設(shè)置時(shí)間

tmn：設(shè)備m 到設(shè)備n 之間的單位運(yùn)輸時(shí)間

ukij：從運(yùn)行Oki到運(yùn)行的訂單k 的單位負(fù)載大小

Sd：工廠Pd的資源集

Ld：可用于從Pd運(yùn)輸?shù)馁Y源集

rkij：優(yōu)先約束

考慮到每臺(tái)機(jī)器上每個(gè)工序的處理時(shí)間的輸入數(shù)據(jù)集，每個(gè)工序之間的建立時(shí)間和每臺(tái)機(jī)器之間的轉(zhuǎn)換時(shí)間，優(yōu)化兩個(gè)目標(biāo)函數(shù)所需的各種參數(shù)如下：

（1）加工工時(shí)

（2）訂單k 的完工時(shí)間

（3）從機(jī)器m 到機(jī)器n 的總運(yùn)輸時(shí)間

（4）設(shè)備M 的工作負(fù)荷

（5）設(shè)備總空閑時(shí)間

式中：i，j 為工序號(hào)序列，i，j=1，2，…，Jk；k，l 為訂單號(hào)序列，k，l=1，2，…，K；m，n 為資源號(hào)序列，m，n=1，2，…，N；d，e 為位置號(hào)序列，d，e=1，2，…，D。

在每個(gè)方程式中，變量xkim，ykilj稱為決策變量，可以通過(guò)將條件循環(huán)應(yīng)用為以下變量來(lái)應(yīng)用：

目標(biāo)函數(shù)

這兩個(gè)目標(biāo)函數(shù)必須通過(guò)牢記一些約束來(lái)最小化：

（1）如果出現(xiàn)以下情況，機(jī)器不能同時(shí)處理多個(gè)操作

（2）在以下情況下，確保機(jī)器之間的中間傳遞：

必須滿足以上兩個(gè)約束條件，這樣操作才能在一臺(tái)機(jī)器上運(yùn)行而不會(huì)產(chǎn)生任何中斷。

（3）產(chǎn)能約束條件滿足：

（4）如果沒(méi)有違反關(guān)于優(yōu)先級(jí)限制的保證：

（5）確保靈活的工序（操作順序）：

（6）對(duì)可變的設(shè)備列表選擇：

2 計(jì)劃排產(chǎn)問(wèn)題

2.1 用例描述

基于上述的數(shù)學(xué)模型建立車(chē)間計(jì)劃排產(chǎn)問(wèn)題的數(shù)學(xué)解法，將問(wèn)題定義為（訂單數(shù)量，工序數(shù)量，資源數(shù)量）。采用經(jīng)典的數(shù)據(jù)模型[3-4]（2，10，4），（4，17，6），（5，25，8），（8，40，10），（20，70，15）（30，150，20）。對(duì)于所有這些要滿足的問(wèn)題，參數(shù)和約束需要設(shè)置3 個(gè)輸入數(shù)據(jù)集，即在各種資源上的每個(gè)工序的處理時(shí)間，每個(gè)工序之間的設(shè)置時(shí)間以及資源之間的轉(zhuǎn)換時(shí)間。其中表1 是對(duì)應(yīng)工序在對(duì)應(yīng)設(shè)備/工作中心的加工時(shí)間；表2 為不同設(shè)備之間的轉(zhuǎn)移時(shí)間；表3 為不同工序之間的設(shè)置時(shí)間（前置時(shí)間）。

表1 對(duì)應(yīng)工序在對(duì)應(yīng)設(shè)備/工作中心的加工時(shí)間/（min）Tab.1 Processing time of corresponding process in corresponding equipment/work/（min）

表2 不同設(shè)備之間的轉(zhuǎn)移時(shí)間/（min）Tab.2 Transfer time between machines/（min ）

表3 不同任務(wù)的安裝時(shí)間/（min）Tab.3 Setup time of different tasks/（min）

對(duì)于數(shù)據(jù)（2、10、4），所有10 個(gè)操作都可以在多臺(tái)機(jī)器上處理，因此稱為自由工序。

2.2 基于迭代搜索技術(shù)的遺傳算法優(yōu)化

可以通過(guò)最小化上述兩個(gè)目標(biāo)函數(shù)f1和f2來(lái)找到給定過(guò)程的最優(yōu)解。相對(duì)于給定數(shù)據(jù)集和約束條件，可以通過(guò)應(yīng)用遺傳算法的概念來(lái)最小化這兩個(gè)方程。遺傳算法會(huì)為給定問(wèn)題生成隨機(jī)解的數(shù)量，并從中選擇適合度最大的一個(gè)。這些解決方案將進(jìn)行多次迭代以找到最大擬合值。具有最大適合度值的解決方案表示最佳解決方案。在遺傳算法應(yīng)用可以通過(guò)考慮設(shè)置一些基本參數(shù)：

最大變種數(shù)MG=100；

種群規(guī)模Psize=50；

最大迭代數(shù)N=50；

目標(biāo)函數(shù)Oj1的權(quán)重w1=0.2；

目標(biāo)函數(shù)Oj2的權(quán)重w2=0.5；

最早時(shí)間的權(quán)重α=0.1；

總延遲時(shí)間的權(quán)重β=0.9；

2.2.1 工序優(yōu)先級(jí)分配向量

這基本上是通過(guò)牢記優(yōu)先約束來(lái)隨機(jī)處理所有工序的分配，以完成所有任務(wù)。由于在上述案例研究中有10 個(gè)工序。這意味著為機(jī)器生成的初始染色體只會(huì)隨機(jī)生成10 個(gè)帶有隨機(jī)序列的操作的染色體。用P1表示。

如圖1所示，從P1到Pn隨機(jī)生成工序分配矢量的數(shù)量，其中n 表示總代數(shù)。

圖1 遺傳算法中工序優(yōu)先級(jí)分配向量示圖Fig.1 Vector diagram of process priority allocation in genetic algorithm

2.2.2 工序的設(shè)備分配向量

再次為上述工序隨機(jī)分配設(shè)備/工作中心。由于針對(duì)提供的不同設(shè)備進(jìn)行處理時(shí)，每個(gè)工序都具有不同的加工時(shí)間，因此設(shè)備分配是尋找遺傳算法最優(yōu)解的有效任務(wù)之一，對(duì)于每個(gè)工序序列，將分配多個(gè)設(shè)備序列，即從M1到Mn，如圖2所示。

圖2 遺傳算法中工序的設(shè)備分配向量示圖Fig.2 Vector diagram of equipment allocation in genetic algorithm

（1）適應(yīng)度函數(shù)

最佳解決方案是由對(duì)前代具有更高適應(yīng)性的染色體代表的，公式如下：

式中：w1和w2是基于目標(biāo)函數(shù)的分配權(quán)重。

（2）交叉

通過(guò)保持對(duì)應(yīng)工序的設(shè)備分配向量相同，可以選擇具有最高適應(yīng)性的2 條最佳染色體，示意圖如圖3所示。

圖3 遺傳算法中交叉過(guò)程示圖Fig.3 Diagram of crossover process in genetic algorithm

（3）突變

遺傳算法中突變的實(shí)際目是檢查在雜交過(guò)程中產(chǎn)生的后代具有比先前最大適應(yīng)性的其他可能性。在計(jì)劃排產(chǎn)問(wèn)題上表現(xiàn)為從每個(gè)工序處理時(shí)間的給定數(shù)據(jù)來(lái)看，每個(gè)工序在不同的機(jī)器上具有不同的執(zhí)行時(shí)間，如圖4所示。

圖4 遺傳算法中突變過(guò)程示圖Fig.4 Diagram of mutation process in genetic algorithm

3 結(jié)果與討論

表1 中顯示了針對(duì)每臺(tái)設(shè)備的優(yōu)化測(cè)試計(jì)劃。它由行數(shù)為1～4 的行的矩陣組成，每臺(tái)設(shè)備的工序順序?yàn)?～10。優(yōu)化的時(shí)間表顯示，首先為所有4 臺(tái)設(shè)備選擇了所有獨(dú)立的操作。其余工序?qū)⒌玫絻?yōu)先處理。

對(duì)于用例（2，10，4）采用上述基于迭代搜索的遺傳算法的優(yōu)化。得到優(yōu)化結(jié)果如表4所示，圖5展示了當(dāng)前適應(yīng)度函數(shù)的設(shè)備利用率。

表4 對(duì)于（2，10，4）的優(yōu)化結(jié)果Tab.4 Optimization results of（2，10，4）

與以往的研究對(duì)比發(fā)現(xiàn)[3-5]，在相同的目標(biāo)函數(shù)下，優(yōu)化結(jié)果更佳，且計(jì)算時(shí)間更短。

迭代次數(shù)在最小化編譯時(shí)間的情況下起著至關(guān)重要的作用，可以最大程度地減少總生產(chǎn)時(shí)間，確保交期，表5 給出了幾個(gè)數(shù)據(jù)集下的最小化完工時(shí)間。

圖5 設(shè)備利用率Fig.5 Equipment utilization

表5 迭代搜索遺傳算法下的最小化完工時(shí)間Tab.5 Minimizing completion time under iterative search genetic algorithm

4 結(jié)語(yǔ)

本文給出了一種迭代搜素的遺傳算法（IGA），該算法提供引入了均值匯編參數(shù)，建立基于一個(gè)編程模型的遺傳算法，可以在滿足多約束條件的情況下最小化生產(chǎn)的總生產(chǎn)時(shí)間，經(jīng)與以往研究對(duì)比發(fā)現(xiàn)，該算法可行。同時(shí)針對(duì)不同的數(shù)據(jù)集進(jìn)行計(jì)算分析，這些數(shù)據(jù)集的求解結(jié)果與迭代次數(shù)的所需變化有關(guān)。因此，對(duì)于多目標(biāo)多約束高級(jí)計(jì)劃和調(diào)度，基于迭代搜索的遺傳算法可以以較少的計(jì)算時(shí)間找到給定問(wèn)題的最佳和最佳解決方案，可以滿足實(shí)際生產(chǎn)應(yīng)用中的實(shí)時(shí)性要求，尤其是在以按訂單設(shè)計(jì)（ETO）、按訂單生產(chǎn)（MTO）制造模式為主的生產(chǎn)制造業(yè)具備良好的應(yīng)用性。