基于改進(jìn)NSGAII算法的渦流紡車間調(diào)度方法

摘 要：為應(yīng)對(duì)渦流紡車間生產(chǎn)向小批量多品種生產(chǎn)模式轉(zhuǎn)變的發(fā)展趨勢(shì)，對(duì)渦流紡車間生產(chǎn)調(diào)度進(jìn)行研究。通過(guò)分析金華某渦流紡企業(yè)訂單生產(chǎn)情況，建立了以最小化最大完成時(shí)間、最小化逾期損失和最小化改機(jī)次數(shù)為目標(biāo)的渦流紡生產(chǎn)調(diào)度模型。為避免NSGAII陷入早熟收斂的情況，提出一種改進(jìn)的NSGAII算法（INSGAII_SAA）對(duì)渦流紡車間調(diào)度模型求解。利用啟發(fā)式規(guī)則初始化種群、自適應(yīng)選擇交叉變異算子以及融合模擬退火算法（SAA）的方法，有效降低解空間的冗余程度，提高求解效率并得到全局最優(yōu)解。另外，使用NSGAII、SAA、INSGAII_SAA、MOSAA以及MOPSO求解，對(duì)比該渦流紡企業(yè)訂單數(shù)據(jù)來(lái)驗(yàn)證求解模型和改進(jìn)算法的有效性，結(jié)果表明：相較于NSGAII，所提出的INSGAII_SAA最大完成時(shí)間平均減少了8.7%、逾期損失平均減少59.89%、改機(jī)次數(shù)平均減少34.91%，具有較好的調(diào)度效果。研究方法能較好地實(shí)現(xiàn)渦流紡生產(chǎn)科學(xué)調(diào)度，有效降低企業(yè)生產(chǎn)管理成本。

關(guān)鍵詞：渦流紡；紡紗車間；生產(chǎn)調(diào)度；多目標(biāo)優(yōu)化；改進(jìn)NSGAII

中圖分類號(hào)：TS111.8

文獻(xiàn)標(biāo)志碼：A

文章編號(hào)：1009-265X（2025）02-0118-12

隨著中國(guó)經(jīng)濟(jì)社會(huì)發(fā)展，消費(fèi)者對(duì)紡織品的要求越來(lái)越高，市場(chǎng)需求多樣化特征顯著。面對(duì)多樣化的市場(chǎng)需求，渦流紡生產(chǎn)從產(chǎn)品種類單一逐漸向小批量多品種生產(chǎn)模式轉(zhuǎn)變^［1］。小批量、多品種的渦流紡生產(chǎn)模式具有多約束、多目標(biāo)的特點(diǎn)，屬于NP-hard問(wèn)題^［2］，是一種并行機(jī)調(diào)度問(wèn)題。目前大多數(shù)渦流紡企業(yè)仍依靠人工方式安排車間生產(chǎn)，這一方式可能會(huì)制約小批量多品種模式的生產(chǎn)效率。

目前雖已有不少學(xué)者針對(duì)傳統(tǒng)紡紗生產(chǎn)調(diào)度問(wèn)題進(jìn)行研究，但對(duì)于渦流紡車間調(diào)度問(wèn)題研究較少。潘欣明等^［3］針對(duì)小批量多品種的色紡生產(chǎn)人工調(diào)度困難的問(wèn)題，建立了一個(gè)色紡細(xì)紗工序生產(chǎn)調(diào)度模型，提出了一種改進(jìn)蟻群算法用于該模型求解；Ma等^［4］研究資源節(jié)約型的紡織生產(chǎn)模式，使用粒子群算法解決了具有資源節(jié)約問(wèn)題的綜合生產(chǎn)調(diào)度問(wèn)題；Krishnamoorthy等^［5］使用LSPM-WC算法解決了紡紗生產(chǎn)中AVG運(yùn)行效率低的問(wèn)題。上述研究通過(guò)改進(jìn)已有單目標(biāo)算法，實(shí)現(xiàn)對(duì)傳統(tǒng)紗線生產(chǎn)調(diào)度模型求解且達(dá)到理想效果。高詠珊等^［6］為提高細(xì)紗車間自動(dòng)接頭小車的調(diào)度效率，建立了以細(xì)紗生產(chǎn)產(chǎn)量最大化為目標(biāo)函數(shù)的細(xì)紗接頭調(diào)度模型并使用改進(jìn)的遺傳算法進(jìn)行求解；章國(guó)政^［7］為提高紡紗車間生產(chǎn)效率，建立了以訂單準(zhǔn)時(shí)交付、車間總紡紗時(shí)間最短并且翻改品種次數(shù)最少為目標(biāo)的優(yōu)化模型并使用遺傳算法進(jìn)行求解；董平軍等^［8］針對(duì)縫制車間訂單批量小需求個(gè)性化高的問(wèn)題構(gòu)建考慮員工學(xué)習(xí)—遺忘效應(yīng)的混合流水分批調(diào)度模型，并設(shè)計(jì)了一種非支配遺傳算法對(duì)模型求解；周亞勤等^［9］構(gòu)建了考慮織造車間多因素的生產(chǎn)調(diào)度模型，并使用改進(jìn)遺傳算法求解；Li等^［10］采用遺傳算法解決了紡紗和紡織品批量染色生產(chǎn)調(diào)度問(wèn)題。上述研究通過(guò)對(duì)多目標(biāo)優(yōu)化的遺傳算法進(jìn)行改進(jìn)，實(shí)現(xiàn)了多目標(biāo)智能算法在紡織企業(yè)的應(yīng)用，但主要是針對(duì)傳統(tǒng)環(huán)錠紡或織造的生產(chǎn)過(guò)程的研究，并不適用于求解渦流紡生產(chǎn)調(diào)度問(wèn)題。渦流紡企業(yè)面對(duì)小批量多品種的訂單需求，常難以得到科學(xué)合理的調(diào)度方案。

本文對(duì)渦流紡車間生產(chǎn)調(diào)度進(jìn)行研究，通過(guò)分析金華某渦流紡企業(yè)訂單生產(chǎn)情況，建立以最小化最大完成時(shí)間、最小化逾期損失和最小化改機(jī)次數(shù)為目標(biāo)的渦流紡生產(chǎn)調(diào)度模型，提出一種改進(jìn)的NSGAII算法（Fusion of SAA algorithm to improve NSGAII，INSGAII_SAA），通過(guò)建立啟發(fā)式規(guī)則初始化種群，降低初始種群冗余程度，并引入自適應(yīng)選擇交叉變異算子機(jī)制以及融合SAA提高算法的局部搜索和全局搜索能力，避免求解過(guò)程陷入早熟收斂并獲得最優(yōu)的調(diào)度方案，最后通過(guò)企業(yè)實(shí)際訂單數(shù)據(jù)仿真實(shí)驗(yàn)，驗(yàn)證改進(jìn)算法的可行性。

1 渦流紡紗生產(chǎn)流程分析

與傳統(tǒng)紡紗車間相比，渦流紡車間具有工藝流程短、制成率高、原料損耗低^［11］等特點(diǎn)。為研究渦流紡車間小批量多品種生產(chǎn)調(diào)度，本文以金華某渦流紡企業(yè)生產(chǎn)車間為研究對(duì)象，展示了其渦流紡紗生產(chǎn)工藝路線，如圖1所示。

紡紗生產(chǎn)中，紗線生產(chǎn)效率是紡紗企業(yè)生產(chǎn)技術(shù)管理的綜合表現(xiàn)，可以代表企業(yè)的管理水平和生產(chǎn)能力，而熟條加工為成品紗線的效率高低對(duì)整個(gè)紗線生產(chǎn)影響較大，因此本文主要研究由熟條到成品紗線這一關(guān)鍵工序的調(diào)度問(wèn)題。生產(chǎn)調(diào)度流程如圖2所示。

2 渦流紡車間調(diào)度優(yōu)化模型

2.1 模型定義與假設(shè)

為簡(jiǎn)化渦流紡紗生產(chǎn)車間調(diào)度模型，便于描述，對(duì)模型進(jìn)行以下定義與假設(shè)：

1）n個(gè)生產(chǎn)批次，批次G∈｛1，2，3…，n｝。t種紗線，紗線品種P∈｛1，2，3…，t｝，屬于紗線P的訂單數(shù)為nP，∑tP=1nP=n，即按不同訂單中的紗線品種將訂單拆分為若干批次，且每批次只有一種紗線。

2）有z臺(tái)相同的渦流紡紗機(jī)，設(shè)備m∈｛1，2，3，…，z｝。每臺(tái)渦流紡紗機(jī)均可對(duì)紗線P生產(chǎn)加工，加工時(shí)一臺(tái)渦流紡紗機(jī)同一時(shí)刻只能加工一種紗線，加工時(shí)間只與紗線品種有關(guān)。

3）同一臺(tái)紡紗設(shè)備上，只有在上一批次加工任務(wù)完成后才能進(jìn)行下一批次生產(chǎn)，即只有在設(shè)備空閑且設(shè)備狀態(tài)良好的情況下才能接受新的加工任務(wù)，在加工過(guò)程中不允許中斷。

4）用于紡紗生產(chǎn)的原料供給充足，不影響正常生產(chǎn)。

5）初始零時(shí)刻，所有紡紗設(shè)備均無(wú)故障，處于空閑且可正常使用狀態(tài)。

6）相鄰工序間的準(zhǔn)備時(shí)間忽略不計(jì)。

7）初始時(shí)刻，所有待加工的熟條條筒數(shù)量充足，因此不會(huì)因?yàn)槭鞐l不足影響渦流紡紗設(shè)備的正常生產(chǎn)。

8）訂單優(yōu)先級(jí)規(guī)定，每個(gè)訂單根據(jù)合同約定的逾期懲罰確定生產(chǎn)優(yōu)先級(jí)，訂單被拆分為若干個(gè)生產(chǎn)批次后，其對(duì)應(yīng)的生產(chǎn)批次將繼承該訂單的優(yōu)先級(jí)。

2.2 多目標(biāo)優(yōu)化模型

2.2.1 約束條件

為更好地還原實(shí)際生產(chǎn)場(chǎng)景，為優(yōu)化模型建立以下約束條件：

1）改機(jī)約束

設(shè)備m上的加工任務(wù)i完成后，繼續(xù)下一加工任務(wù)i+1時(shí)，若兩次加工的產(chǎn)品品種相同，不需要進(jìn)行改機(jī)操作，決策變量為0；若兩次加工產(chǎn)品品種不同，此時(shí)應(yīng)進(jìn)行改機(jī)操作，決策變量為1。

GPm，i=0，Pm，i=Pm，i+1

1，Pm，i≠Pm，i+1（1）

式中：m表示加工設(shè)備編號(hào)；i表示設(shè)備m 加工任務(wù)中的生產(chǎn)順序編號(hào)；Pm，i表示在設(shè)備m上加工順序?yàn)閕的產(chǎn)品品種。

gm，i+1=cm，i， GPm，i=0

jm，i+1，且jm，i+1≥cm，i，GPm，i=1（2）

gm，i+1表示在設(shè)備m上生產(chǎn)加工順序?yàn)閕+1的任務(wù)前的改機(jī)完成時(shí)刻。若設(shè)備m不需要進(jìn)行改機(jī)操作，此時(shí)gm，i+1為cm，i，cm，i為加工順序?yàn)閕的任務(wù)加工完成時(shí)刻；若設(shè)備m需要進(jìn)行改機(jī)操作，此時(shí)gm，i+1為jm，i+1，jm，i+1為改機(jī)完成時(shí)刻。

2）加工順序約束

對(duì)于需要先后在同一臺(tái)設(shè)備加工的任務(wù)須滿足如下約束：

cm，i+1-Tm，i+1≥max｛cm，i，gm，i+1｝（3）

式中：m為設(shè)備編號(hào)，cm，i+1和Tm，i+1分別為加工順序?yàn)閕+1生產(chǎn)任務(wù)在設(shè)備m加工完成時(shí)刻和在設(shè)備m上加工時(shí)長(zhǎng)。

3）訂單完成時(shí)間約束

該約束表示訂單完成時(shí)間不小于訂單中所有紗線完成生產(chǎn)所用時(shí)間。

Ck≥∑zm=1∑vmi=1∑rk=1（Tm，i+T′m，i）Xm，iPm，kRi，k（4）

式中：Tm，i表示在加工設(shè)備m上加工紗線i需要的時(shí)間；T′m，i+1表示設(shè)備m上紗線i完成加工時(shí)已用的改機(jī)時(shí)間；Xm，i表示紗線i是否在設(shè)備m上加工；Pm，k表示訂單k是否在設(shè)備m上生產(chǎn)；Ri，k紗線i是否屬于訂單k；Ck為訂單k完成時(shí)間。

4）設(shè)備資源約束

使用的加工設(shè)備數(shù)量不超過(guò)車間設(shè)備總數(shù)：

M≥∑zi=1mi（5）

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

為滿足渦流紡車間調(diào)度需求，提高渦流紡紗車間生產(chǎn)效率，本文為渦流紡紗車間調(diào)度問(wèn)題建立了3個(gè)目標(biāo)函數(shù)，分別為最小化最大完成時(shí)間、最小化逾期損失、最小化改機(jī)次數(shù)。

2.2.2.1 最小化最大完成時(shí)間

最大完成時(shí)間是指某個(gè)訂單中的最后一批紗線生產(chǎn)完成的時(shí)間，是企業(yè)生產(chǎn)效率高低的重要參考指標(biāo)，因此將最小化最大完成時(shí)間作為目標(biāo)函數(shù)，如式 （6）：

f1=min（max1≤i≤r（Ci））（6）

式中：r為訂單總數(shù)；Ci為訂單i完成時(shí)間，f1為最大完成時(shí)間。

2.2.2.2 最小化逾期損失

紡紗企業(yè)的訂單量直接受到市場(chǎng)供需關(guān)系的影響^［12］，當(dāng)市場(chǎng)對(duì)產(chǎn)品的需求大于產(chǎn)品供應(yīng)時(shí)，即使車間各生產(chǎn)設(shè)備滿負(fù)荷運(yùn)行也無(wú)法避免出現(xiàn)訂單逾期交付的情況。因此，為能夠更好符合實(shí)際生產(chǎn)場(chǎng)景和反映逾期損失與逾期時(shí)間的關(guān)系，本文建立了兩者的系數(shù)關(guān)系。Ci - Di為訂單i超出合同約定日期Di的時(shí)間；hi為訂單i的權(quán)重值，可根據(jù)約定的逾期懲罰設(shè)置。訂單i的逾期損失用hi·（Ci - Di）表示；f2為訂單逾期損失。

f2=min（∑ni=1hi·（Ci-Di）），Ci≥Di（7）

2.2.2.3 最小化改機(jī)次數(shù)

減少設(shè)備改機(jī)次數(shù)能夠提高紡紗生產(chǎn)效率，降低不利影響發(fā)生的概率，因此將最小化改機(jī)次數(shù)作為優(yōu)化目標(biāo)之一。

f3=min（∑zm=1∑vmi=1GPm，i）（8）

式中：z為車間設(shè)備總數(shù)；i為設(shè)備m待加工任務(wù)中的順序編號(hào)；vm為設(shè)備m上加工產(chǎn)品品種數(shù)量；GPm，i為設(shè)備m在生產(chǎn)完成加工順序?yàn)閕的任務(wù)后是否繼續(xù)生產(chǎn)相同品種產(chǎn)品；f3為設(shè)備改機(jī)次數(shù)。

2.2.3 評(píng)價(jià)函數(shù)

由于渦流紡車間調(diào)度問(wèn)題具有多個(gè)優(yōu)化目標(biāo)且實(shí)際生產(chǎn)過(guò)程中各目標(biāo)無(wú)法同時(shí)達(dá)到最理想狀態(tài)，因此設(shè)立總體優(yōu)化目標(biāo)評(píng)價(jià)函數(shù)如式 （9）：

F=αf1+βf2+δf3（9）

式中：F為評(píng)價(jià)函數(shù)，f1、f2、f3分別為上述目標(biāo)函數(shù)，α、β、δ為各目標(biāo)函數(shù)權(quán)重值。

3 改進(jìn)NSGAII算法

NSGAII算法（Non-Dominated Sorting Genetic Algorithm II）是一種有效的用于解決多目標(biāo)優(yōu)化問(wèn)題的進(jìn)化算法^［13］，但算法求解過(guò)程對(duì)參數(shù)較為敏感，若解空間范圍較大，也可能會(huì)出現(xiàn)早熟而陷入局部最優(yōu)的情況，為此本文針對(duì)渦流紡車間調(diào)度問(wèn)題提出一種改進(jìn)的NSGAII（INSGAII_SAA）。

3.1 INSGAII_SAA流程圖

INSGAII_SAA流程如圖3所示。

INSGAII_SAA執(zhí)行步驟如下：

1）初始化算法參數(shù)并通過(guò)啟發(fā)式規(guī)則生成初始種群。設(shè)置最大迭代次數(shù)、交叉和變異概率以及SAA各參數(shù)并。

2）計(jì)算種群適應(yīng)度值，保留最優(yōu)帕累托解集。

3）使用精英保留策略對(duì)種群進(jìn)行選擇。

4）對(duì)染色體進(jìn)行交叉變異操作。校正并修復(fù)進(jìn)化后的染色體編碼，防止產(chǎn)生不可行解，合并父代與子代種群。

5）對(duì)結(jié)果中擁擠距離最大的個(gè)體進(jìn)行SAA局部搜索，得到非支配集合Pareto_best和支配集合Pareto1，用Pareto_best代替原種群中支配等級(jí)最低的個(gè)體。

6）將Pareto1與原Pareto合并，更新當(dāng)前種群的Pareto集合。

7）判斷是否達(dá)到終止條件。達(dá)到最大迭代次數(shù)則輸出最優(yōu)解，否則，繼續(xù)執(zhí)行步驟2）至步驟6）。

3.2 INSGAII_SAA

3.2.1 啟發(fā)式初始化種群

初始種群的質(zhì)量影響著算法的性能^［14］。為了降低初始種群冗余程度，提高算法運(yùn)行效率和解的質(zhì)量，本文為初始化種群建立以下啟發(fā)式規(guī)則。

規(guī)則1：加工順序優(yōu)先規(guī)則。根據(jù)不同交期時(shí)間安排加工順序，交期時(shí)間最近則最先安排生產(chǎn)。當(dāng)交期時(shí)間相同或相近時(shí)，根據(jù)訂單的權(quán)重值安排生產(chǎn)順序，權(quán)重值越大越優(yōu)先生產(chǎn)。

規(guī)則2：設(shè)備選擇優(yōu)先規(guī)則。記錄各設(shè)備換品種次數(shù)，并設(shè)置閾值，在設(shè)備改機(jī)次數(shù)較多的情況下，優(yōu)先選擇改機(jī)次數(shù)較少的生產(chǎn)設(shè)備，以均衡各設(shè)備改機(jī)次數(shù)。

染色體由訂單、紗線品種、加工設(shè)備和加工順序4部分組成。其中訂單部分與紗線品種部分關(guān)聯(lián)生成，例如訂單1包含紗線1數(shù)量為2噸、紗線2數(shù)量為1噸、紗線3數(shù)量為2噸，交付時(shí)間為3天；訂單2包含紗線2數(shù)量為2噸、紗線3數(shù)量為1噸、紗線4數(shù)量為2噸，交付時(shí)間為2天，如圖4所示。染色體長(zhǎng)度等于各訂單紗線需求數(shù)量之和。

在訂單—品種關(guān)聯(lián)編碼完成后，為各品種的紗線選擇生產(chǎn)設(shè)備并確定各品種紗線加工順序。圖5為加工設(shè)備與加工順序編碼。

3.2.2 自適應(yīng)選擇交叉變異算子

不同的交叉變異算子具有不同的全局搜索和局部搜索能力^［15］。本文根據(jù)渦流紡車間調(diào)度問(wèn)題特點(diǎn)，通過(guò)對(duì)交叉和變異算子選擇概率的動(dòng)態(tài)調(diào)整，使算法能夠根據(jù)當(dāng)前種群的適應(yīng)度情況，自適應(yīng)選擇合適的交叉變異算子。對(duì)適應(yīng)度較低的個(gè)體提高其選擇全局搜索能力較強(qiáng)的算子的概率，以增加種群多樣性，防止出現(xiàn)早熟現(xiàn)象；對(duì)適應(yīng)度較高的個(gè)體，則提高其選擇局部搜索能力較強(qiáng)的交叉變異算子的概率，提高收斂效率。最后通過(guò)輪盤賭的方式選擇算子對(duì)染色體進(jìn)行交叉變異操作。

式 （10）為交叉算子選擇概率自適應(yīng)調(diào)整函數(shù)，式 （11）為變異算子選擇概率自適應(yīng)調(diào)整函數(shù)。

p″ci=p′ci+0.1×（Fi—FA/FM-FA），F(xiàn)i≥FA

p″ci=p′ci-0.1×（FA-Fi/FM-FA），F(xiàn)ilt;FA（10）

p″mi=p′mi+0.1×（Fi—FA/FM-FA），F(xiàn)i≥FA

p″mi=p′mi-0.1×（FA-Fi/FM-FA），F(xiàn)ilt;FA（11）

式中：p″ci為調(diào)整后的交叉算子選擇概率，p′ci為初始交叉算子選擇概率，p″mi為調(diào)整后的變異算子選擇概率，p′mi為初始變異算子選擇概率，F(xiàn)i為個(gè)體i的適應(yīng)度，F(xiàn)M為種群最大適應(yīng)度，F(xiàn)A為種群平均適應(yīng)度。對(duì)調(diào)整后的算子選擇概率歸一化處理，如式 （12）。

pci=p″ci∑ni=1p″ci，pmi=p″mi∑ki=1p″mi（12）

式中：pci、pmi分別為第i個(gè)交叉算子和第i個(gè)變異算子被選擇的概率，n、k分別為交叉算子和變異算子的個(gè)數(shù)。

3.2.2.1 自適應(yīng)選擇交叉算子

1）加工設(shè)備基因段交叉操作

對(duì)適應(yīng)度較低的個(gè)體，增加均勻交叉算子被選擇的概率，對(duì)設(shè)備基因段進(jìn)行交叉操作。隨機(jī)產(chǎn)生一組與基因段長(zhǎng)度相等的二進(jìn)制串，根據(jù)二進(jìn)制串中1所對(duì)應(yīng)位置的基因進(jìn)行交叉操作。對(duì)適應(yīng)度較高的個(gè)體，增強(qiáng)保留父代特性的能力，增加單點(diǎn)交叉算子被選擇的概率，隨機(jī)選擇一個(gè)基因位，交換兩父代染色體該基因位后方的等位基因獲得子代染色體。

2）加工順序基因段交叉操作

為防止基因段中產(chǎn)生重復(fù)加工順序而造成求解錯(cuò)誤，采用OX交叉方式對(duì)加工順序基因段進(jìn)行交叉操作，即隨機(jī)選擇兩個(gè)基因位，復(fù)制兩基因位之間的基因到子代染色體，其他基因依次從另一條父代染色體中獲取。

3.2.2.2 自適應(yīng)選擇變異算子

基因變異操作是防止遺傳算法陷入局部最優(yōu)并提高收斂效率的重要步驟^［16］。對(duì)加工設(shè)備基因段和加工順序基因段分別進(jìn)行如下變異操作：

1）加工設(shè)備基因段

使用隨機(jī)變異的方式對(duì)加工設(shè)備基因段進(jìn)行變異操作。隨機(jī)選擇一個(gè)或多個(gè)基因位，將對(duì)應(yīng)基因位的設(shè)備編號(hào)替換為可用于加工該產(chǎn)品的設(shè)備集中的其他設(shè)備編號(hào)。

2）加工順序基因段

對(duì)適應(yīng)度較低的個(gè)體，為增強(qiáng)變異操作對(duì)父代染色體的變動(dòng)，增加全局搜索能力較強(qiáng)的倒序變異算子被選擇的概率，對(duì)基因段進(jìn)行變異操作。對(duì)適應(yīng)度較高的個(gè)體，增加局部搜索能力較強(qiáng)的交換變異算子被選擇的概率，降低對(duì)父代染色體的變動(dòng)，從而使NSGAII_SAA擁有更強(qiáng)的局部搜索能力。

3.2.3 融合SAA局部搜索

SAA具有搜索效率高的特點(diǎn)^［17］。利用SAA對(duì)Pareto1集合中擁擠距離最大的個(gè)體進(jìn)行局部搜索得到更優(yōu)解，同時(shí)，使用Akram等^［18］提出的逆線性降溫函數(shù)并采用均勻分布與指數(shù)分布的組合作為差解的接受準(zhǔn)則。具體步驟如下：

1）初始化SAA參數(shù)，設(shè)置初始溫度T、降溫系數(shù)及最低溫度Tmin等，并對(duì)Pareto集合中擁擠距離最大的個(gè)體進(jìn)行SAA搜索。

2）通過(guò)擾動(dòng)產(chǎn)生新解。若產(chǎn)生的新解嚴(yán)格支配原解或者與原解存在弱支配關(guān)系則將新解集保存至Pareto_best中；若新解完全支配于原解，則以一定概率接受新解，并將接受的新解存入Pareto1中，若不滿足接受概率則不接受新解，然后進(jìn)行降溫操作。

3）判斷T gt;Tmin，若成立則跳轉(zhuǎn)到2），否則SAA結(jié)束，輸出Pareto_best和Pareto1。

4 實(shí)驗(yàn)驗(yàn)證

為驗(yàn)證渦流紡車間調(diào)度模型以及改進(jìn)算法的有效性，選取金華某渦流紡紗廠訂單數(shù)據(jù)（見表1）進(jìn)行算法驗(yàn)證。使用NSGAII、SAA和INSGAII_SAA計(jì)算結(jié)果對(duì)比驗(yàn)證。

本文實(shí)驗(yàn)環(huán)境為：64位Windows11操作系統(tǒng)，IntelCorei5—1155G7CPU，16GB內(nèi)存；編程語(yǔ)言為Matlab；編譯器版本為MatlabR2018b。

4.1 改進(jìn)方法分析

4.1.1 啟發(fā)式初始化種群結(jié)果對(duì)比

在NSGAII的基礎(chǔ)上增加啟發(fā)式規(guī)則初始" 化種群，記為INSGAII_SAA（1）。圖6為NSGAII和INSGAII_SAA（1）迭代對(duì)比圖，從圖6可知，增加啟發(fā)式規(guī)則后，初始種群的冗余度低于原始算法。

圖7為NSGAII和INSGAII_SAA（1）求解得到的目標(biāo)函數(shù)值分布情況。從圖7可知，在原始NSGAII中添加啟發(fā)式規(guī)則初始化種群后，得到的目標(biāo)值總體上小于原始算法得到的目標(biāo)值。說(shuō)明加入啟發(fā)式規(guī)則在一定程度上改善了算法的解集分布。

4.1.2 自適應(yīng)選擇交叉變異算子結(jié)果對(duì)比

在INSGAII_SAA（1）基礎(chǔ)上引入自適應(yīng)選擇交叉變異算子機(jī)制，記為INSGAII_SAA（2）。圖8為INSGAII_SAA（1）與INSGAII_SAA（2）迭代對(duì)比圖，從圖8可知，在INSGAII_SAA（1）基礎(chǔ)上為算子增加自適應(yīng)機(jī)制后，算法的收斂效率和搜索能力有所提升。

圖9為INSGAII_SAA（1）和INSGAII_SAA（2）求解結(jié)果比較圖。從圖9可知，INSGAII_SAA（2）的求解結(jié)果相較于INSGAII_SAA（1），解集分布更為集中。這表明，為交叉變異算子添加自適應(yīng)選擇機(jī)制可以進(jìn)一步改善求解結(jié)果的分布情況。

4.1.3 融合SAA結(jié)果對(duì)比

在INSGAII_SAA（2）的基礎(chǔ)上融合SAA，構(gòu)成完整的INSGAII_SAA。圖10為INSGAII_SAA（2）與INSGAII_SAA迭代對(duì)比圖，從圖10可知，融合SAA后，INSGAII_SAA具有更優(yōu)秀的搜索能力。

圖11為INSGAII_SAA和INSGAII_SAA（2）的計(jì)算結(jié)果對(duì)比。從圖11中可知，INSGAII_SAA的解集分布總體優(yōu)于INSGAII_SAA（2）的解集分布，表明通過(guò)整合SAA后的改進(jìn)算法有更優(yōu)秀的局部搜索能力，可以得到更優(yōu)的解集。

4.1.4 Pareto前沿分布對(duì)比

圖12為NSGAII和INSGAII_SAA迭代過(guò)程中Pareto解集分布對(duì)比圖，種群大小和最大迭代次數(shù)均為100。由于傳統(tǒng)的SAA并未涉及Pareto解集，故不作對(duì)比。

如圖12所示，INSGAII_SAA所得的Pareto解集在解空間的分布情況優(yōu)于INSGAII解集，說(shuō)明INSGAII_SAA具有更優(yōu)秀的全局搜索能力和求解效果。

4.2 案例求解對(duì)比

圖13是使用SAA、NSGAII、INSGAII_SAA、MOSAA以及MOPSO對(duì)案例中訂單樣本求解100次的結(jié)果分布圖。因?qū)嶋H生產(chǎn)中訂單逾期造成的損失較大，改機(jī)操作消耗的人力物力較高，故式 （9）中α、β、δ分別取0.1、0.5、0.4。為便于對(duì)比，在求解結(jié)果中，依次根據(jù)β、δ、α數(shù)值大小選擇最優(yōu)個(gè)體。

從圖13可以看出，本文提出的INSGAII_SAA求解結(jié)果均優(yōu)于所選對(duì)比算法所得結(jié)果。

表2為各組訂單目標(biāo)函數(shù)值對(duì)比結(jié)果，其中B、W、A分別代表最優(yōu)值、最差值和平均值。

通過(guò)圖6—圖13可以看出，NSGAII_SAA初始種群冗余度低于原始算法。在迭代過(guò)程中，自適應(yīng)選擇算子和SAA的使用使得改進(jìn)算法具有更強(qiáng)的全局搜索和局部搜索能力。由表2可知，對(duì)于第1組和第4組結(jié)果可知，NSGAII_SAA相較于原始NSGAII，f1（最大完成時(shí)間）平均減少約8.7%，f2（逾期損失）平均降低約59.89%，f3（改機(jī)次數(shù)）平均減少約34.91%，NSGAII_SAA相較于SAA，求解結(jié)果中f1（最大完成時(shí)間）平均減少約19.18%，f2（逾期損失）平均降低約80.45%，f3（改機(jī)次數(shù)）平均減少約44.92%。當(dāng)算法具有較好的搜索能力時(shí)，可避免產(chǎn)生逾期損失，由第2組和第3組結(jié)果可知，改進(jìn)算法擁有更優(yōu)秀的搜索能力，不易陷入局部最優(yōu)的情況。

4.3 調(diào)度結(jié)果

圖14為各組訂單的最優(yōu)調(diào)度甘特圖，0代表改機(jī)操作。從圖14可知，NSGAII_SAA調(diào)度結(jié)果在保證逾期損失最小的同時(shí)，訂單完成時(shí)間較為均衡，且有效控制了改機(jī)次數(shù)。表3為訂單調(diào)度方案的實(shí)際交付日期及逾期損失，調(diào)度結(jié)果符合實(shí)際生產(chǎn)預(yù)期。

5 結(jié)論

本文著眼于渦流紡生產(chǎn)由品種單一化的生產(chǎn)模式向小批量多品種的生產(chǎn)模式發(fā)展趨勢(shì)，對(duì)小批量多品種的渦流紡生產(chǎn)調(diào)度問(wèn)題進(jìn)行研究，建立了包含多目標(biāo)的渦流紡車間調(diào)度模型，并基于NSGAII提出了INSGAII_SAA，再通過(guò)對(duì)渦流紡企業(yè)實(shí)際訂單信息進(jìn)行模擬計(jì)算，得到以下結(jié)論：

a）與所選對(duì)比算法相比，INSGAII_SAA具有更好的全局搜索能力和局部搜索能力。在對(duì)比算法陷入局部最優(yōu)時(shí)，INSGAII_SAA能夠跳出局部最優(yōu)并對(duì)解空間進(jìn)行高效搜索，獲得全局最優(yōu)解集。

b）與原始算法NSAGII和SAA相比，INSGAII_SAA所得調(diào)度方案各目標(biāo)值更優(yōu)。相較于NSGAII，INSGAII_SAA的最大完成時(shí)間平均減少了8.82%、逾期損失平均減少59.89%、改機(jī)次數(shù)平均減少20.60%；相較于SAA，INSGAII_SAA的最大完成時(shí)間平均減少了19.18%、逾期損失平均減少80.45%、改機(jī)次數(shù)平均減少44.92%。

c）在保證逾期損失最小的情況下，INSGAII_SAA有效縮短了訂單完成時(shí)間，并減少了改機(jī)操作次數(shù)，適用于求解渦流紡小批量多品種生產(chǎn)模式的調(diào)度問(wèn)題。

本文結(jié)合渦流紡的生產(chǎn)發(fā)展趨勢(shì)，為小批量多品種生產(chǎn)模式提供了一種更加科學(xué)的調(diào)度方法。然而，為便于理論驗(yàn)證，本文忽略了因紡紗原料供應(yīng)以及運(yùn)輸過(guò)程所消耗的人工成本。另外，本文也未考慮實(shí)際生產(chǎn)中緊急插單等特殊情況對(duì)調(diào)度方法的影響，這種緊急插單情況下的渦流紡車間重調(diào)度問(wèn)題值得進(jìn)一步研究。

參考文獻(xiàn)：

［1］付佳琦，楊瑞華.噴氣渦流紡紗技術(shù)進(jìn)程與展望［J］.棉紡織技術(shù)，2024，52（10）：92-96.

FU Jiaqi， YANG Ruihua. Progress and prospect of air jet vortex spinning technology［J］. Cotton Textile Technology， 2024， 52（10）： 92-96.

［2］KOMAKI M， MALAKOOTI B. General variable neighbor-hood search algorithm to minimize makespan of the distri-buted no-wait flow shop scheduling problem［J］. Produc-tion Engineering， 2017， 11（3）： 315-329.

［3］潘欣明， 王靜安， 邱子峻， 等. 基于改進(jìn)蟻群算法的色紡企業(yè)生產(chǎn)調(diào)度方法［J/OL］.現(xiàn)代紡織技術(shù)，2024：1-12［2024-10-23］.http：//kns.cnki.net/kcms/detail/33.1249.TS.20240624.0930.002.html.

PAN Xinming， WANG Jing'an，QIU Zijun， et al. Research on production scheduling method of colored textile enter-prise based on improve ant colony algorithm［J］. Advanced Textile Technology， 2024：1-12［2024-10-23］.http：//kns.cnki.net/kcms/detail/33.1249.TS.20240624.0930.002.html.

［4］MA H， SUN C， WANG J， et al. Multisystem optimization for an integrated production scheduling with resource saving problem in textile printing and dyeing［J］. Complexity， 2020， 2020： 8853735.

［5］KRISHNAMOORTHY P， SATHEESH N， SUDHA D， et al. Effective scheduling of multi-load automated guided vehicle in spinning mill： a case study［J］. IEEE Access， 2023， 11： 9389-9402.

［6］高詠珊， 張?zhí)K道， 孔維健， 等. 基于遺傳算法的細(xì)紗接頭調(diào)度策略［J］. 上海紡織科技， 2022， 50（7）： 19-22.

GAO Yongshan， ZHANG Sudao， KONG Weijian， et al. Scheduling strategy of spinning joint based on genetic algorithm［J］. Shanghai Textile Science amp; Technology， 2022， 50（7）： 19-22.

［7］章國(guó)政. 基于遺傳算法的紡紗車間計(jì)劃調(diào)度優(yōu)化策略研究［J］. 紡織報(bào)告， 2021， 40（2）： 36-39.

ZHANG Guozheng. Research on optimal strategy of spinning workshop planning scheduling based on genetic algorithm［J］. Textile Reports， 2021， 40（2）： 36-39.

［8］董平軍， 俞佳安. 考慮學(xué)習(xí)—遺忘效應(yīng)的服裝縫制車間生產(chǎn)調(diào)度模型［J］. 現(xiàn)代紡織技術(shù)， 2023， 31（3）： 81-91.

DONG Pingjun， YU Jia'an. Production scheduling model of garment sewing workshop with learning and forgetting effects［J］. Advanced Textile Technology， 2023， 31（3）： 81-91.

［9］周亞勤， 王攀， 張朋， 等. 緯編織造車間生產(chǎn)調(diào)度方法研究［J］. 紡織學(xué)報(bào)， 2021， 42（4）： 170-176.

ZHOU Yaqin， WANG Pan， ZHANG Peng， et al. Research on production scheduling method for weft knitting workshops［J］. Journal of Textile Research， 2021， 42（4）： 170-176.

［10］LI K， ZHANG H， CHU C， et al. A bi-objective evolutionary algorithm for minimizing maximum lateness and total pollution cost on non-identical parallel batch processing machines［J］. Computers amp; Industrial Eng-ineering， 2022， 172： 108608.

［11］劉建林， 汪軍， 鄒專勇. 870 EX型渦流紡紗機(jī)優(yōu)勢(shì)分析及應(yīng)用［J］. 紡織器材， 2024， 51（1）： 24-26.

LIU Jianlin， WANG Jun， ZOU Zhuanyong. Advantages analysis and application of 870 EX vortex spinning machine［J］. Textile Accessories， 2024， 51（1）： 24-26.

［12］雷鈞杰， 沈春婭， 胡旭東， 等. 基于NSGAII和神經(jīng)網(wǎng)絡(luò)的織造車間大規(guī)模調(diào)度［J］. 紡織學(xué)報(bào)， 2023， 44（11）： 208-215.

LEI Junjie， SHEN Chunya， HU Xudong， et al. Large-scale scheduling of weaving workshop based on NSGAII and neural network［J］. Journal of Textile Research， 2023， 44（11）： 208-215.

［13］EIBEN A E， SMIT S K. Parameter tuning for configuring and analyzing evolutionary algorithms［J］. Swarm and Evolutionary Computation， 2011， 1（1）： 19-31.

［14］WANG H， FU Y， HUANG M， et al. A NSGA-II based memetic algorithm for multiobjective parallel flowshop scheduling problem［J］. Computers amp; Industrial Eng-ineering， 2017， 113： 185-194.

［15］黃學(xué)文， 陳紹芬， 周闐玉， 等. 求解柔性作業(yè)車間調(diào)度的遺傳算法綜述［J］. 計(jì)算機(jī)集成制造系統(tǒng)， 2022， 28（2）： 536-551.

HUANG Xuewen， CHEN Shaofen， ZHOU Tianyu， et al. Survey on genetic algorithms for solving flexible job-shop scheduling problem［J］. Computer Integrated Manufactu-ring Systems， 2022， 28（2）： 536-551.

［16］牟健慧， 段培永， 高亮， 等. 基于混合遺傳算法求解分布式流水車間逆調(diào)度問(wèn)題［J］. 機(jī)械工程學(xué)報(bào)， 2022， 58（6）： 295-308.

MU Jianhui， DUAN Peiyong， GAO Liang， et al. Hybrid genetic algorithm for distributed flow shop inverse sche-duling problem［J］. Journal of Mechanical Engineering， 2022， 58（6）： 295-308.

［17］沈春婭， 方遼遼， 彭來(lái)湖， 等. 基于自適應(yīng)模擬退火算法的整經(jīng)準(zhǔn)備車間排產(chǎn)模型［J］. 紡織學(xué)報(bào)， 2024， 45（3）： 81-86.

SHEN Chunya， FANG Liaoliao， PENG Laihu， et al. Production scheduling of warping department based on adaptive simulated annealing algorithm［J］. Journal of Textile Research， 2024， 45（3）： 81-86.

［18］AKRAM K， KAMAL K， ZEB A. Fast simulated annealing hybridized with quenching for solving job shop scheduling problem［J］. Applied Soft Computing， 2016， 49： 510-523.

A vortex spinning workshop scheduling method based on improved NSGAII algorithm

LUO Laibing1，" FANG" Liaoliao1，" SHEN" Chunya2，" SHI" Luhong2，" HU" Xudong1

（1.Key Laboratory of Modern Textile Machinery amp; Technology of Zhejiang Province， Zhejiang Sci-Tech

University， Hangzhou 310018， China; 2.Zhejiang Kangli Automation Technology Co.， Ltd.， Shaoxing 312500， China）

Abstract：

To cope with the challenge of gradually changing production of vortex spinning in the textile industry from the traditional single large-volume mode to the small-volume and multi-variety mode， a new scheduling method is proposed in this paper. The method is based on analyzing the order production of a vortex spinning enterprise in Jinhua， and by this method， the article constructs a multi-objective optimization model with the objectives of minimizing the maximum completion time， minimizing the overdue loss and minimizing the number of changeover times. The article also solves the model by the proposed INSGAII_SAA algorithm. The research focuses on improving the production scheduling efficiency to cope with diversified market demands and helping enterprises to reduce the comprehensive cost of production management.

In this paper， firstly， through the analysis of the vortex spinning production process， the vortex spinning scheduling optimization model under the small batch and multi-species mode is established. The model comprehensively considers several production constraints， such as equipment availability， the number of change machines， order priority， etc.， to ensure the practical applicability of the model. On this basis， this paper proposes the INSGAII_SAA algorithm， which aims to improve the efficiency and effectiveness of the solution by avoiding the algorithm from falling into problems such as premature convergence. In terms of algorithm improvement， this paper mainly has three major innovations. Firstly， heuristic rules are used to initialize the population to reduce the redundancy of the initial solution space and improve the quality of the population. Secondly， the mechanism of adaptive selection of the cross-mutation operator is introduced. The traditional cross-mutation operation has a trade-off between local search and global search ability， while in this paper， by dynamically adjusting the selection probability of the cross-mutation operator， the algorithm is able to adaptively select the appropriate operator， which improves the algorithm's local and global search ability while guaranteeing the diversity of the population. Thirdly， this paper incorporates the simulated annealing algorithm （SAA）to locally search the individual with the largest crowding distance to further optimize the algorithm's solving ability and effectively avoid the solution set from falling into the local optimum. To verify the effectiveness of the improved algorithm， this paper selects the order data of a vortex spinning enterprise in Jinhua for experiments. The results show that the proposed INSGAII_SAA algorithm outperforms NSGAII in several performance indicators. INSGAII_SAA reduces the maximum completion time by about 8.7% on average， reduces the overdue loss by about 59.89% on average， and reduces the number of changeover times by about 34.91% on average compared to the original NSGAII.

The improved algorithm proposed in this paper shows good results in the experiments， but there are still some limitations. First of all， the production interruption problem that may be caused by factors such as insufficient supply of raw materials or equipment failure is not considered in the model construction process of this paper. In addition， situations such as order insertion or emergency orders that may occur in actual production are also not taken into account in the model. In future research， the scheduling model can be further optimized for these problems to improve the robustness of the model and the adaptability of the algorithm.

Keywords：

vortex spinning; spinning workshop; production scheduling; multi-objective optimization; improving NSGAII