基于遺傳算法的多目標(biāo)柔性作業(yè)車間調(diào)度優(yōu)化

摘要：在現(xiàn)代制造業(yè)轉(zhuǎn)型升級背景下，柔性作業(yè)車間調(diào)度問題成為企業(yè)保持競爭優(yōu)勢的關(guān)鍵。本文以最小化總成本為目標(biāo)，將工序順序、設(shè)備能力等作為約束構(gòu)建多目標(biāo)優(yōu)化模型。引入輪盤賭選擇、精英保留策略及局部搜索等機制改進(jìn)遺傳算法，增強其全局搜索和局部優(yōu)化能力。實驗對比顯示，改進(jìn)遺傳算法在調(diào)度時間及解的優(yōu)化上優(yōu)于傳統(tǒng)遺傳算法及粒子群算法。

關(guān)鍵詞：柔性作業(yè)車間調(diào)度問題；多目標(biāo)優(yōu)化；遺傳算法；柔性生產(chǎn)

中圖分類號：TB"""""" 文獻(xiàn)標(biāo)識碼：A""""" doi：10.19311/j.cnki.16723198.2025.14.078

0 引言

在現(xiàn)代制造業(yè)中，調(diào)度是提升生產(chǎn)效率的關(guān)鍵。柔性作業(yè)車間調(diào)度問題（FJSP）突破了傳統(tǒng)資源限制，允許工序在多臺機器上進(jìn)行加工，這種靈活性使其更貼近實際生產(chǎn)需求，因而具有重要的理論和應(yīng)用價值。FJSP是經(jīng)典作業(yè)車間調(diào)度問題（JSP）的擴展，不僅需要確定工序的加工順序，還需合理分配機器資源，屬于復(fù)雜的NP-hard問題[13]。在實際生產(chǎn)中，調(diào)度目標(biāo)多種多樣，包括最小化最大完工時間、平均流經(jīng)時間、總拖期時間、機器負(fù)荷以及生產(chǎn)成本等。單一目標(biāo)往往難以全面反映車間調(diào)度的復(fù)雜性，因此多目標(biāo)優(yōu)化成為解決此類問題的必然選擇。

盡管已有許多研究探索了FJSP問題的求解方法，但大多數(shù)現(xiàn)有的算法在處理多目標(biāo)優(yōu)化時，仍然存在著計算時間長、精度不高等缺點[45]。近年來，遺傳算法（GA）作為一種常用的元啟發(fā)式算法，在求解FJSP問題中取得了較好的效果，但其在多目標(biāo)優(yōu)化中的應(yīng)用仍有很大的提升空間。因此，本文旨在針對這一問題提出一種改進(jìn)的遺傳算法，通過優(yōu)化算法參數(shù)和操作過程，提升FJSP問題在實際調(diào)度中的應(yīng)用效果。本文以S公司為案例，將改進(jìn)后的遺傳算法（IGA）與GA、粒子群算法（PSO）進(jìn)行對比驗證。

1 優(yōu)化模型建立

1.1 問題描述

成本是衡量生產(chǎn)調(diào)度優(yōu)化效果的關(guān)鍵指標(biāo)。S公司是一家綜合性機械制造企業(yè)，業(yè)務(wù)范圍廣泛，生產(chǎn)流程極為復(fù)雜。公司專注于生產(chǎn)各類汽車沖壓件和電阻焊接設(shè)備，其生產(chǎn)流程涉及n個工件、m道工序和p臺設(shè)備。每個工件包含多個工序，且這些工序需要在不同的設(shè)備上進(jìn)行加工。每道工序的加工時間和費用因設(shè)備而異，同時，工件還受到不同的釋放時間和交貨期約束。這種復(fù)雜的加工過程不僅增加了調(diào)度的難度，也對生產(chǎn)效率和資源利用提出了更高的要求。因此本文的目標(biāo)是構(gòu)建一個多目標(biāo)柔性作業(yè)車間調(diào)度優(yōu)化模型，旨在綜合考慮完工時間、設(shè)備負(fù)荷、生產(chǎn)成本等因素，找到一個最優(yōu)的生產(chǎn)調(diào)度方案。為確保生產(chǎn)調(diào)度的可行性和高效性，模型內(nèi)任意的工件i∈{1，…，n}，工序j∈{1，…，m}，設(shè)備k∈{1，…，p}需滿足以下關(guān)鍵約束條件：

Tij+Pij≤Ti（j+1）（1）

∑pk=1xijk=0ifk合法設(shè)備列表1ifk∈合法設(shè)備列表

∑ni=1∑mj=1xijk.Pij≤Mk（2）

Tij+Pij≤Mk或TijMk+Dk（3）

TijTi'j'+Pi'j'+Sk（4）

Ti1Ri+24（5）

TijStartTimeofShiftTij+Pij≤EndTimeofShift（6）

其中，Tij表示工件i的第j道工序的開始時間；Pij表示該工序的加工時間；n表示工件總數(shù)；m表示工序總數(shù)；p表示設(shè)備總數(shù)；xijk是一個二進(jìn)制變量，表示工件i的第j道工序是否分配到設(shè)備k上；Mk表示設(shè)備k的可用時間；Dk表示設(shè)備k的維修保養(yǎng)時間；Sk表示設(shè)備k的換型準(zhǔn)備時間；Ri表示工件i的訂單下單時間。

約束（1）表示每個工件的工序必須按照預(yù)設(shè)的固定順序執(zhí)行；約束（2）表示每道工序必須分配到一臺合法的設(shè)備上，且每臺設(shè)備同一時間只能加工一個工序；約束（3）表示設(shè)備在規(guī)定的維保時間段內(nèi)不能進(jìn)行生產(chǎn)操作；約束（4）表示設(shè)備切換任務(wù)時，需考慮換型準(zhǔn)備時間；約束（5）表示工序安排不能早于訂單下單時間，且需在下單24小時后才能排產(chǎn)；約束（6）表示設(shè)備工作時間需符合日班或夜班的時間范圍，遵守勞動法規(guī)和生產(chǎn)管理規(guī)定。

1.2 模型建立

本文設(shè)定柔性車間生產(chǎn)調(diào)度優(yōu)化模型的目標(biāo)函數(shù)是最小化總成本，包括能耗成本、人工成本、計件成本、庫存成本和延遲成本，目標(biāo)函數(shù)如下所示：

MinC=∑ni=1∑mj=1∑pk=1（Cenergy，ijk+Clabor，ijk+Cpiece，ijk+Chold，ijk+Cdelay，ijk）（7）

其中各項成本計算方式如下：

Cenergy，ijk=∑i，j，kEijk×Penergy×Fdate（8）

Clabor，ijk=∑i，j，kRk×Tijk（9）

Cpiece，ijk=∑i，j，kQi×Ppiecework（10）

Chold，ijk=∑iQi×Pinventory×Iij（11）

Cdelay，ijk=∑iQi×Di×δ（12）

式（8）表示能耗成本，式（9）表示人工成本，式（10）表示計件成本，式（11）表示庫存成本，式（12）表示延遲成本。其中，Eijk表示設(shè)備k處理工件i的工序j的能耗，Penergy是能耗價格基準(zhǔn)，F(xiàn)date是日期價格因子，Tijk是設(shè)備k處理工件i的工序j的工時，Rk是設(shè)備k的人工工時費率，Qi是工件i數(shù)量，Ppiecework是計件成本單價，Pinventory是庫存成本單價，Iij是工件i的工序j和j+1之間的間隔時間，Di是工件i的延遲天數(shù)，Di是工件i的延遲天數(shù)，δ為訂單延遲成本懲罰系數(shù)。

2 改進(jìn)遺傳算法設(shè)計

在FJSP問題中，GA雖然具有良好的全局搜索能力，但在處理多目標(biāo)優(yōu)化問題時，存在收斂速度較慢、容易陷入局部最優(yōu)等不足。為了克服這些缺點，本文通過引入輪盤賭選擇策略、精英保留策略和局部搜索機制，改進(jìn)GA模型求解問題。

2.1 染色體編碼和解碼設(shè)計

針對FJSP問題，染色體編碼需能夠表示每個工序在每臺設(shè)備上的分配情況。本文設(shè)計了基于工序序列和設(shè)備序列的雙層編碼方式，第一層編碼為工序序列，每個基因表示一個工序，其值表示該工序分配的設(shè)備編號；第二層編碼基于設(shè)備的編碼，用于安排設(shè)備對工件進(jìn)行加工的順序。在基于工序序列的編碼中，工件按1到n的順序編號，并通過隨機全排列為工件分配編碼。該編碼反映了工件的處理優(yōu)先級。如圖1所示，若工件1的編碼排在工件4之前，則工件1的優(yōu)先級較高，設(shè)備空閑且滿足條件時，優(yōu)先加工工件1。這種編碼方式具有直觀、簡便、解碼成本低等優(yōu)勢。

2.2 初始群體設(shè)計

初始種群的質(zhì)量直接影響算法的收斂速度和最終解的質(zhì)量。本文采用啟發(fā)式規(guī)則生成初始種群，即根據(jù)工序的優(yōu)先級和設(shè)備的可用性，優(yōu)先選擇能夠最小化當(dāng)前工序等待時間的設(shè)備進(jìn)行分配。具體步驟包括任務(wù)排序、工序分配和隨機擾動，確保初始種群具有高質(zhì)量和多樣性。

2.3 適應(yīng)度函數(shù)設(shè)計

適應(yīng)度函數(shù)用于評估個體優(yōu)劣。本文適應(yīng)度函數(shù)綜合考慮最大完工時間、設(shè)備負(fù)荷和生產(chǎn)成本等多個因素。適應(yīng)度值越大，表示個體的總成本越低，優(yōu)化效果越好。具體公式如下：

F=ω11Tmax+ω21MachineLoad+ω31TotalCost（13）

其中，ω1、ω2和ω3是權(quán)重系數(shù)，用于平衡不同目標(biāo)的重要性，Tmax為最大完工時間，MachineLoad為設(shè)備負(fù)荷，TotalCost為生產(chǎn)總成本。

2.4 選擇、交叉、變異操作

選擇操作用于從當(dāng)前種群中選擇適應(yīng)度較高的個體進(jìn)入下一代種群，以保留優(yōu)良的遺傳信息。本文采用輪盤賭選擇方法，通過概率機制優(yōu)先選擇適應(yīng)度高的個體，同時保留一定的隨機性，避免算法過早收斂。具體步驟如下：

首先，計算每個個體的適應(yīng)度值Fi，并根據(jù)適應(yīng)度值計算其在種群中的選擇概率Pi。

Pi=Fi∑Nt=1Ft（14）

其中，N是種群規(guī)模，∑Nt=1Ft是種群中所有個體適應(yīng)度值的總和。因此適應(yīng)度較高的個體將獲得更高的選擇概率，從而更有可能被選中進(jìn)入下一代種群。

然后根據(jù)計算得到的選擇概率Pi，構(gòu)建輪盤賭模型。該模型將種群中的每個個體視為輪盤上的一個扇區(qū)，扇區(qū)的大小與其選擇概率Pi成正比。算法通過隨機生成一個介于0和1之間的數(shù)值r（r～U（0，1）），并根據(jù)這個隨機值在輪盤上選擇對應(yīng)的個體。具體步驟如下：（1）初始化累積概率S=0；（2）遍歷種群中的每個個體，依次計算累積概率S=S+Pi；（3）當(dāng)累積概率S超過隨機值r時，選擇當(dāng)前個體進(jìn)入下一代種群。通過輪盤賭選擇機制，適應(yīng)度較高的個體有更高的概率被選中，但同時也保留了一定的隨機性，使得適應(yīng)度較低的個體也有機會被選中。

交叉操作通過結(jié)合兩個父代個體的遺傳信息，生成具有新特征的子代個體，從而顯著提升種群的多樣性。在此基礎(chǔ)上，本文采用單點交叉與多點交叉相結(jié)合的方法，既保留了父代優(yōu)良特征，又通過基因片段的交換引入新的遺傳信息，有效增強了算法的全局探索能力。與此同時，變異操作通過隨機改變個體的某些基因，進(jìn)一步引入新的遺傳信息，打破種群的同質(zhì)化，有效防止算法陷入局部最優(yōu)。為此，本文設(shè)計了隨機變異與交換變異相結(jié)合的策略。隨機變異通過隨機改變基因值引入新的遺傳特征，而交換變異通過基因位置的交換調(diào)整個體的結(jié)構(gòu)特征。這種結(jié)合方式不僅增強了種群的多樣性，還顯著提升了算法的局部搜索能力，使其在全局搜索與局部優(yōu)化之間取得了良好的平衡。

2.5 精英保留和局部搜索

在IGA算法中，精英保留策略用于確保當(dāng)前最優(yōu)解在進(jìn)化過程中得以保留。具體操作為：在每一代種群中，篩選出適應(yīng)度最高的若干個體（通常為種群規(guī)模的一定比例，如10%），并將這些精英個體直接復(fù)制到下一代種群中。這一策略為算法的收斂提供了穩(wěn)定基礎(chǔ)，避免因交叉和變異操作導(dǎo)致優(yōu)質(zhì)解丟失。例如，假設(shè)種群規(guī)模為N，則每代保留的精英個體數(shù)量為Nelite=N×0.1。這些精英個體直接進(jìn)入下一代種群，為算法的收斂提供了穩(wěn)定基礎(chǔ)。

而局部搜索機制在每一代種群中對部分個體進(jìn)行優(yōu)化，以進(jìn)一步提升解的質(zhì)量。對于工序序列，隨機選取兩個工序j和j'，并交換它們的加工順序。通過計算新解的適應(yīng)度F1，并與原解的適應(yīng)度F0進(jìn)行比較，如果F1lt;F0，則接受調(diào)整；否則恢復(fù)原序列。對于設(shè)備分配，隨機選擇某個工序j，嘗試將其重新分配到其他可用設(shè)備k'上，并評估新解的適應(yīng)度。若新設(shè)備分配能降低總成本或縮短完工時間，即F1lt;F0，則接受新的設(shè)備分配。

為了更好地平衡全局搜索和局部優(yōu)化，局部搜索的范圍需根據(jù)種群多樣性動態(tài)調(diào)整。設(shè)種群多樣性指標(biāo)為Div，可以通過計算種群中所有個體基因序列之間的平均漢明距離來衡量，即Div=2N（N-1）∑Ni=1∑jgt;idij，其中dij表示個體i和j之間的漢明距離。當(dāng)Div數(shù)值較低時，表示種群中個體差異較小，此時擴大搜索范圍以避免算法陷入局部最優(yōu)；而當(dāng)Div數(shù)值較高時，表示種群中存在較多的多樣性，此時縮小搜索范圍以集中優(yōu)化優(yōu)質(zhì)解。通過這種動態(tài)調(diào)整機制，IGA算法能夠在全局搜索和局部優(yōu)化之間取得良好的平衡。

3 驗證與分析

3.1 實驗設(shè)置

本文采用的數(shù)據(jù)直接來源于S公司的實際生產(chǎn)場景，涵蓋了從產(chǎn)品設(shè)計到車間調(diào)度以及物流配送等關(guān)鍵環(huán)節(jié)。S公司生產(chǎn)流程復(fù)雜，涉及P0001至P0006 6個產(chǎn)品，每種產(chǎn)品需經(jīng)過8道工序，其中工序1、4和7為添料工序，其余為普通工序。實驗設(shè)置綜合考慮了各產(chǎn)品的工序需求、倉儲成本系數(shù)、訂單延遲成本系數(shù)，以及設(shè)備的作業(yè)時間和維保時間等關(guān)鍵參數(shù)。這些數(shù)據(jù)均來源于S公司的車間生產(chǎn)記錄和訂單管理系統(tǒng)，確保本實驗數(shù)據(jù)的可靠性和可操作性。表1詳細(xì)列出了各產(chǎn)品在八道工序中的加工需求及關(guān)鍵指標(biāo)，反映了不同產(chǎn)品的成本側(cè)重點。

為了驗證算法的有效性，本文將IGA、GA和PSO三種算法進(jìn)行比較。IGA算法參數(shù)設(shè)置如下：種群規(guī)模為100，交叉概率為0.7，變異概率為0.1，選擇比例為0.8，變異算子改變的時點為30。GA算法設(shè)置如下：種群規(guī)模為100，交叉概率為0.7，變異概率為0.1，選擇比例0.8。PSO算法參數(shù)設(shè)置如下：種群規(guī)模100。為了確保模型在合理時間內(nèi)逐步趨近最優(yōu)解，最大迭代次數(shù)設(shè)置為40。

3.2 實驗結(jié)果分析

結(jié)果如圖2所示，IGA在多目標(biāo)柔性作業(yè)車間調(diào)度問題表現(xiàn)出顯著的優(yōu)越性。IGA的運行時間僅為0.34分鐘，顯著低于PSO的1.55分鐘和GA的0.42分鐘，顯示出更高的計算效率。在總成本方面，IGA達(dá)到575598.625，低于PSO的578569.6和GA的575598。IGA在第18代后穩(wěn)定在最優(yōu)值，收斂速度顯著快于PSO和GA，這表明IGA在全局搜索和局部優(yōu)化能力上具有顯著優(yōu)勢。因此本文的IGA算法在實際生產(chǎn)調(diào)度中的應(yīng)用價值，可為柔性作業(yè)車間生產(chǎn)調(diào)度提供高質(zhì)量的解決方案。

參考文獻(xiàn)

［1］姜一嘯，吉衛(wèi)喜，何鑫，等.基于改進(jìn)非支配排序遺傳算法的多目標(biāo)柔性作業(yè)車間低碳調(diào)度[J].中國機械工程，2022，33（21）：25642577.

[2]李益兵，黃煒星，吳銳.基于改進(jìn)人工蜂群算法的多目標(biāo)綠色柔性作業(yè)車間調(diào)度研究[J].中國機械工程，2020，31（11）：13441350+1385.

[3]張超勇，董星，王曉娟，等.基于改進(jìn)非支配排序遺傳算法的多目標(biāo)柔性作業(yè)車間調(diào)度[J].機械工程學(xué)報，2010，46（11）：156164.

[4]Meeran S，Morshed M S.A hybrid genetic tabu search algorithm for solving job shop scheduling problems：a case study[J].Journal of intelligent manufacturing，2012，23：10631078.

[5]李益兵，黃煒星，吳銳.基于改進(jìn)人工蜂群算法的多目標(biāo)綠色柔性作業(yè)車間調(diào)度研究[J].中國機械工程，2020，31（11）：13441350+1385.