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

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

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

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

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

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

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

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

1 GJSPMCO問題描述

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

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

a）一臺(tái)機(jī)器在同一時(shí)刻只能處理一個(gè)工序或指定組合工序；

b）一個(gè)工件同一時(shí)刻只能在一臺(tái)機(jī)器上作業(yè)；

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

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

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

f）所有工件在零時(shí)刻可以對(duì)其進(jìn)行作業(yè)。

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

在此，基于混合整數(shù)規(guī)劃法構(gòu)建其優(yōu)化模型，以最小化最大完工時(shí)間為優(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以工件工序進(jìn)行說明。式（1）為優(yōu)化目標(biāo)函數(shù)；式（2）表示工序進(jìn)行作業(yè)后中途不能中斷；式（3）表示任意工序在機(jī)器上只作業(yè)一次；式（4）表示任意工序的開始作業(yè)時(shí)間都不大于其完工時(shí)間；式（5）表示任意工序完工時(shí)間都不大于最大完工時(shí)間；式（6）表示每臺(tái)機(jī)器在同一時(shí)刻只能有一道工序在作業(yè)；式（7）表示任意工件工序開始作業(yè)時(shí)間不小于該工序工件緊前工序的完工時(shí)間，同時(shí)約束了組合工序的開始時(shí)間大于等于其所有組成元素的工件緊前工序的結(jié)束時(shí)間；式（8）表示任意工序的開始作業(yè)時(shí)間非負(fù)，作業(yè)時(shí)間和完工時(shí)間大于0；式（9）和（10）表示組合工序OIJ的各元素Oij∈OIJ必須同時(shí)開始和同時(shí)完工。

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

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

2.1 編碼和解碼

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

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

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

算法1 順序解碼方法

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

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

c）OIJ的開始和完工時(shí)間分別為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ì)量和收斂速度。為增強(qiáng)初始解的質(zhì)量，在此采用混合初始化方式［23］，其中一半種群采用貪婪初始化方式生成，另一半種群采用隨機(jī)初始化方式生成?；诰幋a方式設(shè)計(jì)混合初始化種群生成算法，如算法2所示。

算法2 混合初始化種群

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

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

c）如果［1，N］全部被標(biāo)記，轉(zhuǎn)f）；反之，隨機(jī)選?。?，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尾部，并在該基因位補(bǔ)l－1個(gè)0；如果Oij為組合工序元素，轉(zhuǎn)d）。

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

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

f）生成（0，1）的隨機(jī)數(shù)r，若r<0.5，對(duì)于OPlan［k］，1≤k≤|OPlan|中工序OIJ，根據(jù)順序解碼選擇m=argmin{EIJm1，EIJm2，…，EIJmj}，m1，m2，…，mj∈MIJ作為作業(yè)機(jī)器；反之從MIJ中隨機(jī)選擇m作為OIJ作業(yè)機(jī)器；最后形成機(jī)器序列MPlan。進(jìn)一步確定各工序作業(yè)時(shí)間，生成作業(yè)時(shí)間序列TmPlan。存儲(chǔ)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ù)生成一個(gè)初始可行方案的示意，如圖3所示。假設(shè)算法2中步驟c）隨機(jī)生成了（3，0）（1，0）（4，0）（2，0）（1，0）（1，0）工件集序號(hào)表示的工序序列（如圖3中第一行），對(duì)應(yīng)工序分別為O31、O11、O41、O21、O12、O13。然后基于步驟c）隨機(jī)選取工件2，對(duì)應(yīng)工序O22、O22和O33形成組合工序，基于步驟d）在序列尾部放入O22、O33，對(duì)應(yīng)工件（2，3）（如圖3中第三行），但O33前驅(qū)工序O32未插入工序序列且O22、O33無前驅(qū)組合工序，基于步驟e）將O32對(duì)應(yīng)工件集編號(hào)3插入到（2，3）之前，并采用0補(bǔ)位（如圖3中的第四行），網(wǎng)格框?yàn)楣ぜ?隨機(jī)插入位置。在已生成工序序列基礎(chǔ)上基于步驟c）生成工件編號(hào)3的工序序列，對(duì)應(yīng)工序?yàn)镺34。繼續(xù)基于步驟c）隨機(jī)生成工件編號(hào)4，對(duì)應(yīng)工序O43，因?yàn)镺24和O43為組合工序O24、O43，基于步驟d）在序列尾部放入O24、O43，對(duì)應(yīng)工件（2，4）。但O24前驅(qū)工序中O23未進(jìn)行插入且O24、O43工件2存在前驅(qū)組合工序O22、O33，基于步驟e）將O23對(duì)應(yīng)工件編號(hào)2插入（2，4）和（2，3）之間，并采用0補(bǔ)位。根據(jù)步驟c）繼續(xù)選取未標(biāo)記的工件編號(hào)連同補(bǔ)位0一起加入工序序列尾部，直至1～4中所有數(shù)都被標(biāo)記，此時(shí)工序序列編碼完成，最終工序編碼序列如圖3中第五行所示。進(jìn)一步基于步驟f）生成對(duì)應(yīng)機(jī)器和作業(yè)時(shí)間序列，如圖中第六、七行所示。

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

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

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

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

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

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

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

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

為使交叉更加充分，在完成工序交叉后進(jìn)一步對(duì)機(jī)器編碼序列進(jìn)行多點(diǎn)交叉，具體步驟如下：

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

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

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

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

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

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

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

為獲得更優(yōu)種群并加速收斂，在此提出一種自適應(yīng)交叉變異算子。將種群中的個(gè)體分為三類：適應(yīng)度值f前20%的個(gè)體為優(yōu)良個(gè)體，應(yīng)降低交叉率和變異率來保留自身優(yōu)良基因；f倒數(shù)20%的個(gè)體為拙劣個(gè)體，應(yīng)提高交叉率和變異率以增加生成優(yōu)良個(gè)體的概率；其余個(gè)體稱為普通個(gè)體，以一個(gè)適中的交叉率和變異率進(jìn)行交叉和變異。分段函數(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表示個(gè)體i的適應(yīng)度值；s為極小的正實(shí)數(shù)。

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

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

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

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

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

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

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

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

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

圖8為針對(duì)MK05雙約束問題AHIGA所得最優(yōu)調(diào)度方案的甘特圖。可以看出，圖中所有工序均滿足工序作業(yè)順序約束、不同工序在同一機(jī)器上作業(yè)先后順序與強(qiáng)制同機(jī)并行作業(yè)約束等要求。

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

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

4 結(jié)束語

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

參考文獻(xiàn)：

［1］張潔， 秦威. 智能制造調(diào)度為先—《制造系統(tǒng)智能調(diào)度方法與云服務(wù)》導(dǎo)讀［J］. 中國機(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é)報(bào)： 工學(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］. 機(jī)械工程學(xué)報(bào)， 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ù)防性維護(hù)的分布式柔性作業(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］張國輝， 閆少峰， 陸熙熙， 等. 改進(jìn)混合多目標(biāo)蟻群算法求解帶運(yùn)輸時(shí)間和調(diào)整時(shí)間的柔性作業(yè)車間調(diào)度問題［J］. 計(jì)算機(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］. 計(jì)算機(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］王雷， 鄒新. 基于改進(jìn)免疫克隆選擇算法的柔性作業(yè)車間調(diào)度［J］. 南京理工大學(xué)學(xué)報(bào)， 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］吳銳， 郭順生， 李益兵， 等. 改進(jìn)人工蜂群算法求解分布式柔性作業(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］杜凌浩， 向鳳紅. 改進(jìn)多鄰域候鳥優(yōu)化算法的柔性作業(yè)車間調(diào)度研究［J］. 兵器裝備工程學(xué)報(bào)， 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］. 中國機(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ùn)輸時(shí)間的柔性作業(yè)車間調(diào)度［J］. 浙江大學(xué)學(xué)報(bào)： 工學(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］王無雙， 駱淑云. 基于強(qiáng)化學(xué)習(xí)的智能車間調(diào)度策略研究綜述［J］. 計(jì)算機(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é)報(bào)： 自然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］. 計(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 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.