考慮強制同機并行作業(yè)的廣義作業(yè)車間調(diào)度優(yōu)化

摘 要：模具組合加工、電子產(chǎn)品合檢等帶來不同工件強制同機并行作業(yè)，這打破了作業(yè)車間調(diào)度同一機器不能在同一時刻處理不同工件的約束。為解決該類作業(yè)車間調(diào)度問題，提出一種自適應(yīng)混合初始化遺傳算法對其進行求解。首先，將該問題定義為考慮強制同機并行作業(yè)的廣義作業(yè)車間調(diào)度；利用混合整數(shù)規(guī)劃法以最小化最大完工時間為優(yōu)化目標(biāo)建立優(yōu)化模型。然后，新設(shè)計了相應(yīng)的編碼、解碼以支持同機并行作業(yè)約束下可行調(diào)度方案的表達和約束解析；建立了種群混合初始化方法，以支持新約束下高質(zhì)量可行解的生成；設(shè)計了新的交叉、變異操作方法，保證了同機并行作業(yè)約束下新生解的可行性；構(gòu)建了交叉、變異自適應(yīng)算子，實現(xiàn)了子代的自適應(yīng)更新，提高了算法全局搜索能力。最后，基于作業(yè)車間調(diào)度基準(zhǔn)算例構(gòu)建了40個測試算例，對該測試算例和電子產(chǎn)品分組合檢實例開展實驗。結(jié)果表明，所構(gòu)建模型和算法可以有效求解強制同機并行作業(yè)的廣義作業(yè)車間調(diào)度問題，提出的改進策略均有效提升了解的質(zhì)量，驗證了模型的可行性和算法的優(yōu)越性。

關(guān)鍵詞：強制同機并行作業(yè)； 廣義作業(yè)車間調(diào)度； 自適應(yīng)； 混合初始化； 遺傳算法

中圖分類號：TP18 文獻標(biāo)志碼：A

文章編號：1001-3695（2024）08-014-2343-08

doi：10.19734/j.issn.1001-3695.2023.12.0609

General job shop scheduling optimization considering mandatoryconcurrent operations on same machine

Jin Hong， Zhang Hucheng， Xin Dequan， Lyu Shengping

（School of Engineering， South China Agricultural University， Guangzhou 510642， China）

Abstract：The combination processing of molds and electronic product joint inspection introduce the mandatory concurrent operations on the same machine（MCDSM）， which breaks the constraint that the same machine cannot process different jobs at the same time in the job shop scheduling（JSP） . To solve this type of job shop scheduling problem， this paper proposed an adaptive hybrid initialization genetic algorithm（AHIGA）. Firstly， this paper defined the problem as a generalized JSP considering mandatory concurrent operations on the same machine（GJSPMCO） problem， and established an optimization model using mixed integer programming with the objective of minimizing the maximum completion time. Next， it designed corresponding encoding and decoding techniques to support the representation and resolution of feasible scheduling plans within the constraints of MCOSM. Meanwhile， it established a population hybrid initialization method to generate high-quality feasible solutions. This paper also designed novel crossover and mutation operation methods to ensure the feasibility of newly generated solutions under the constraint of MCOSM. Additionally， it constructed an adaptive crossover and mutation operators to enable the adaptive updating of offspring， thereby enhancing the algorithm’s global search capability. Finally， it constructed 40 test cases based on JSP benchmark， and used these test cases and an example of joint inspection of electronic products for experiments. The results show that the proposed model and algorithm can effectively solve GJSPMCO problem， and the improvement strategies can enhance the quality of solutions， demonstrating the feasibility of the model and the superiority of AHIGA.

Key words：mandatory concurrent operations on the same machine; generalized job shop scheduling; adaptive; hybrid initiali-zation; genetic algorithm

0 引言

模具生產(chǎn)中的部分工序需要進行組合加工，使得車間運行優(yōu)化時需要考慮不同工件強制同機并行作業(yè)的特殊約束。比如，模具型腔結(jié)構(gòu)復(fù)雜，經(jīng)常設(shè)計成由多個鑲塊組成的型腔，為保證模具型腔成型精度和外觀的美觀，在進行型腔加工之前應(yīng)先將鑲塊正確地鑲拼在相應(yīng)位置，而各鑲塊上的其他特征單獨進行加工。類似，在電子產(chǎn)品檢測過程中，檢測車間對同種產(chǎn)品樣機設(shè)計總工藝路線，并將樣機劃分為不同組，各分組樣機按照其工藝路線指定子路線串行完成各工序的檢測。但部分檢測樣機需要跨組組合檢測經(jīng)歷不同前置檢測工序的多個組件或功能，形成強制同機并行作業(yè)約束。無論是型腔加工還是電子產(chǎn)品檢測，都要確保強制同機并行作業(yè)工序的所有前驅(qū)工序全部完成，才能開始進行強制同機并行作業(yè)。

模具組合加工、電子產(chǎn)品檢測車間同種產(chǎn)品不同樣機合檢等帶來了不同工件強制同機并行作業(yè)，這打破了作業(yè)車間調(diào)度（job shop scheduling，JSP）同一機器不能在同一時刻處理多個不同工件的約束。這種新約束給車間的智能調(diào)度優(yōu)化帶來了新的挑戰(zhàn)，解決帶強制同機并行作業(yè)約束的作業(yè)調(diào)度是模具生產(chǎn)和電子產(chǎn)品檢測車間亟待突破的瓶頸。為此，本研究將其定義為考慮強制同機并行作業(yè)的廣義作業(yè)車間調(diào)度（general JSP considering mandatory concurrent operations on the same machine，GJSPMCO）。

JSP是車間運行優(yōu)化的核心，是優(yōu)化利用車間生產(chǎn)資源、提高生產(chǎn)效率、減少車間運行成本、縮短生產(chǎn)周期的重要手段［1］。國內(nèi)外學(xué)者對其已開展了大量研究。從模型約束角度看，相關(guān)研究者主要考慮了車間不確定性［2］、搬運和貨物托盤影響（如AGV聯(lián)動）［3］、人機雙資源約束［4］等。這些約束給JSP模型構(gòu)建和優(yōu)化求解帶來了新的挑戰(zhàn)，但其更符合車間生產(chǎn)實際。同時，JSP研究擴展考慮了工藝柔性（如機器可選、工藝路線可選以及工序順序無關(guān)）［5～7］，形成了柔性作業(yè)車間調(diào)度（flexible job shop scheduling，F(xiàn)JSP）。無論是JSP還是FJSP，其所考慮的核心約束為單一工件作業(yè)時獨占其所選機器，未涉及本研究所考慮強制同機并行作業(yè)約束。

從（F）JSP優(yōu)化方法角度看，現(xiàn)有研究主要經(jīng)歷了三個主要階段。20世紀(jì)60年代，混合整數(shù)規(guī)劃、動態(tài)規(guī)劃等運籌學(xué)方法以及一些尋找近似優(yōu)化解的啟發(fā)式算法被提出來［8，9］；70年代，JSP被相關(guān)學(xué)者證實為NP-Complete問題［10］，難以在多項式時間內(nèi)得到精確最優(yōu)結(jié)果，故大量啟發(fā)式規(guī)則不斷涌現(xiàn)；80年代以來，大量智能優(yōu)化方法不斷應(yīng)用于（F）JSP［11～16］，這些方法能快速獲得近似最優(yōu)甚至最優(yōu)化結(jié)果，大大擴展了（F）JSP的求解范圍與規(guī)模，是當(dāng)前深受歡迎的方法。近年來，候鳥算法［17］、蛙跳算法［18］、灰狼算法［19］、樽海鞘群算法［20］、強化學(xué)習(xí)算法［21］等智能優(yōu)化算法被廣泛應(yīng)用于該類問題。

上述研究推動了（F）JSP約束模型構(gòu)建和優(yōu)化求解，但是所建立的約束模型和相應(yīng)優(yōu)化機制難以直接應(yīng)用于GJSPMCO。因為GJSPMCO不同于傳統(tǒng)的（F）JSP，（F）JSP中的工件之間相互獨立，作業(yè)遵循各自的加工路徑，在可行方案表達、生成、解析、迭代操作時只需考慮各自工件的前驅(qū)工序約束；GJSPMCO中的某些工件之間存在強制同機并行作業(yè)約束，導(dǎo)致工件之間并不相互獨立，在可行方案表達、生成、解析、迭代操作每一步都需要聯(lián)合考慮強制同機并行作業(yè)工序的前驅(qū)工序約束，從而保證每一步生成的個體都為可行個體。將（F）JSP中的可行方案表達、生成、解析、迭代操作應(yīng)用于GJSPMCO，打破強制同機并行作業(yè)工序的前驅(qū)工序約束，從而生成不可行解。因此強制同機并行作業(yè)約束給問題建模、優(yōu)化求解時可行方案的表達、生成、解析、迭代操作等帶來挑戰(zhàn)。遺傳算法因自身具有并行性、靈活性、適應(yīng)性、可拓展性等特點，在求解（F）JSP時能取得不錯的效果，所以當(dāng)前大量學(xué)者在求解（F）JSP時會選擇在遺傳算法的基礎(chǔ)上進行改進［22］。而且遺傳算法的求解過程是基于個體的基因編碼，可以對問題進行靈活的建模和表達，所以可以根據(jù)實際問題的需要定義適當(dāng)?shù)木幋a方式和操作，以便更好地表達問題的約束和目標(biāo)，并且遺傳算法的可拓展性可以使遺傳算法與其他優(yōu)化方法結(jié)合，形成混合算法，從而進一步提高求解效果。為簡單高效地求解GJSPMCO，本文將在遺傳算法的基礎(chǔ)上對GJSPMCO開展研究。創(chuàng)新工作如下：a）定義了GJSPMCO新問題，并利用混合整數(shù)規(guī)劃法建立了GJSPMCO優(yōu)化模型；b）以最小化最大完工時間為優(yōu)化目標(biāo)，根據(jù)GJSPMCO問題特性提出一種自適應(yīng)混合初始化遺傳算法（adaptive hybrid initialization genetic algorithm，AHIGA），具體包括針對強制同機并行作業(yè)約束設(shè)計了相應(yīng)編碼、解碼、混合初始化種群以及交叉、變異操作方法，并引入了自適應(yīng)算子提高了算法全局搜索能力；c）基于JSP基準(zhǔn)算例，通過隨機引入強制組合作業(yè)構(gòu)建了GJSPMCO測試算例，基于該測試算例和電子產(chǎn)品分組合檢實例開展測試和對比分析，驗證了AHIGA的可行性和優(yōu)越性。

1 GJSPMCO問題描述

GJSPMCO問題描述如下：N個工件{1，2，…，N}在M臺機器{1，2，…，M}上作業(yè)；各工件具有確定的工藝路線，但存在不同工件的多個工序形成組合工序的同時，在同一機器上并行完成作業(yè)；為提高泛化性并滿足車間生產(chǎn)實際，同時考慮機器柔性即每道工序可能在多臺不同機器上作業(yè)，各工件工序的作業(yè)時間由所在機器確定。調(diào)度目標(biāo)是在滿足機器可用、工序順序和強制同機并行作業(yè)約束條件下，為各工序選擇最合適的機器，確定每臺機器上各工序的最佳作業(yè)順序，使系統(tǒng)的某些性能指標(biāo)達到最優(yōu)。表1給出了四個工件四臺機器的GJSPMCO實例，機器下面對應(yīng)的數(shù)字表示工序在該機器上的作業(yè)時間。

為此，GJSPMCO還需要滿足如下約束條件：

a）一臺機器在同一時刻只能處理一個工序或指定組合工序；

b）一個工件同一時刻只能在一臺機器上作業(yè)；

c）同一工件的工序之間存在先后順序約束，不同工件的工序之間受到強制同機并行作業(yè)約束影響；

d）所有工件的優(yōu)先級相同；

e）某道（組合）工序一旦在某臺機器上開始作業(yè)就不能中斷，直到該工件作業(yè)完成；

f）所有工件在零時刻可以對其進行作業(yè)。

現(xiàn)有的（F）JSP模型無法準(zhǔn)確描述GJSPMCO問題：一是強制同機并行作業(yè)的多個工序形成組合工序，組合工序中組成元素對應(yīng)工件緊前工序耦合影響該組合工序的可開始時間，該組合工序的結(jié)束時間影響組成元素的所有工件緊后工序的可開始時間，但現(xiàn)有（F）JSP模型中并未引入該約束；二是現(xiàn)有（F）JSP模型無法約束構(gòu)成組合工序的多個工序元素之間的關(guān)系。為解決上述問題，建模時先將各工件的工序Oij統(tǒng)一抽象為只包含一個元素的組合工序OIJ，并將Oij和OIJ統(tǒng)稱為工序。在此基礎(chǔ)上構(gòu)建優(yōu)化模型，模型涉及的符號定義如表2所示。

在此，基于混合整數(shù)規(guī)劃法構(gòu)建其優(yōu)化模型，以最小化最大完工時間為優(yōu)化目標(biāo)。

Cmax=min（max（Cm）） 1≤m≤M（1）

約束：CIJ-SIJ=PIJm I，J，m（2）

∑Mm=1XIJm=1 I，J（3）

SIJ+XIJmPIJm≤CIJ I，J，m（4）

CIJ≤Cmax I，J（5）

CIJ+Q（YIJPKm-1）≤SPK I，J，P，K，m（6）

Ci（j-1）≤SIJ I，J，Oij∈OIJ（7）

SIJ≥0，PIJm>0，CIJ>0 I，J，m（8）

Sij×XIJm=Spq×XIJm Oij，Opq∈OIJ（9）

Cij×XIJm=Cpq×XIJm Oij，Opq∈OIJ（10）

上述模型約束關(guān)系主體基于OIJ構(gòu)建，如無特別說明，這里的工序均指OIJ；具體組成元素Oij以工件工序進行說明。式（1）為優(yōu)化目標(biāo)函數(shù)；式（2）表示工序進行作業(yè)后中途不能中斷；式（3）表示任意工序在機器上只作業(yè)一次；式（4）表示任意工序的開始作業(yè)時間都不大于其完工時間；式（5）表示任意工序完工時間都不大于最大完工時間；式（6）表示每臺機器在同一時刻只能有一道工序在作業(yè)；式（7）表示任意工件工序開始作業(yè)時間不小于該工序工件緊前工序的完工時間，同時約束了組合工序的開始時間大于等于其所有組成元素的工件緊前工序的結(jié)束時間；式（8）表示任意工序的開始作業(yè)時間非負(fù)，作業(yè)時間和完工時間大于0；式（9）和（10）表示組合工序OIJ的各元素Oij∈OIJ必須同時開始和同時完工。

2 自適應(yīng)混合初始化遺傳算法

為滿足強制同機并行作業(yè)約束要求，設(shè)計新的編碼、解碼以及初始可行方案生成機制，在此基礎(chǔ)上研究相應(yīng)的優(yōu)化迭代操作方法，為此提出AHIGA機制，具體流程如圖1所示。

2.1 編碼和解碼

GJSPMCO考慮工序排序和機器QWvpp9oxu09JF/Ac27srPzqgaFZufewoSbkC9kQw6eU=選擇，在此采用工序編碼，編碼由三段整數(shù)編碼序列組成，表1對應(yīng)的編碼實例如圖2所示。

第一段為工序編碼序列，每個基因用工件集序號表示，為了保證各基因位的一致性，每個基因位的元素數(shù)量設(shè)為l=max{|OIJ|}，I，J;對于|OIJ|<l，在該基因位用虛擬工件0進行補位，具體如圖2第一行所示。每個基因位中非0元素i，i∈［1，N］出現(xiàn)頻次j∈［1，Ni］代表工件i對應(yīng)工序Oij，如圖2中第二行所示。第二段為機器編碼，其可選范圍為［1，M］，機器編碼順序與工序編碼相對應(yīng)，表示該工序編碼序列對應(yīng)（組合）工序所指定作業(yè)機器。第三段為作業(yè)時間編碼，表示其對應(yīng)工序在指定機器上作業(yè)所需要時間。

基于編碼方案設(shè)計的順序解碼方法如算法1所示。

算法1 順序解碼方法

a）設(shè)置AO（1，1：ON）、AO（2，1：ON）分別存儲各工序的開始時間和完工時間，ON=|OPlan|；用JP={JP［1］，JP［2］，…，JP［N］}、MP={MP［1］，MP［2］，…，MP［M］}分別記錄各工件和機器緊前工序的工序結(jié)束時間。初始化AO、MP、JP元素為0，k=1。

b）從左往右順序讀取工序編碼序列OPlan［k］，1≤k≤|OPlan|中各基因位非0元素（工件編號），確定其工序OIJ，并從MPlan和TmPlan中分別獲取OIJ作業(yè)機器m和作業(yè)時間PIJm。

c）OIJ的開始和完工時間分別為SIJ=maxi∈I{JP［i］，MP［m］}，CIJ=SIJ+PIJm。

d）更新JP［i］=CIJ，i∈I，MP［m］=CIJ，AO（1，k）=SIJ，AO（2，k）=CIJ。

e）若k<ON，k=k+1，轉(zhuǎn)b），否則轉(zhuǎn)f）。

f）結(jié)束。

2.2 混合初始化種群

初始種群的質(zhì)量決定遺傳算法求解質(zhì)量和收斂速度。為增強初始解的質(zhì)量，在此采用混合初始化方式［23］，其中一半種群采用貪婪初始化方式生成，另一半種群采用隨機初始化方式生成?；诰幋a方式設(shè)計混合初始化種群生成算法，如算法2所示。

算法2 混合初始化種群

a）初始化種群規(guī)模NP，定義NP×3的數(shù)組Pop，計數(shù)器np=1，k=max{|OIJ|}，I，J。

b）生成新的空的基于工件表示的工序序列OPlan、機器序列MPlan和作業(yè)時間序列TmPlan，設(shè)置［1，N］所有數(shù)為未標(biāo)狀態(tài)。

c）如果［1，N］全部被標(biāo)記，轉(zhuǎn)f）；反之，隨機選?。?，N］中未標(biāo)記的數(shù)i，判斷OPlan中i出現(xiàn)頻次j，如果j=Ni，標(biāo)記工件i，轉(zhuǎn)c）；如果j<Ni，從不同工件工藝路線PPlank，1≤k≤N中獲取Oij，如果Oij為常規(guī)工序，將i加入OPlan尾部，并在該基因位補l－1個0；如果Oij為組合工序元素，轉(zhuǎn)d）。

d）獲取Oij∈OIJ={Oij，Opq，…，Oyz}對應(yīng)工件集I，將I中各工件編號綁定放入到OPlan尾部，并在該基因位補l－|OIJ|個0。

e）獲取OIJ未放入調(diào)度序列的前驅(qū)工序集JP［OIJ］，判斷OIJ中i∈I是否有前驅(qū)組合工序，如果工件i無前驅(qū)組合工序，依次將Oij∈JP［OIJ］對應(yīng)工件編號i隨機插入在OPlan中I之前；反之將其隨機插入在最靠近i的前驅(qū)組合工序和I之間，轉(zhuǎn)c）；并在插入的基因位補l－1個0。

f）生成（0，1）的隨機數(shù)r，若r<0.5，對于OPlan［k］，1≤k≤|OPlan|中工序OIJ，根據(jù)順序解碼選擇m=argmin{EIJm1，EIJm2，…，EIJmj}，m1，m2，…，mj∈MIJ作為作業(yè)機器；反之從MIJ中隨機選擇m作為OIJ作業(yè)機器；最后形成機器序列MPlan。進一步確定各工序作業(yè)時間，生成作業(yè)時間序列TmPlan。存儲Pop（np，1）=OPlan、Pop（np，2）=MPlan、Pop（np，3）=TmPlan。

g）如果np<NP，np=np+1，轉(zhuǎn)b）；反之結(jié)束。

利用算法2和表1中的數(shù)據(jù)生成一個初始可行方案的示意，如圖3所示。假設(shè)算法2中步驟c）隨機生成了（3，0）（1，0）（4，0）（2，0）（1，0）（1，0）工件集序號表示的工序序列（如圖3中第一行），對應(yīng)工序分別為O31、O11、O41、O21、O12、O13。然后基于步驟c）隨機選取工件2，對應(yīng)工序O22、O22和O33形成組合工序，基于步驟d）在序列尾部放入O22、O33，對應(yīng)工件（2，3）（如圖3中第三行），但O33前驅(qū)工序O32未插入工序序列且O22、O33無前驅(qū)組合工序，基于步驟e）將O32對應(yīng)工件集編號3插入到（2，3）之前，并采用0補位（如圖3中的第四行），網(wǎng)格框為工件3隨機插入位置。在已生成工序序列基礎(chǔ)上基于步驟c）生成工件編號3的工序序列，對應(yīng)工序為O34。繼續(xù)基于步驟c）隨機生成工件編號4，對應(yīng)工序O43，因為O24和O43為組合工序O24、O43，基于步驟d）在序列尾部放入O24、O43，對應(yīng)工件（2，4）。但O24前驅(qū)工序中O23未進行插入且O24、O43工件2存在前驅(qū)組合工序O22、O33，基于步驟e）將O23對應(yīng)工件編號2插入（2，4）和（2，3）之間，并采用0補位。根據(jù)步驟c）繼續(xù)選取未標(biāo)記的工件編號連同補位0一起加入工序序列尾部，直至1～4中所有數(shù)都被標(biāo)記，此時工序序列編碼完成，最終工序編碼序列如圖3中第五行所示。進一步基于步驟f）生成對應(yīng)機器和作業(yè)時間序列，如圖中第六、七行所示。

2.3 自適應(yīng)遺傳操作

迭代過程中的遺傳操作包括選擇、交叉、變異和精英保留等。選擇操作是為了挑選出種群中優(yōu)秀的個體作為后續(xù)交叉變異的對象，本研究以目標(biāo)函數(shù)的倒數(shù)為適應(yīng)度函數(shù)f，采用輪盤賭方式進行選擇。對于種群規(guī)模為NP的種群，基于各個體概率Pi=fi/∑NPj=1fj，1≤i≤NP計算相應(yīng)累計概率Qq=∑qi=1Pi，1≤q≤NP，然后生成（0，1）之間的隨機數(shù)r，當(dāng)r≤Q1，選擇第一個個體；當(dāng)Qq－1≤r≤Qq，選擇第q個個體，當(dāng)選擇NP數(shù)量個體時選擇操作結(jié)束。

交叉是產(chǎn)生具有更優(yōu)基因組合后代的重要操作。常見的交叉操作有單點交叉、多點交叉、均勻交叉、次序交叉、工序順序交叉和擴展順序交叉等［24］。但這些交叉操作無法處理同機并行作業(yè)工序帶來的耦合影響，無法避免在子代中產(chǎn)生不可行解。為滿足同機并行作業(yè)約束，需設(shè)計新的交叉機制，對工序序列設(shè)計逐個順序交叉方法（one by one order crossover，OOOX），具體步驟如下：

a）選擇父代工序序列P1和P2，設(shè)置工序序列子代CP=、設(shè)備序列子代CM=和作業(yè)時間序列子代CT=。

b）生成（0，1）的隨機數(shù)r，若r<0.5，則選擇P1工序序列第一個基因位元素，否則選擇P2工序序列第一個基因位元素。

c）將所選元素添放在CP末尾，并將該元素對應(yīng)機器和時間分別放入CM和CT末尾。在P1和P2中刪除第一次出現(xiàn)該元素的基因。

d）重復(fù)b）和c），直到父代P1和P2中元素為空，則工序交叉完成。

以表1數(shù)據(jù)為例，OOOX示意如圖4所示。首先通過隨機數(shù)r<0.5選擇P1工序序列第一個基因位元素3，將元素3添放入子代CP首位，并刪除P1和P2中第一次出現(xiàn)元素3的基因位；然后繼續(xù)生成隨機數(shù)r≥0.5，選擇P2第一個基因位元素4，將元素4添放入子代CP末尾，并刪除P1和P2中第一次出現(xiàn)元素4的基因位；依此類推，直到P1和P2中元素為空則交叉完成，生成子代工序序列CP。

為使交叉更加充分，在完成工序交叉后進一步對機器編碼序列進行多點交叉，具體步驟如下：

a）隨機生成一段長度等于機器編碼序列長度的0-1序列，序列中元素1對應(yīng)機器編碼位置即為進行機器交叉的位置。

b）將父代P1編碼序列復(fù)制給子代C1，父代P2編碼序列復(fù)制給子代C2。

c）將父代P1機器交叉位置的機器更新到子代C2對應(yīng)工序的機器編碼位置，將父代P2機器交叉位置的機器更新到子代C1對應(yīng)工序的機器編碼位置。

d）P1機器交叉位置的機器對應(yīng)的作業(yè)時間更新到子代C2對應(yīng)工序的作業(yè)時間編碼位，P2機器交叉位的機器對應(yīng)的作業(yè)時間更新到子代C1對應(yīng)工序的作業(yè)時間編碼位。

機器交叉示意如圖5所示。首先將父代P1編碼序列復(fù)制給子代C1，父代P2編碼序列復(fù)制給子代C2，機器編碼上方為該機器對應(yīng)的工序；然后根據(jù)產(chǎn)生的隨機序列中元素1的位置進行機器交叉，父代P1機器序列中工序O11、O41、O32、O22，O33、O34、O14、O44對應(yīng)機器3、2、2、1、3、1、4更新到子代C2工序O11、O41、O32、O22，O33、O34、O14、O44對應(yīng)的機器碼位，父代P2機器序列中工序O21、O31、O22，O33、O23、O24，O43、O13、O14對應(yīng)機器3、1、2、1、1、1、4更新到子代C1工序O21、O31、O22，O33、O23、O24，O43、O13、O14對應(yīng)的機器碼位。

變異操作可增加種群的多樣性并防止早熟，影響著算法的局部搜索能力。對于（F）JSP，常見的變異操作有互換變異、逆序變異、插入變異和單點變異。但是這些變異操作應(yīng)用于本研究問題的工序序列變異時，因其隨機性，不可避免地打破了同機并行作業(yè)的工件前驅(qū)工序約束。為確保組合工序在變異后能夠滿足工序前后作業(yè)約束，對于工序變異，將以組合工序為節(jié)點進行分段變異。先以組合工序為分段點，依次判斷各分段工序編碼序列長度。若分段工序編碼序列長度大于等于2，則在分段工序編碼序列中隨機選擇兩個工序進行工序互換變異，否則不進行變異操作。為得到可行解，變異完成后需更新機器序列和作業(yè)時間序列，使得各工序?qū)?yīng)的作業(yè)機器和作業(yè)時間與變異之前相同。工序變異操作如圖6所示。

對于機器編碼序列的變異操作采用單點變異方式進行變異，將該位置上的機器隨機替換成該工序可選作業(yè)機器集中其他一臺機器。為得到可行解，與機器編碼變異位置對應(yīng)的作業(yè)時間需更新為該工序在替換機器上的作業(yè)時間。

為獲得更優(yōu)種群并加速收斂，在此提出一種自適應(yīng)交叉變異算子。將種群中的個體分為三類：適應(yīng)度值f前20%的個體為優(yōu)良個體，應(yīng)降低交叉率和變異率來保留自身優(yōu)良基因；f倒數(shù)20%的個體為拙劣個體，應(yīng)提高交叉率和變異率以增加生成優(yōu)良個體的概率；其余個體稱為普通個體，以一個適中的交叉率和變異率進行交叉和變異。分段函數(shù)描述的自適應(yīng)交叉率和變異率如式（11）（12）所示。

Pc=-arctan（50（fi-fminfmax-fmin+s-0.2））5π+0.9 fmin≤fi≤fmax+4fmin5

-2arctan（20（fi-fminfmax-fmin+s-0.2））5π+0.9

fmax+4fmin5<fi≤4fmax+fmin5

-3arctan（100（fi-fminfmax-fmin+s-0.8））5π+0.74fmax+fmin5<fi≤fmax（11）

Pm=-arctan（50（fi-fminfmax-fmin+s-0.2））5π+0.3 fmin≤fi≤fmax+4fmin5

-arctan（20（fi-fminfmax-fmin+s-0.2））5π+0.3fmax+4fmin5<fi≤ 4fmax+fmin5-arctan（50（fi-fminfmax-fmin+s-0.8））5π+0.24fmax+fmin5<fi≤fmax（12）

其中：fmax、fmin分別表示種群中最大和最小的適應(yīng)度值；fi表示個體i的適應(yīng)度值；s為極小的正實數(shù)。

采取精英保留策略保留具有優(yōu)良基因的個體到下一代。將經(jīng)過遺傳操作的種群與上一代種群合并形成新的種群，計算新種群中個體的適應(yīng)度值，取新種群中適應(yīng)度值大的50%個體作為下一代的初始種群，精英保留可以將歷代種群中具有優(yōu)良基因的個體保留下來，防止優(yōu)良個體遺失。

設(shè)N為種群規(guī)模，L表示一個染色體的位數(shù)，P表示一個染色體中的組合工序數(shù)。上述混合初始化、輪盤賭選擇、交叉、變異和精英保留等在最壞情況下操作的時間復(fù)雜度分別為O（N×L）、O（N）、O（N×L）、O（N×（P+1））、O（2×N），整體時間復(fù)雜度為O（N×L），由此推斷本文算法的時間復(fù)雜度并不高。

3 實驗結(jié)果與分析

因缺乏GJSPMCO問題相關(guān)基準(zhǔn)實例，本文在MK01-MK15［25］和SFJS6-SFJS10［26］基準(zhǔn)算例基礎(chǔ)上，通過隨機引入一、兩個組合工序生成測試算例，組合工序的作業(yè)時間信息如表3所示，其中由于MK01-MK15和SFJS6-SFJS10國際基準(zhǔn)算例并未說明單位，所以本研究中基于這兩個算例生成的GJSPMCD測試算例也無具體單位。以SFJS6為例：O12和O22為第一個組合工序，可在機器1和2上作業(yè)，作業(yè)時間分別為150和160；O13和O23為第二個組合工序，可在機器3上作業(yè)，作業(yè)時間為70。同時將對電子產(chǎn)品分組合檢實例進行進一步驗證?；谏鲜鰯?shù)據(jù)開展實驗，所有實驗均在Windows 10操作系統(tǒng)、主頻3.5 GHz、內(nèi)存16 GB的個人計算機上完成。

為驗證所構(gòu)建的GJSPMCO混合整數(shù)規(guī)劃模型的有效性，基于引入組合工序的SFJS6-SFJS10算例，利用IBM ILOG CPLEX 12.10進行求解，運行時間上限設(shè)置為360 s。CPLEX所得結(jié)果如表4所示。

表4中單約束為只考慮表3中對應(yīng)算例的第一個組合工序，雙約束為考慮各算例中兩個組合工序，更多組合工序在原理上與雙約束場景相似。n×m表示測試算例問題規(guī)模，Cmax為最小化最大完工時間，CPUs表示CPLEX實際求解時間，單位為秒（s）?？梢钥闯觯珻PLEX能獲得這些小規(guī)模GJSPMCO問題的可行解，證明了模型的可行性。

進一步通過對比實驗驗證OOOX、混合初始化策略以及自適應(yīng)算子的效果。在此，將GA+OOOX與常規(guī)的GA+工序順序交叉（POX）進行實驗對比。因直接應(yīng)用POX到GJSPMCO將得到不可行子代，所以在此限定POX只能對不涉及組合工序的工件進行交叉。在GA+OOOX基礎(chǔ)上，引入混合初始化，形成HIGA+OOOX；進一步增加自適應(yīng)算子，形成最終算法AHIGA。本研究選取文獻中常見的實驗參數(shù)進行初步實驗并選取效果最好的一組實驗參數(shù)：種群規(guī)模為200，交叉率和變異率為0.8和0.3，最大迭代次數(shù)為300，并采用MATLAB 2021a軟件實現(xiàn)。實驗結(jié)果如表5所示，表中CM為各算法運行10次所得Cmax的最小值；sd為算法10次運行所得Cmax的標(biāo)準(zhǔn)差，用來評估算法在求解各算例的穩(wěn)定性，sd越小，算法的穩(wěn)定性越高；sdmean為30個算例下各算法sd的平均值，用來評估算法面對不同規(guī)模算例時的綜合穩(wěn)定性；RPD表示相對百分比差異，用于評估當(dāng)前算法與最優(yōu)算法之間的差距，計算公式為RPD=100×（CM-Min）/Min，其中Min表示各算法最優(yōu)結(jié)果的最小值，RPD越小，算法的搜索能力越強；RPDmean為30個算例下所求解得到RPD的平均值，用來評估算法面對不同規(guī)模算例時的綜合搜索能力。加粗?jǐn)?shù)字為所有算法中的最優(yōu)值。

從表中可知，在所有30個測試算例中，引入OOOX的GA+OOOX得到的CM和RPD，有21個算例優(yōu)于GA+POX所得結(jié)果，其余9個算例中，兩者得到相同的CM和RPD，且RPDmean降低了72.8%，表明OOOX可以大幅度提升算法全局搜索能力。同時可以看出，GA+OOOX得到的sd有24個算例優(yōu)于GA+POX所得結(jié)果，5個算例中，兩者得到相同的sd，僅1個算例GA+OOOX的sd劣于GA+POX，且GA+OOOX與GA+POX相比將sdmean降低了36.9%，說明OOOX可以顯著提高GA的穩(wěn)定性。對比HIGA+OOOX和GA+OOOX可知，引入混合初始化策略的HIGA+OOOX在GA+OOOX基礎(chǔ)上進一步改進了15個算例的CM和RPD，其余15個算例中，兩者得到相同的CM和RPD，且RPDmean降低了65.5%，表明混合初始化策略進一步增強了算法的全局搜索能力。而HIGA+OOOX得到的sd有13個算例優(yōu)于GA+OOOX所得結(jié)果，11個算例中，兩者得到相同的sd，6個算例HIGA+OOOX的sd劣于GA+OOOX，且HIGA+OOOX與 GA+OOOX相比，將sdmean降低了13.7%，說明混合初始化策略也可以有效提高算法的穩(wěn)定性。引入自適應(yīng)算子的AHIGA在HIGA+OOOX基礎(chǔ)上進一步改進了12個算例的CM和RPD，其余18個算例，兩者得到相同的CM和RPD，且RPDmean降低至0，表現(xiàn)出自適應(yīng)算子對提高算法全局搜索能力的有效性。而AHIGA得到的sd有10個算例優(yōu)于HIGA+OOX所得結(jié)果，12個算例中，兩者得到相同的sd，8個算例中，AHIGA的sd劣于HIGA+OOOX，且AHIGA與HIGA+OOOX相比將sdmean降低了6.1%，表明自適應(yīng)算子進一步提升了算法的穩(wěn)定性。上述對比結(jié)果證明了OOOX、混合初始化以及自適應(yīng)算子均有利于提升算法全局搜索能力和維持算法穩(wěn)定性，所提出的優(yōu)化策略具有可行性和有效性。

各優(yōu)化策略算法求解10次MK05雙約束問題獲得最優(yōu)結(jié)果的迭代過程收斂曲線對比如圖7所示。可以看出，OOOX、混合初始化以及自適應(yīng)算子均有利于減少GA的迭代次數(shù)，獲得更好的優(yōu)化結(jié)果，證明了本文方法能快速獲得高質(zhì)量解。

圖8為針對MK05雙約束問題AHIGA所得最優(yōu)調(diào)度方案的甘特圖?？梢钥闯?，圖中所有工序均滿足工序作業(yè)順序約束、不同工序在同一機器上作業(yè)先后順序與強制同機并行作業(yè)約束等要求。

進一步以電子產(chǎn)品檢測車間中的無人機、手機和車載導(dǎo)航儀三類產(chǎn)品的檢測實例來驗證本文模型和所提出的AHIGA。其中無人機、導(dǎo)航儀和手機相應(yīng)的待檢樣機分別被劃分為4、7、7組（每組視為一個工件），為各工件分別設(shè)計相應(yīng)工藝路線，具體工藝路線及產(chǎn)品檢測信息分別如圖9～11所示，工序下方為該工序的作業(yè)機器及對應(yīng)作業(yè)時間，作業(yè)時間單位為小時（h）。其中車載導(dǎo)航儀和手機的強制同機并行作業(yè)約束工序均為其分組后工件1、2的跌落沖擊測試和工件3、4的灰塵實驗；無人機的強制同機并行作業(yè)約束工序為工件1、2的交變鹽霧測試。

針對這三類產(chǎn)品檢測作業(yè)的調(diào)度，表6給出了各優(yōu)化策略運行10次的求解結(jié)果對比，其中CM單位為小時（h）。可以看出，AHIGA與HIGA+OOOX獲得最優(yōu)CM，AHIGA與GA+OOOX獲得最優(yōu)sd。進一步說明AHIGA具有較強的全局搜索能力和較好的解的穩(wěn)定性。圖12為AHIGA運行10次得到的最優(yōu)調(diào)度結(jié)果甘特圖，其中進行強制同機并行作業(yè)的組合工序用紅色框圖標(biāo)注（參見電子版），橫坐標(biāo)單位為小時（h）。從圖中可以看出，進行強制同機并行作業(yè)的組合工序依舊滿足工序順序、作業(yè)機器和作業(yè)時間約束，再一次驗證了AHIGA求解GJSPMCO問題的可行性。

4 結(jié)束語

本文探究利用自適應(yīng)混合初始化遺傳算法（AHIGA）求解考慮強制同機并行作業(yè)的廣義作業(yè)車間調(diào)度（GJSPMCO）問題。但在實際生產(chǎn)應(yīng)用中，存在強制同機并行作業(yè)、柔性同機并行作業(yè)和設(shè)備與工人耦合等多種約束影響，接下來將研究更符合車間實際情況的多約束廣義作業(yè)車間調(diào)度問題。

參考文獻：

［1］張潔， 秦威. 智能制造調(diào)度為先—《制造系統(tǒng)智能調(diào)度方法與云服務(wù)》導(dǎo)讀［J］. 中國機械工程， 2019，30（8）： 1002-1007. （Zhang Jie， Qin Wei. Intelligent manufacturing scheduling first：a guide of manufacturing system intelligent scheduling method and cloud service［J］. China Mechanical Engineering， 2019， 30（8）： 1002-1007.）

［2］Gao Liang， Pan Quanke. A shuffled multi-swarm micro-migrating birds optimizer for a multi-resource-constrained flexible job shop scheduling problem［J］. Information Sciences， 2016， 372： 655-676.

［3］Zhang Fayong， Li Rui， Gong Wenyin， et al. Deep reinforcement learning-based memetic algorithm for energy-aware flexible job shop scheduling with multi-AGV［J］. Computers & Industrial Enginee-ring， 2024， 189： 109917.

［4］郭鵬， 郝東輝， 鄭鵬， 等. 考慮工人疲勞的雙資源柔性作業(yè)車間調(diào)度優(yōu)化［J］. 浙江大學(xué)學(xué)報： 工學(xué)版， 2023， 57（9）： 1-10. （Guo Peng， Hao Donghui， Zheng Peng， et al. Scheduling optimization of dual resource-constrained flexible job shop considering worker fatigue［J］. Journal of Zhejiang University： Engineering Science， 2023， 57（9）： 1-10.）

［5］劉瓊， 梅偵. 面向低碳的工藝規(guī)劃與車間調(diào)度集成優(yōu)化［J］. 機械工程學(xué)報， 2017， 53（11）： 164-174. （Liu Qiong， Mei Zhen. Integrated optimization of process planning and shop scheduling for reducing manufacturing carbon emissions［J］. Journal of Mechanical Engineering， 2017， 53（11）： 164-174.）

［6］Li Yufeng， He Yan， Wang Yulin， et al. An optimization method for energy-conscious production in flexible machining job shops with dynamic job arrivals and machine breakdowns［J］. Journal of Cleaner Production， 2020， 254： 120009.

［7］Gong Xu ， Pessemier T D， Martens L， et al. Energy and labor-aware flexible job shop scheduling under dynamic electricity pricing： a many-objective optimization investigation［J］. Journal of Cleaner Production， 2019， 209： 1078-1094.

［8］Ku Wenyang， Beck J C. Mixed integer programming models for job shop scheduling： a computational analysis［J］. Computer & Operations Research， 2016， 73： 165-173.

［9］Ozolins A. Bounded dynamic programming algorithm for the job shop problem with sequence dependent setup times［J］. Operational Research， 2020， 20： 1701-1728.

［10］Meng Leilei， Duan Peng， Gao Kaizhou， et al. MIP modeling of energy-conscious FJSP and its extended problems： from simplicity to complexity［J］. Expert Systems with Applications， 2024， 241： 122594.

［11］李佳磊， 顧幸生. 雙種群混合遺傳算法求解具有預(yù)防性維護的分布式柔性作業(yè)車間調(diào)度問題［J］. 控制與決策， 2023， 38（2）： 475-482. （Li Jialei， Gu Xingsheng. Two-population hybrid genetic algorithm for distributed flexible job-shop scheduling problem with preventive maintenance［J］. Control and Decision， 2023， 38（2）： 475-482.）

［12］張國輝， 閆少峰， 陸熙熙， 等. 改進混合多目標(biāo)蟻群算法求解帶運輸時間和調(diào)整時間的柔性作業(yè)車間調(diào)度問題［J］. 計算機應(yīng)用研究， 2023， 40（12）： 3690-3695. （Zhang Guohui， Yan Shaofeng， Lu Xixi， et al. Improved hybrid multi-objective ant colony optimization for flexible job-shop scheduling problem with transportation time and setup time［J］. Application Research of Computers， 2023， 40（12）： 3690-3695.）

［13］董君， 葉春明. 新型教與同伴學(xué)習(xí)粒子群算法求解作業(yè)車間調(diào)度問題［J］. 計算機應(yīng)用研究， 2019， 36（12）： 3764-3768. （Dong Jun， Ye Chunming. Novel teaching and peer-learning-based particle swarm optimization for job-shop scheduling problem［J］ . Application Research of Computers， 2019， 36（12）： 3764-3768.）

［14］Zhang Pengyu， Song Shiji， Niu Shengsheng， et al. A hybrid artificial immune-simulated annealing algorithm for multiroute job shop scheduling problem with continuous limited output buffers［J］. IEEE Trans on Cybernetics， 2022， 52（11）： 12112-12125.

［15］王雷， 鄒新. 基于改進免疫克隆選擇算法的柔性作業(yè)車間調(diào)度［J］. 南京理工大學(xué)學(xué)報， 2018， 42（3）： 345-351. （Wang Lei， Zou Xin. Flexible job-shop scheduling based on improved immune clone selection algorithm［J］. Journal of Nanjing University of Science and Technology， 2018， 42（3）： 345-351.）

［16］吳銳， 郭順生， 李益兵， 等. 改進人工蜂群算法求解分布式柔性作業(yè)車間調(diào)度問題［J］. 控制與決策， 2019， 34（12）： 2527-2536. （Wu Rui， Guo Shunsheng， Li Yibing， et al. Improved artificial bee colony algorithm for distributed and flexible job-shop scheduling problem［J］. Control and Decision， 2019， 34（12）： 2527-2536.）

［17］杜凌浩， 向鳳紅. 改進多鄰域候鳥優(yōu)化算法的柔性作業(yè)車間調(diào)度研究［J］. 兵器裝備工程學(xué)報， 2022， 43（12）： 299-306. （Du Linghao， Xiang Fenghong. Research on flexible job shop scheduling based on improved multi-neighborhood migratory bird optimization algorithm［J］. Journal of Ordnance Equipment Engineering， 2022， 43（12）： 299-306.）

［18］楊冬婧， 雷德明. 新型蛙跳算法求解總能耗約束FJSP［J］. 中國機械工程， 2018， 29（22）： 2682-2689. （Yang Dongjing， Lei Deming. A novel shuffled frog-leaping algorithm for FJSP with total energy consumption constraints［J］. China Mechanical Engineering， 2018， 29（22）： 2682-2689.）

［19］Jiang Tianhua， Zhang Chao. Application of grey wolf optimization for solving combinatorial problems： job shop and flexible job shop schedu-ling cases［J］. IEEE Access， 2018， 6： 26231-26240.

［20］牛昊一， 吳維敏， 章庭棋， 等. 自適應(yīng)樽海鞘群算法求解考慮運輸時間的柔性作業(yè)車間調(diào)度［J］. 浙江大學(xué)學(xué)報： 工學(xué)版， 2023， 57（7）： 1267-1277. （Niu Haoyi， Wu Weimin， Zhang Tingqi， et al. Adaptive salp swarm algorithm for solving flexible job shop scheduling problem with transportation time［J］. Journal of Zhejiang Univer-sity： Engineering Science， 2023， 57（7）： 1267-1277.）

［21］王無雙， 駱淑云. 基于強化學(xué)習(xí)的智能車間調(diào)度策略研究綜述［J］. 計算機應(yīng)用研究， 2022， 39（6）： 1608-1614. （Wang Wu-shuang， Luo Shuyun. Research on intelligent shop scheduling strategies based on reinforcement learning［J］. Application Research of Computers， 2022， 39（6）： 1608-1614.）

［22］Chen Ronghua， Yang Bo， Li Shi， et al. A self-learning genetic algorithm based on reinforcement learning for flexible job-shop scheduling problem［J］. Computers & Industrial Engineering， 2020， 149： 106778.

［23］屈新懷， 王嬌， 丁必榮， 等. 貪婪初始種群的遺傳算法求解柔性作業(yè)車間調(diào)度［J］. 合肥工業(yè)大學(xué)學(xué)報： 自然294a220038706dc2bb88ce1a66a85b639fdd1bd212e61d3c4d685b4045a1560a科學(xué)版， 2021， 44（9）： 1153-1156，1171. （Qu Xinhuai， Wang Jiao， Ding Birong， et al. Genetic algorithm of greedy initial population to solve flexible job-shop scheduling［J］. Journal of Hefei University of Technology： Natural Science， 2021， 44（9）： 1153-1156，1171.）

［24］黃學(xué)文， 陳紹芬， 周闐玉， 等. 求解柔性作業(yè)車間調(diào)度的遺傳算法綜述［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 Manufacturing Systems， 2022， 28（2）： 536-551.）

［25］Brandimarte P. Routing and scheduling in a flexible job shop by Tabu search［J］. Annual Operation Research， 1993， 41： 157-183.

［26］Bagheri A， Zandieh M， Mahdavi I， et al. An artificial immune algorithm for the flexible job-shop scheduling problem［J］. Future Gene-ration Computer Systems， 2010， 26（4）： 533-541.