基于孿生人工蜂鳥算法的多作業(yè)模式半導(dǎo)體封測環(huán)節(jié)調(diào)度

王洪 吳立輝 陳達(dá) 張潔

摘要 ：針對多作業(yè)模式的半導(dǎo)體封裝測試環(huán)節(jié)調(diào)度問題，以最小化最大完工時間為目標(biāo)，提出了孿生人工蜂鳥算法。設(shè)計(jì)了孿生種群機(jī)制，通過構(gòu)建雙解碼、孿生種群生成與協(xié)作方法，擴(kuò)大解的搜索空間，提高初始解的質(zhì)量，增加優(yōu)化過程中解的多樣性，進(jìn)而提高求解精度。通過雙向引導(dǎo)覓食策略，平衡算法多樣性與收斂性，增強(qiáng)算法穩(wěn)定性。通過構(gòu)建四鄰域搜索策略，增強(qiáng)算法局部優(yōu)化能力。實(shí)驗(yàn)結(jié)果表明，該方法能有效縮短半導(dǎo)體封測環(huán)節(jié)的最大完工時間。

關(guān)鍵詞 ：生產(chǎn)調(diào)度；半導(dǎo)體封裝測試；多作業(yè)模式；孿生人工蜂鳥算法

中圖分類號 ：TP18

DOI：10.3969/j.issn.1004-132X.2024.02.010

開放科學(xué)（資源服務(wù)）標(biāo)識碼（OSID）：

Scheduling in SAT in Multi-operation Mode Based on Artificial

Hummingbird Algorithm with Twin Population

WANG Hong ?1，2 ?WU Lihui 3 CHEN Da ?1，2 ?ZHANG Jie 2

1.College of Mechanical Engineering，Donghua University，Shanghai，201620

2.Institute of Artificial Intelligence，Donghua University，Shanghai，201620

3.College of Mechanical Engineering，Shanghai Institute of Technology，Shanghai，201418

Abstract ： In order to solve the scheduling problem of SAT in multi-operation mode， an artificial hummingbird algorithm with twin population was proposed with the goal of minimizing the maximum completion time. The twin population mechanism was designed to improve the solution accuracy. By double decoding， twin population generation and cooperation methods， the searching space for solutions was expanded， the quality of the initial population solution was improved， and the diversity of population solutions was increased in optimization processes. By the bidirectional-guiding foraging strategy， the relationship between algorithm diversity and convergence was balanced， and algorithm stability was enhanced. By the strategy of four-variable neighbor searching， the local optimization ability of the algorithm was enhanced. The test results show that the proposed method may effectively shorten the maximum completion time of the SAT.

Key words ： production scheduling；semiconductor assembly and test（SAT）；multi-operation mode；artificial hummingbird algorithm with twin population（AHA-TP）

0 引言

半導(dǎo)體封裝測試（semiconductor assembly and test， SAT）是半導(dǎo)體生產(chǎn)的重要環(huán)節(jié)，然而現(xiàn)階段的SAT生產(chǎn)組織主要依賴調(diào)度人員的經(jīng)驗(yàn)，具有較大局限性，因此急需兼顧求解時間與求解質(zhì)量的方法，縮短SAT環(huán)節(jié)的加工周期，提高企業(yè)生產(chǎn)效益。對SAT的4道關(guān)鍵工序（貼片/裝片、引線鍵合、塑封、電鍍）的調(diào)度進(jìn)行研究后，發(fā)現(xiàn)該調(diào)度問題具有多作業(yè)模式、設(shè)備工藝能力差異化、大規(guī)模等特點(diǎn)。SAT環(huán)節(jié)存在單機(jī)加工（引線鍵合）、批準(zhǔn)備單處理加工（電鍍）、批準(zhǔn)備批處理加工（貼片/裝片、塑封）三種作業(yè)模式，具有多作業(yè)模式的特點(diǎn)。引線鍵合與電鍍工序中，各設(shè)備組均只能加工特定工藝范圍的芯片且加工速度不一致，具有明顯的工藝能力差異特點(diǎn)。SAT加工車間通常具有上千臺加工設(shè)備，同時處理數(shù)十種產(chǎn)品、數(shù)百批芯片彈夾，具有大規(guī)模特點(diǎn)。多作業(yè)模式、設(shè)備工藝能力差異大、大規(guī)模等特點(diǎn)使SAT調(diào)度問題具有大規(guī)模解空間、可行解域扭曲畸形等特性，導(dǎo)致SAT調(diào)度問題優(yōu)化困難。

SAT車間調(diào)度問題是典型的NP-hard問題 ?［1］ ，國內(nèi)外學(xué)者對其進(jìn)行大量研究，提出了啟發(fā)式規(guī)則方法、整數(shù)規(guī)劃方法與智能優(yōu)化方法。

姚麗麗等 ?［2］ 提出一種結(jié)合邏輯約束與啟發(fā)式調(diào)度規(guī)則的方法，實(shí)現(xiàn)了SAT產(chǎn)線調(diào)度問題的優(yōu)化求解。CHEN等 ?［3］ 設(shè)計(jì)了一種調(diào)度規(guī)則自動生成框架，解決了不同生產(chǎn)擾動下的調(diào)度問題。ZHANG等 ?［4］ 利用調(diào)度規(guī)則解決了智能作業(yè)車間調(diào)度問題。以上啟發(fā)式規(guī)則方法具有求解快的優(yōu)點(diǎn)，但調(diào)度解的質(zhì)量欠佳。

APPELO等 ?［5］ 將混合整數(shù)規(guī)劃方法用于半導(dǎo)體測試工序的調(diào)度優(yōu)化。MENG等 ?［6］ 提出一種新的混合整數(shù)規(guī)劃模型用于解決分布式混合流水車間調(diào)度問題。QIU等 ?［7］ 提出一種統(tǒng)一的混合整數(shù)線性規(guī)劃（MILP）求解框架用于電力調(diào)度。以上整數(shù)規(guī)劃方法雖能得到最優(yōu)解，但求解較大規(guī)模問題的時間過長。

為解決求解質(zhì)量欠佳與求解較慢的問題，借鑒自然界優(yōu)化規(guī)律的智能優(yōu)化算法被大量研究。WANG等 ?［8］ 將合作迭代貪婪算法（CIG）用于解決分布式流水車間群的調(diào)度問題。WANG等 ?［9］ 提出一種多子種群并行計(jì)算遺傳算法（MSPCGA）來解決實(shí)際生產(chǎn)約束下的SAT調(diào)度問題。CHIU等 ?［10］ 提出一種進(jìn)化優(yōu)化算法來解決SAT環(huán)節(jié)中具有靈活拆分規(guī)則的訂單分配問題。牛昊一等 ?［11］ 利用自適應(yīng)樽海鞘群算法解決了柔性作業(yè)車間的調(diào)度問題。梁望等 ?［12］ 通過兩階段智能優(yōu)化算法解決了緊湊型帶鋼生產(chǎn)熱軋調(diào)度問題。然而，現(xiàn)有面向SAT調(diào)度的智能優(yōu)化算法具有求解效率不高等問題。

人工蜂鳥算法（artificial hummingbird algorithm， AHA）具有搜索效率高的特點(diǎn)，且該方法的尋優(yōu)效率與優(yōu)化效果優(yōu)于遺傳算法、粒子群算法、海鞘群算法等群智能優(yōu)化算法 ?［13］ 。然而，針對具有解空間規(guī)模大、可行解域扭曲畸形等特征的SAT調(diào)度問題，該方法存在收斂慢、易于陷入局部最優(yōu)等 不足。

本文提出一種孿生人工蜂鳥算法（artificial hummingbird algorithm with twin population， AHA-TP）來解決SAT環(huán)節(jié)調(diào)度問題。首先，通過設(shè)計(jì)孿生種群機(jī)制，構(gòu)建雙解碼、孿生種群生成與協(xié)作方法，提高蜂鳥種群初始解的質(zhì)量，增加優(yōu)化過程中種群解的多樣性，提高求解精度。其次，通過構(gòu)建雙向引導(dǎo)覓食策略，加快孿生蜂鳥種群的收斂，平衡算法多樣性與收斂性的關(guān)系。最后，設(shè)計(jì)四鄰域搜索策略，避免孿生蜂鳥種群陷入局部最優(yōu)搜索的瓶頸，提高算法的局部搜索優(yōu)化能力，實(shí)現(xiàn)SAT問題的高效優(yōu)化求解。

1 問題描述與建模

1.1 問題描述

SAT 環(huán)節(jié)的實(shí)際生產(chǎn)中， Lot 常作為調(diào)度的基本單元。本文所提多作業(yè)模式下的 SAT 調(diào)度問題描述如下：n個 Lot （工件）經(jīng)過K個階段的加工，每個 Lot 在不同階段的作業(yè)模式不同，階段k（k=1，2，…，K）有m k臺設(shè)備。本文以最小化最大完工時間C ??max ?為調(diào)度目標(biāo)，作出以下假設(shè)： ①Lot在不同設(shè)備上的加工時間已知；②初始時刻，所有Lot與設(shè)備均準(zhǔn)備就緒；③加工順序固定，即所有Lot需按同一順序加工；④每一階段存在多臺非等效的并行機(jī)，同一Lot在每階段不同設(shè)備上的加工時間不同；⑤各個加工階段中，Lot只能在一臺設(shè)備上加工；⑥任何時刻，一個Lot只能在一臺設(shè)備上加工；⑦加工一旦開始就不能 中斷。

1.2 問題建模

為數(shù)學(xué)描述 SAT 車間調(diào)度問題，定義表1所示的參數(shù)符號。

SAT 調(diào)度模型目標(biāo)函數(shù)為

min ?C ??max ?= min （ max （C 1，C 2，…，C n）） ?（1）

模型約束條件如下：

E ?i，k，j ≤B ?i，k+1，j ??（2）

∑ m ??k j=1 X ?i，k，j =1 ?（3）

P ?i，k，j =∑ m ??k j=1 ?X ?i，k，j W ?i，k，j ?v ?k，j ???（4）

E ?i，k，j =B ?i，k，j +P ?i，k，j ??（5）

B ?i+1，k，j =E ?i，k，j ??（6）

式（1）為目標(biāo)函數(shù)即最小化最大加工時間；式（2）表示 Lot ?i當(dāng)前工序的開始時間在上道工序之后；式（3）表示 Lot ?i每階段僅在一臺設(shè)備上加工；式（4）表示 Lot ?i在各工序中的完工時間；式（5）表示 Lot ?i的完工時間為該 Lot ?i開始加工時間與該階段處理時間之和；式（6）表示在k階段設(shè)備j上的 Lot ?i加工結(jié)束時間為 Lot ??i+1 加工開始 時間。

2 基于AHA-TP的SAT調(diào)度方法

2.1 人工蜂鳥算法

人工蜂鳥算法模擬蜂鳥群在多維搜索空間的飛行，尋找待優(yōu)化問題的最優(yōu)解 ?［13］ 。人工蜂鳥算法設(shè)計(jì)了“蜂鳥”的3種飛行方式（一維、多維和全維度的搜索），3種覓食方式（引導(dǎo)覓食、領(lǐng)域覓食、遷移覓食），以及訪問表。引導(dǎo)覓食和領(lǐng)域覓食時，“蜂鳥”選擇一種飛行方式來改變自身位置，從而獲得新解，并根據(jù)新解的優(yōu)劣情況更新原“蜂鳥”代表的解。遷徙覓食時，隨機(jī)生成新解替換掉原“蜂鳥”種群中適應(yīng)值最差的解。訪問表用于指導(dǎo)“蜂鳥”在引導(dǎo)覓食過程中選擇候選食物源，若迭代過程中尋找到更優(yōu)秀的解，則“蜂鳥”在訪問表中的被訪問值會成為最大值，并在下次引導(dǎo)覓食過程中優(yōu)先引導(dǎo)“蜂鳥”。每次覓食結(jié)束后，訪問表會根據(jù)覓食類型與當(dāng)前“蜂鳥”位置是否變得更優(yōu)，進(jìn)行不同方式的更新。

人工蜂鳥算法的流程如圖1所示，具體步驟如下：

（1）種群初始化，即通過隨機(jī)生成的方式得到初始種群。

（2） 種群個體隨機(jī)進(jìn)行引導(dǎo)覓食或領(lǐng)域覓食。

（3）若迭代次數(shù)為遷移系數(shù)MC的倍數(shù)，則進(jìn)入步驟（4），否則進(jìn)入步驟（5）；

（4） “蜂鳥”種群進(jìn)行遷徙覓食。

（5）若達(dá)到最大迭代次數(shù)，則結(jié)束迭代并輸出最優(yōu)解，否則進(jìn)入步驟（2）。

2.2 AHA-TP算法框架

為對SAT調(diào)度問題進(jìn)行高效求解，本文對AHA進(jìn)行改進(jìn)，提出了AHA-TP。AHA-TP的主要改進(jìn)措施包括：①引入孿生種群機(jī)制，通過雙解碼、孿生種群生成與協(xié)作方法增大解的搜索空間，提高種群初始解的質(zhì)量，增加優(yōu)化過程中種群解的多樣性，提高算法的求解精度；②實(shí)施雙向引導(dǎo)覓食策略，通過設(shè)計(jì)最優(yōu)引導(dǎo)覓食與訪問引導(dǎo)覓食，平衡種群解的多樣性與收斂性，增強(qiáng)算法的穩(wěn)定性；③運(yùn)用四鄰域搜索策略，通過設(shè)計(jì)的4種鄰域搜索方式增強(qiáng)算法的局部優(yōu)化能力，加快算法收斂。AHA-TP的流程如圖2所示，具體步驟如下：

（1）令迭代次數(shù)為I ??total ?，種群數(shù)量為P ??size ?，基于雙解碼策略生成孿生種群，完成種群初始化。

（2） “蜂鳥”個體基于雙向引導(dǎo)覓食策略進(jìn)行覓食。迭代次數(shù)I≤I ??total ?/2時，“蜂鳥”個體進(jìn)行訪問引導(dǎo)覓食，否則進(jìn)行最優(yōu)引導(dǎo)覓食。

（3）若迭代次數(shù)為P ??size ?/2的倍數(shù)，則進(jìn)入步驟（4），否則進(jìn)入步驟（5）。

（4）對孿生種群進(jìn)行四鄰域搜索。

（5）若迭代次數(shù)為P ??size ?的倍數(shù)，則進(jìn)入步驟（6），否則進(jìn)入步驟（7）。

（6）對孿生種群進(jìn)行孿生種群協(xié)作。

（7）若達(dá)到最大迭代次數(shù)，則結(jié)束迭代并輸出最優(yōu)解，否則進(jìn)入步驟（2）。

2.3 編碼

本文采用基于操作的編碼方式 ?［14］ ，將所有Lot的一種排序作為一個“蜂鳥”個體，Lot在“蜂鳥”個體中的位置序號為該Lot的加工順序。

2.4 孿生種群機(jī)制

為擴(kuò)大解搜索空間，提高種群初始解的質(zhì)量與種群解在增加優(yōu)化過程中的多樣性，設(shè)計(jì)了雙解碼、孿生種群生成與協(xié)作方法，形成孿生種群 機(jī)制。

2.4.1 孿生種群雙解碼

本文設(shè)計(jì)的雙解碼策略包括正向解碼與反向解碼。

正解碼從第一道工序開始，解碼過程考慮2個子問題：①Lot在每階段的加工順序；②Lot在每階段的設(shè)備分配。對于Lot加工順序，解碼采用“先進(jìn)先出”（first in first out， FIFO）規(guī)則完成Lot序列的分配。對于設(shè)備分配，采取最先加工結(jié)束設(shè)備優(yōu)先的原則即選擇min（ E ?i，K，j ?）對應(yīng)的設(shè)備 j ，當(dāng)存在多個相等的min（ E ?i，K，j ?）時，正向解碼選擇序號更小的設(shè)備。

反向解碼從第四道工序開始，解碼過程與正解碼方式相似，但有兩點(diǎn)不同：①反向解碼過程中，可將第四工序（該工序?yàn)榕鷾?zhǔn)備單處理加工模式）按照單機(jī)加工模式進(jìn)行解碼，調(diào)度結(jié)果依舊滿足批準(zhǔn)備單處理加工模式的約束；②對于設(shè)備分配，當(dāng)存在多個相等的min（ E ?i，K，j ?）時，反向解碼選擇序號更大的設(shè)備。圖3為編碼{2，7，8，3，4，6，9，10，5，1}采用兩種解碼方式得到的甘特圖。

2.4.2 孿生種群生成

本文結(jié)合雙解碼提出一種基于孿生種群的初始化方法，如圖4所示，圖中，上標(biāo)p表示正向解碼，n表示反向解碼。首先，基于隨機(jī)數(shù)方式生成 P ??size 個“蜂鳥”個體；其次，對所有初始化個體進(jìn)行正解碼，并按照適應(yīng)值排序；然后，通過間隔篩選個體的方式，抽取出排序靠前的若干個體構(gòu)建正孿生種群。同理，對隨機(jī)種群進(jìn)行反解碼，按適應(yīng)度值進(jìn)行排序，并通過間隔篩選獲得反孿生種群。最后，合并正反孿生種群，得到孿生種群。

2.4.3 孿生種群協(xié)作

為增加種群解在優(yōu)化過程中的多樣性，算法設(shè)計(jì)了孿生種群協(xié)作策略。如圖5所示，該策略包括孿生種群解碼逆序、臨時種群解碼適應(yīng)值排序、交叉協(xié)作等，具體步驟如下。

（1）孿生種群解碼逆序。先對正孿生種群P ?p ?0、反孿生種群P ?n ?0進(jìn)行適應(yīng)值排序，再對排序后的種群個體進(jìn)行解碼，并對得到的編碼進(jìn)行逆序操作，獲得末階段、初階段的 Lot 編碼，形成臨時反孿生種群P ?n ?1、正孿生種群P ?p ?1。

（2） 臨時種群解碼適應(yīng)值排序。對P ?p ?1、P ?n ?1分別進(jìn)行正反解碼，并根據(jù)適應(yīng)度值大小進(jìn)行排序。

（3）交叉協(xié)作。從P ?p ?1中選出排序前α的個體替換掉P ?p ?0中排序后α的個體，從P ?n ?1中選出排序前α的個體替換掉P ?n ?0中排序后α的個體，形成新的正孿生種群P ?p ?2、反孿生種群P ?n ?2。

2.5 雙向引導(dǎo)覓食策略

為平衡種群的多樣性與收斂性，并增強(qiáng)算法的穩(wěn)定性，本文設(shè)計(jì)了雙向引導(dǎo)覓食策略，包括訪問引導(dǎo)覓食與最優(yōu)引導(dǎo)覓食。當(dāng)?shù)螖?shù)I≤I ??total ?/2時，“蜂鳥”個體B 0進(jìn)行訪問引導(dǎo)覓食，由訪問表中最大引導(dǎo)值對應(yīng)的“蜂鳥”B ?G 進(jìn)行引導(dǎo)；當(dāng)?shù)螖?shù)I>I ??total ?/2時，進(jìn)行最優(yōu)引導(dǎo)覓食，即讓當(dāng)前適應(yīng)值最小的“蜂鳥”個體B ??mfit ?引導(dǎo)“蜂鳥”個體B 0。覓食結(jié)束后，生成新的“蜂鳥”個體B 1與B 2，比較B 0、B 1與B 2的適應(yīng)值，將適應(yīng)值最小的“蜂鳥”個體替換B 0，并更新訪問表。訪問表更新規(guī)則參考文獻(xiàn)［13］。3種飛行方式對應(yīng)的引導(dǎo)覓食如圖6所示。

2.6 四鄰域搜索策略

為增強(qiáng)算法的局部優(yōu)化能力，本文設(shè)計(jì)了四鄰域搜索策略，即每經(jīng)過P ??size ?/2次迭代，對正反孿生種群適應(yīng)值排序前N ?S 的個體進(jìn)行變鄰域搜索，每種鄰域搜索方式針對種群個體進(jìn)行N ??nb ?次搜索。

變鄰域搜索按照搜索范圍從大到小的順序，依次進(jìn)行多點(diǎn)互換、反轉(zhuǎn)逆序、插入與兩點(diǎn)互換。多點(diǎn)互換：選擇3～n個位置的編碼進(jìn)行隨機(jī)排序。反轉(zhuǎn)逆序：隨機(jī)取出一段編碼進(jìn)行逆序。插入：隨機(jī)取兩個位置，將后一位置的編碼插入至前一位置的編碼所在位置，原編碼依次后退一位。兩點(diǎn)互換：隨機(jī)抽取兩個位置更換編碼。四鄰域搜索策略如圖7所示。

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

為驗(yàn)證AHA-TP求解多作業(yè)模式下SAT調(diào)度問題的有效性，基于某半導(dǎo)體封測企業(yè)數(shù)據(jù)，設(shè)計(jì)了驗(yàn)證案例進(jìn)行實(shí)驗(yàn)。實(shí)驗(yàn)驗(yàn)證分為實(shí)驗(yàn)設(shè)計(jì)、算法參數(shù)實(shí)驗(yàn)、算法改進(jìn)有效性實(shí)驗(yàn)和案例測試四個環(huán)節(jié)。

3.1 實(shí)驗(yàn)設(shè)計(jì)

根據(jù)某半導(dǎo)體封測工廠實(shí)際生產(chǎn)數(shù)據(jù)，設(shè)計(jì)了三種規(guī)模的案例，如表2所示，其中，J i、M i分別為 Lot 數(shù)量和四階段（貼片/裝片、引線鍵合、塑封和電鍍）設(shè)備數(shù)量。考慮貼片/裝片、塑封批處理加工特性，設(shè)定兩階段加工時間為W 1=60，W 3=120，相對加工速度為v 1，v 3=1.00（W 1、W 3分別為第一階段與第三階段的加工時間，v 1、v 3分別為第一階段與第三階段的相對加工速度）；考慮引線鍵合、電鍍單處理加工特性，設(shè)定第二階段與第四階段的加工時間為W 2∈［60，90］，W 4∈［45，60］，相對加工速度v 2，v 4∈{1.00，1.25， 1.50}， 具體的加工時間和相對加工速度為區(qū)間或集合內(nèi)均勻分布的隨機(jī)數(shù)。 實(shí)驗(yàn)環(huán)境為Win10系統(tǒng)，CPU為i5-12400f、內(nèi)存為16GB，采用python3.6編程，編譯器為PyCharm2021。

3.2 算法參數(shù)實(shí)驗(yàn)

參數(shù)設(shè)置會對 AHA-TP 性能產(chǎn)生較大影響，其中的關(guān)鍵參數(shù)為種群數(shù)量P ??size ?和變鄰域搜索的次數(shù)N ??nb ?。 AHA-TP 參數(shù)水平的取值見表3。基于中規(guī)模案例數(shù)據(jù)確定P ??size ?與N ??nb ?，該案例中的 Lot 數(shù)量為30，四階段設(shè)備數(shù)量{3，6，6，6}。對每一組參數(shù)組合獨(dú)立運(yùn)行算法10次，每次進(jìn)行2000次迭代，以最小適應(yīng)值的均值為評價(jià)指標(biāo)。

AHA-TP 參數(shù)實(shí)驗(yàn)的結(jié)果如表4所示，對實(shí)驗(yàn)結(jié)果進(jìn)行分析處理，得到表5所示的分析結(jié)果。表5中，T 1～T 4為兩參數(shù)對應(yīng)水平的適應(yīng)值均值之和，t 1～t 4為兩參數(shù)對應(yīng)水平的適應(yīng)值均值的平均值。 對比表5中的極差可知，P ??size ?對算法效果的影響程度大于N ??nb ?的影響。由表5可得，P ??size ??為水平2、N ??nb ?為水平3時， AHA-TP 的效果最好，即 AHA-TP 設(shè)定的最佳參數(shù)為P ??size ?=60，N ??nb ?=30。

3.3 算法改進(jìn)有效性實(shí)驗(yàn)

為驗(yàn)證AHA-TP改進(jìn)策略的有效性，基于中等規(guī)模算例將AHA-TP與AHA-1、AHA-2、AHA-3、AHA-4進(jìn)行對比，其中，AHA-1為AHA-TP去掉孿生種群機(jī)制中的孿生種群生成方法的優(yōu)化算法，AHA-2為AHA-TP去掉孿生種群機(jī)制中的孿生種群協(xié)作方法的優(yōu)化算法，AHA-3為AHA-TP去掉雙向引導(dǎo)策略的優(yōu)化算法，AHA-4為AHA-TP去掉四鄰域搜索策略的優(yōu)化算法。

由表6可得如下結(jié)果：①AHA-TP與AHA-1的比較結(jié)果表明，孿生種群生成方法使適應(yīng)值的均值差（均值與已發(fā)現(xiàn)最小值531.00之差）減小84%，標(biāo)準(zhǔn)差減小60%，增大了搜索空間，提高了算法求解精度;②AHA-TP與AHA-2的比較結(jié)果表明，孿生種群協(xié)作方法使適應(yīng)值均值減小37%，標(biāo)準(zhǔn)差減小41%，增加了優(yōu)化過程中種群解的多樣性，避免算法陷入局部最優(yōu);③AHA-TP與AHA-3的比較結(jié)果表明，雙向引導(dǎo)覓食策略設(shè)計(jì)使適應(yīng)值均值減小32%，標(biāo)準(zhǔn)差減小49%，平衡了算法的收斂性與多樣性，增強(qiáng)了算法的穩(wěn)定性；④AHA-TP與AHA-4的比較結(jié)果表明，四鄰域搜索策略設(shè)計(jì)使適應(yīng)值均值減小72%，標(biāo)準(zhǔn)差減小60%，最優(yōu)值迭代數(shù)的均值減小17%，增強(qiáng)了算法的局部優(yōu)化能力。

3.4 案例測試

為驗(yàn)證AHA-TP在多作業(yè)模式下SAT調(diào)度問題上的有效性，將其與AHA和改進(jìn)遺傳算法（improved genetic algorithm， IGA）進(jìn)行比較。對比指標(biāo)包括最大加工完工時間（適應(yīng)值）的最小值、均值、均值差（均值與最小值之差）、最大值、最大值差（最大值與最小值之差）、標(biāo)準(zhǔn)差。為減小隨機(jī)性對實(shí)驗(yàn)的影響，3個算法在每個案例上運(yùn)行15次，迭代次數(shù)為2000。為保證實(shí)驗(yàn)的有效性，AHA和IGA的種群規(guī)模與AHA-TP一致，均為60。IGA的交叉概率和變異概率分別設(shè)為0.9和0.1，采用隨機(jī)多點(diǎn)交叉操作和兩點(diǎn)交換變異操作。AHA與IGA采用正向解碼，通過隨機(jī)數(shù)的方式生成初始種群。實(shí)驗(yàn)結(jié)果如表7、表8所示。

由表7、表8可知：①AHA-TP在小規(guī)模案例中的最小值、均值與最大值的平均值分別為 546.86、 546.88、547.20，在中規(guī)模案例中的最小值、均值與最大值的平均值分別為538.56、 540.43、 542.74，在大規(guī)模案例中的最小值、均值與最大值的平均值分別為594.44、596.50、 598.60， 均優(yōu)于AHA與IGA，說明AHA-TP的求解精度優(yōu)于AHA與IGA；②AHA-TP在小規(guī)模案例中的均值差與最大值差的平均值分別為 0.02、 0.34，在中規(guī)模案例中的均值差與最大值差的平均值分別為1.87、4.18，在大規(guī)模案例中的均值差與最大值差的平均值分別為2.06、4.16，均優(yōu)于AHA與IGA；③AHA-TP在小、中、大規(guī)模案例中的標(biāo)準(zhǔn)差平均值為0.08、1.09、1.12，在中規(guī)模、大規(guī)模案例中優(yōu)于AHA，而稍遜于IGA，說明AHA-TP的穩(wěn)定性優(yōu)于AHA，而稍遜于IGA。圖8中，AHA-TP與AHA的箱型圖中位線均低于IGA， 且相對于AHA，AHA-TP解的最大值與最小值之差更小， 即算法求解精度與穩(wěn)定性得到提高。綜上所述，AHA-TP在解決SAT調(diào)度問題上具有良好優(yōu)化效果，能有效最大完工時間。

4 結(jié)語

本文研究了以最小化最大完工時間為目標(biāo)的多作業(yè)模式下SAT調(diào)度問題，提出了基于AHA-TP的SAT調(diào)度方法。該方法主要改進(jìn)如下：①設(shè)計(jì)了孿生種群機(jī)制策略，完成AHA-TP種群的初始化，擴(kuò)大了解的搜索空間，提高了初始種群解的質(zhì)量，在優(yōu)化過程中增加了解的多樣性；②改進(jìn)了AHA-TP中的雙向引導(dǎo)覓食尋優(yōu)策略，平衡了算法多樣性與收斂性，增強(qiáng)了算法的穩(wěn)定性；③AHA-TP增加了四鄰域搜索策略，增強(qiáng)了算法局部優(yōu)化能力。案例實(shí)驗(yàn)結(jié)果證明了AHA-TP的性能，可有效縮短SAT調(diào)度問題的最大完工時間。在SAT調(diào)度實(shí)際應(yīng)用中，AHA-TP可與半導(dǎo)體封測車間MES系統(tǒng)緊密結(jié)合，從MES獲取數(shù)據(jù)，計(jì)算并反饋優(yōu)化結(jié)果給MES，實(shí)現(xiàn)生產(chǎn)線的調(diào)度優(yōu)化。

在未來研究中，為貼近實(shí)際生產(chǎn)情況，可考慮包括換機(jī)時間、資源約束等更多約束，以及總拖期時間、總能耗、總排放等其他性能指標(biāo)。

參考文獻(xiàn) ：

［1］ ?CHEN ?Jianbin， PENG Jiayu， LIN D K J. A Statistical Perspective on Non-deterministic Polynomial-time Hard Ordering Rroblems：Making Use of Design for Order-of-addition Experiments［J］. Computers & Industrial Engineering， 2021， 162：107773.

［2］ ?姚麗麗，史海波，劉昶. 半導(dǎo)體封裝測試生產(chǎn)線排產(chǎn)研究［J］. 自動化學(xué)報(bào)， 2014（5）：892-900.

YAO Lili， SHI Haibo， LIU Xu. Research on Scheduling in Semiconductor Assembly and Test Manufacturing［J］. Acta Automatica Sinica， 2014（5）：892-900.

［3］ ?CHEN ?Xiaowu， JIANG Guozhang， XIAO Yongmao， et al. A Hyper Heuristic Algorithm Based Genetic Programming for Steel Production Scheduling of Cyber-physical System-oriented［J］. Mathematics， 2021， 9（18）：2256.

［4］ ?ZHANG ?Liping， HU Yifan， WANG Chuangjian， et al. Effective Dispatching Rules Mining Based on Near-optimal Schedules in Intelligent Job Shop Environment［J］. Journal of Manufacturing Systems， 2022， 63：424-438.

［5］ ?APPELLO ?D， LAURINO M， PRANZO M. A Mathematical Model to Assess the Influence of Parallelism in a Semiconductor Back-end Test Floor［C］∥2017 International Test Conference in Asia （ITC-Asia）. Taipei， 2017：138-143.

［6］ ?MENG ?Leilei， GAO Kaizhou， REN Yaping， et al. Novel MILP and CP Models for Distributed Hybrid Flowshop Scheduling Problem with Sequence- dependent ?Setup Times［J］. Swarm and Evolutionary Computation， 2022， 71：101058.

［7］ ?QIU ?Haifeng， GOOI H B. A Unified MILP Solution Framework for Adaptive Robust Scheduling Problems with Mixed-Integer Recourse Objective［J］. IEEE Transactions on Power Systems， 2022， 38（1）：952-955.

［8］ ?WANG ?Yuhang， HAN Yuyan， WANG Yuting， et al. Intelligent Optimization under the Makespan Constraint：Rapid Evaluation Mechanisms Based on the Critical Machine for the Distributed Flowshop Group Scheduling Problem［J/OL］. European Journal of Operational Research， 2023［2023-10-23］. https：∥doi.org/10.1016/j.ejor.2023.05.010.

［9］ ?WANG ?H K， LIN Y C， LIANG C J， et al. Multi-subpopulation Parallel Computing Genetic Algorithm for the Semiconductor Packaging Scheduling Problem with Auxiliary Resource Constraints［J］. Applied Soft Computing， 2023， 142：110349.

［10］ ?CHIU ?C C， LAI C M， CHEN C M. An Evolutionary Simulation-optimization Approach for the Problem of Order Allocation with Flexible Splitting Rule in Semiconductor Assembly［J］. Applied Intelligence， 2023， 53（3）：2593-2615.

［11］ ?牛昊一，吳維敏，章庭棋， 等.自適應(yīng)樽海鞘群算法求解考慮運(yùn)輸時間的柔性作業(yè)車間調(diào)度［J］.浙江大學(xué)學(xué)報(bào)（工學(xué)版），2023，57（7）：1267-1277.

NIU Haoyi， WU Weimin， ZHANG Tingqi， et al. Adaptive Zunhei Scabbard Swarm Algorithm for Flexible Job Shop Scheduling Considering Transportation Time［J］. Journal of Zhejiang University （Engineering Edition）， 2023，57（7）：1267-1277.

［12］ ?梁望，錢斌，胡蓉， 等.兩階段智能優(yōu)化算法求解緊湊型帶鋼生產(chǎn)熱軋調(diào)度問題［J/OL］.計(jì)算機(jī)集成制造系統(tǒng)， 2023［2023-10-23］. http：∥kns.cnki.net/kcms/detail/11.5946.TP.20230801.1648.007.html.

LIANG Wang， QIAN Bin， HU Rong et al. A Two-stage Intelligent Optimization Algorithm for Solving the Hot Rolling Scheduling Problem of Compact Strip Production［J/OL］. Computer Integrated Manufacturing System， 2023［2023-10-23］. http：∥kns.cnki.net/kcms/detail/11.5946.TP.20230801.1648.007.html.

［13］ ?ZHAO ?Weiguo， Wang Liying， MIRJALILI S. Artificial Hummingbird Algorithm：a New Bio-inspired Optimizer with Its Engineering Applications［J］. Computer Methods in Applied Mechanics and Engineering， 2022， 388：114194.

［14］ ?崔琪，吳秀麗，余建軍. 變鄰域改進(jìn)遺傳算法求解混合流水車間調(diào)度問題［J］. 計(jì)算機(jī)集成制造系統(tǒng)， 2017， 23（9）：1917-1927.

CUI Qi， WU Xiuli， YU Jianjun. Improved Genetic Algorithm Variable Neighborhood Search for Solving Hybrid Flow Shop Scheduling Problem［J］. Computer Integrated Manufacturing System， 2017， 23（9）：1917-1927.

（ 編輯 張 洋 ）

作者簡介 ：

王 洪 ，男，2000年生，碩士研究生。研究方向?yàn)閺?fù)雜制造系統(tǒng)調(diào)度、制造大數(shù)據(jù)分析。E-mail：2221044@mail.dhu.edu.cn。

張 潔 （通信作者），女，1963 年生，教授、博士研究生導(dǎo)師。研究方向?yàn)榇髷?shù)據(jù)驅(qū)動的智能制造系統(tǒng)、制造系統(tǒng)的建模仿真調(diào)度，發(fā)表論文100余篇。E-mail：mezhangjie@dhu.edu.cn。