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

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

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

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

0 引言

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

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

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

1.1 問(wèn)題描述

成本是衡量生產(chǎn)調(diào)度優(yōu)化效果的關(guān)鍵指標(biāo)。S公司是一家綜合性機(jī)械制造企業(yè)，業(yè)務(wù)范圍廣泛，生產(chǎn)流程極為復(fù)雜。公司專(zhuān)注于生產(chǎn)各類(lèi)汽車(chē)沖壓件和電阻焊接設(shè)備，其生產(chǎn)流程涉及n個(gè)工件、m道工序和p臺(tái)設(shè)備。每個(gè)工件包含多個(gè)工序，且這些工序需要在不同的設(shè)備上進(jìn)行加工。每道工序的加工時(shí)間和費(fèi)用因設(shè)備而異，同時(shí)，工件還受到不同的釋放時(shí)間和交貨期約束。這種復(fù)雜的加工過(guò)程不僅增加了調(diào)度的難度，也對(duì)生產(chǎn)效率和資源利用提出了更高的要求。因此本文的目標(biāo)是構(gòu)建一個(gè)多目標(biāo)柔性作業(yè)車(chē)間調(diào)度優(yōu)化模型，旨在綜合考慮完工時(shí)間、設(shè)備負(fù)荷、生產(chǎn)成本等因素，找到一個(gè)最優(yōu)的生產(chǎn)調(diào)度方案。為確保生產(chǎn)調(diào)度的可行性和高效性，模型內(nèi)任意的工件i∈{1，…，n}，工序j∈{1，…，m}，設(shè)備k∈{1，…，p}需滿(mǎn)足以下關(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道工序的開(kāi)始時(shí)間；Pij表示該工序的加工時(shí)間；n表示工件總數(shù)；m表示工序總數(shù)；p表示設(shè)備總數(shù)；xijk是一個(gè)二進(jìn)制變量，表示工件i的第j道工序是否分配到設(shè)備k上；Mk表示設(shè)備k的可用時(shí)間；Dk表示設(shè)備k的維修保養(yǎng)時(shí)間；Sk表示設(shè)備k的換型準(zhǔn)備時(shí)間；Ri表示工件i的訂單下單時(shí)間。

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

1.2 模型建立

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

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

其中各項(xiàng)成本計(jì)算方式如下：

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

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

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

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

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

2.2 初始群體設(shè)計(jì)

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

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

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

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

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

2.4 選擇、交叉、變異操作

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

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

Pi=Fi∑Nt=1Ft（14）

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

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

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

2.5 精英保留和局部搜索

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

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

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

3 驗(yàn)證與分析

3.1 實(shí)驗(yàn)設(shè)置

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

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

3.2 實(shí)驗(yàn)結(jié)果分析

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

參考文獻(xiàn)

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

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

[3]張超勇，董星，王曉娟，等.基于改進(jìn)非支配排序遺傳算法的多目標(biāo)柔性作業(yè)車(chē)間調(diào)度[J].機(jī)械工程學(xué)報(bào)，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è)車(chē)間調(diào)度研究[J].中國(guó)機(jī)械工程，2020，31（11）：13441350+1385.