陸志強(qiáng)，王浩宇

（同濟(jì)大學(xué)機(jī)械與能源工程學(xué)院，上海201804）

飛機(jī)總裝脈動生產(chǎn)線因其產(chǎn)線平穩(wěn)、生產(chǎn)柔性高，已經(jīng)廣泛應(yīng)用于大型飛機(jī)的裝配過程［1］。在飛機(jī)總裝脈動生產(chǎn)線的生產(chǎn)過程中，裝配線被劃分為多個資源共享的裝配單元，總裝過程被拆分為多個作業(yè)子集分配到各裝配單元上，每個作業(yè)子集包含多個作業(yè)，這些作業(yè)子集可以視為飛機(jī)總裝項(xiàng)目的子項(xiàng)目。飛機(jī)沿生產(chǎn)線方向依次緩慢通過各單元，同時各單元按照裝配計劃完成裝配作業(yè)。在一個裝配周期內(nèi)，多架飛機(jī)在多個裝配單元上同時進(jìn)行裝配。因此，飛機(jī)總裝脈動生產(chǎn)線的調(diào)度問題可抽象為一類多項(xiàng)目調(diào)度問題。此外，當(dāng)一類飛機(jī)裝配項(xiàng)目生產(chǎn)結(jié)束時，需要對生產(chǎn)線上的各類資源進(jìn)行調(diào)整，以適應(yīng)新的裝配項(xiàng)目。在原項(xiàng)目到新項(xiàng)目的轉(zhuǎn)換過程中，原類型飛機(jī)不斷完工離開生產(chǎn)線，新類型飛機(jī)逐漸進(jìn)入各裝配單元，這種2個項(xiàng)目在裝配線上共存的時期，稱為項(xiàng)目轉(zhuǎn)換期。由于2個項(xiàng)目的資源需求和節(jié)拍時間的差異，原有調(diào)度計劃可能無法正常實(shí)施，致使項(xiàng)目延期，因此需要對項(xiàng)目轉(zhuǎn)換期內(nèi)的裝配計劃進(jìn)行調(diào)整，重新分配各裝配單元對應(yīng)的作業(yè)子集，調(diào)整作業(yè)時間，制定新的裝配計劃以優(yōu)化轉(zhuǎn)換過程，縮短項(xiàng)目工期。目前針對這類問題的研究較少，實(shí)際生產(chǎn)時多采用犧牲生產(chǎn)效率、降低裝配線速度的方式適應(yīng)新項(xiàng)目。

為了研究飛機(jī)總裝脈動生產(chǎn)線的節(jié)拍轉(zhuǎn)換過程，提出了基于項(xiàng)目拆分的資源受限項(xiàng)目節(jié)拍轉(zhuǎn)換調(diào)度問題（RCPTTSP-PS）。RCPTTSP-PS在理論上是一類具有多項(xiàng)目并行調(diào)度、復(fù)雜約束并且考慮時空多維度的大規(guī)模多項(xiàng)目協(xié)同調(diào)度問題。目前尚沒有對RCPTTSP-PS的直接研究，但是對基礎(chǔ)的多項(xiàng)目協(xié)同調(diào)度問題（RCMPSP）的研究已經(jīng)十分透徹。學(xué)界常見的求解RCMPSP的方法有2種，即Goncalves等［2］提出的組合方法和Kurtulus等［3］提出的獨(dú)立方法，前者是通過虛任務(wù)將多項(xiàng)目連接成單項(xiàng)目后求解，后者是對每個項(xiàng)目給出各自的關(guān)鍵路徑進(jìn)行并行求解。Browning等［4］認(rèn)為第二種方法更加貼近真實(shí)情況，將是多項(xiàng)目問題求解的方向。RCMPSP是一個NP難題［5］，無法使用精確算法求解，因此學(xué)界多采用啟發(fā)式算法和元啟發(fā)算法進(jìn)行求解。優(yōu)先級規(guī)則是啟發(fā)式算法的主流，Browning等［4］對20種主流的優(yōu)先級規(guī)則進(jìn)行了評價，對于不同的項(xiàng)目特性給出了不同優(yōu)先級規(guī)則使用的建議。Wang等［6］和Kurtulus［7］分別引入了隨機(jī)作業(yè)時長和不同的項(xiàng)目延遲懲罰，并分析了相同的優(yōu)先級規(guī)則在不同環(huán)境下的求解質(zhì)量和魯棒性。元啟發(fā)算法相較于啟發(fā)式算法，求解精度更高，但是迭代時間長，適用于靜態(tài)項(xiàng)目求解。Kim等［8］提出了一種使用模糊邏輯控制器進(jìn)行參數(shù)調(diào)整的混合遺傳算法以求解RCMPSP；陳俊杰等［9］提出了以蟻群算法為基礎(chǔ)的兩階段算法，對考慮柔性資源的RCMPSP效果顯著；陳浩杰等［10］使用超啟發(fā)式遺傳規(guī)劃算法，對多目標(biāo)RCMPSP進(jìn)化出最優(yōu)的優(yōu)先級規(guī)則。

對RCMPSP的擴(kuò)展問題——基于項(xiàng)目拆分的資源受限項(xiàng)目調(diào)度問題（RCPMSP-PS），由陸志強(qiáng)等［11］首先提出并進(jìn)行了詳細(xì)闡述，根據(jù)項(xiàng)目拆分的特點(diǎn)，設(shè)計了雙層迭代算法進(jìn)行求解。朱宏偉等［12］在RCMPSP-PS的基礎(chǔ)上，提出了考慮資源轉(zhuǎn)移時間的RCMPSP-PS問題，通過自適應(yīng)遺傳算法有效避免了不合理的資源轉(zhuǎn)移。宗保氏等［13］在RCMPSP-PS的基礎(chǔ)上提出了考慮項(xiàng)目拆分的資源投入調(diào)度問題，通過遺傳算法進(jìn)行搜索，以優(yōu)化項(xiàng)目過程的資源投入。在考慮新項(xiàng)目加入調(diào)度方面，Chen等［14］考慮了突發(fā)訂單對生產(chǎn)線的干擾，并對基礎(chǔ)計劃利用優(yōu)先級規(guī)則進(jìn)行實(shí)時調(diào)整；Yassine等［15］對產(chǎn)品開發(fā)過程中具有優(yōu)先級的項(xiàng)目迭代過程進(jìn)行了建模分析，并利用遺傳算法求解，最終給出了可供管理者使用的決策矩陣。Abrantes等［16］對產(chǎn)品開發(fā)過程也進(jìn)行了研究，重點(diǎn)分析產(chǎn)品開發(fā)過程中新項(xiàng)目開始時的人力資源再分配問題，通過跨國企業(yè)的人力資源管理模式分析，優(yōu)化管理流程以快速響應(yīng)產(chǎn)品開發(fā)的動態(tài)環(huán)境。

綜上所述，大多數(shù)多項(xiàng)目調(diào)度研究只考慮了周期內(nèi)的并行調(diào)度，對于有新項(xiàng)目加入的多項(xiàng)目調(diào)度，也僅考慮了各項(xiàng)目獨(dú)立的情況。RCPTTSP-PS不僅將項(xiàng)目拆分與作業(yè)調(diào)度同時納入決策模型，還考慮了轉(zhuǎn)換前后的2個裝配項(xiàng)目對于資源、工期和節(jié)拍時間的差異，以及2個項(xiàng)目相互影響的復(fù)雜情況?，F(xiàn)有算法難以求解RCPTTSP-PS，因此對RCPTTSP-PS進(jìn)行建模與算法研究，有著重要的理論意義。

1 問題描述及數(shù)學(xué)模型

1.1 問題描述

RCPTTSP-PS以飛機(jī)總裝脈動生產(chǎn)線的節(jié)拍轉(zhuǎn)換過程為實(shí)際應(yīng)用背景。在脈動生產(chǎn)線上，根據(jù)實(shí)際生產(chǎn)線長度L、飛機(jī)長度LA、安全距離SD，裝配線被分為N個裝配單元，總裝項(xiàng)目也被拆分為N個作業(yè)子集并分配給各個裝配單元。由于新項(xiàng)目的進(jìn)入和原項(xiàng)目的完工，整個轉(zhuǎn)換過程在時間上被分為多個階段。如圖1所示，飛機(jī)沿裝配線方向逐步完成裝配，轉(zhuǎn)換期前后，裝配線上都僅有一種類型飛機(jī)，裝配線穩(wěn)定無變動，而轉(zhuǎn)換期內(nèi)，裝配線由2種飛機(jī)（G0，G1）的作業(yè)子集構(gòu)成，每過一個周期時間，飛機(jī)都會沿裝配線方向移動一個裝配單元，各裝配單元對應(yīng)的作業(yè)子集都會改變。在此過程中每個周期內(nèi)調(diào)度計劃均不同，周期內(nèi)的資源需求和周期時間也均會發(fā)生變化。以轉(zhuǎn)換期時長最小化為優(yōu)化目標(biāo)，建立數(shù)學(xué)模型并求解。

圖1 飛機(jī)移動裝配線轉(zhuǎn)換過程Fig.1 Aircraft moving assembly line transition process

為了描述拆分之后的時序約束關(guān)系，給出如下定義：

定義1真實(shí)時序約束。對于在初始項(xiàng)目網(wǎng)絡(luò)中存在時序約束的2個作業(yè)，若項(xiàng)目拆分后2個作業(yè)仍處于同一個作業(yè)子集內(nèi)，則2個作業(yè)間的時序約束仍然存在，稱該約束為真實(shí)時序約束。

定義2虛擬時序約束。對于在初始項(xiàng)目網(wǎng)絡(luò)中存在時序約束的2個作業(yè)，若項(xiàng)目拆分后2個作業(yè)不處于同一個作業(yè)子集內(nèi)，則2個作業(yè)間不存在時序約束，僅在拆分時需要考慮，稱該約束為虛擬時序約束。

定義3同源作業(yè)子集。如果一系列作業(yè)子集拆分自同一架飛機(jī)的總裝項(xiàng)目，就稱這一系列作業(yè)子集為同源作業(yè)子集，也被稱為同源子項(xiàng)目。

圖2為轉(zhuǎn)換過程中項(xiàng)目的拆分方案以及時序約束關(guān)系。其中，數(shù)字代表裝配作業(yè)，實(shí)線有向弧代表真實(shí)時序約束，虛線有向弧代表虛擬時序約束。在考慮了拆分的飛機(jī)裝配過程中，不同周期內(nèi)的同源作業(yè)子集間會有虛擬時序約束，同時同源作業(yè)子集間可以進(jìn)行作業(yè)的移動以優(yōu)化拆分方案。在調(diào)度時，只有真實(shí)時序約束會被考慮；在作業(yè)移動時，真實(shí)時序約束和虛擬時序約束都需要納入考慮。

圖2 轉(zhuǎn)換過程拆分方式Fig.2 Splitting method in transition process

此外，為了著重研究項(xiàng)目轉(zhuǎn)換，給出如下假設(shè)：作業(yè)執(zhí)行不可中斷，當(dāng)前周期內(nèi)所有作業(yè)完工后才能進(jìn)入下一周期，作業(yè)只有一種執(zhí)行模式。

1.2 數(shù)學(xué)模型

根據(jù)以上問題描述，給出具體參數(shù)定義。模型中部分參數(shù)如表1所示。

表1 部分參數(shù)符號及說明Tab.1 Some parameter symbols and their descriptions

（1）決策變量

xtjmn為0、1變量，若裝配周期m時裝配單元n上作業(yè)j的開始時間為t，則xtjmn=1，否則xtjmn=0。

yjmn為0、1變量，若作業(yè)j屬于作業(yè)子集Smn，則yjmn=1，否則yjmn=0。

zpjmn為0、1變量，表示作業(yè)的真實(shí)時序約束，若作業(yè)p是作業(yè)j的緊前作業(yè)，并且拆分后在同一個作業(yè)子集Smn中，則zpjmn=1，否則zpjmn=0。

（2）目標(biāo)函數(shù)

式（1）是目標(biāo)函數(shù)，即要求轉(zhuǎn)換過程的總時間最小。式（2）和式（3）表達(dá)了4個參數(shù)g、v、m、n之間的關(guān)系，如圖3所示。圖3中，一個圓角矩形表示一個作業(yè)子集，該作業(yè)子集所屬的飛機(jī)類型g與項(xiàng)目序號v用于確定作業(yè)子集在生產(chǎn)計劃中的位置，具有相同g、v的作業(yè)子集屬于同一飛機(jī)，互為同源作業(yè)子集，圖3中雙向箭頭表示同源關(guān)系。作業(yè)子集對應(yīng)裝配周期m與裝配單元n，用以確定作業(yè)子集的位置，m相同的作業(yè)在同一周期內(nèi)裝配，共享線邊資源。

圖3 作業(yè)子集序號關(guān)系Fig.3 Relationship between sub-projects’sequence numbers

式（4）和式（5）保證每一組同源作業(yè)子集完成了所有需要完成的作業(yè)；式（6）表示所有作業(yè)的緊前作業(yè)不能分配到該作業(yè)所在作業(yè)子集的后序同源作業(yè)子集中；式（7）表示真實(shí)時序約束zpjmn與項(xiàng)目拆分決策變量yjmn的關(guān)系，當(dāng)作業(yè)與其緊前作業(yè)被同時分配到同一個作業(yè)子集時，真實(shí)時序約束生效；式（8）表示作業(yè)開始時間與決策變量xtjmn的關(guān)系；式（9）限制作業(yè)子集內(nèi)的優(yōu)先次序關(guān)系，作業(yè)必須在其緊前作業(yè)完工后才能開始；式（10）表示每個作業(yè)只開始一次，并且開始后不能中斷；式（11）表示每個作業(yè)都要在節(jié)拍時間內(nèi)完成；式（12）表示資源約束，即每個時刻所使用的資源不能超過資源上限。

2 算法框架

針對所研究的問題，采用雙層迭代算法。上層使用雙重禁忌搜索（DTS）算法對作業(yè)拆分方案進(jìn)行搜索，在作業(yè)子集之間進(jìn)行作業(yè)的移動以搜索最優(yōu)的拆分決策；下層使用基于最小最晚結(jié)束時間（MIN LFT）的優(yōu)先級規(guī)則并結(jié)合串行調(diào)度生成機(jī)制進(jìn)行調(diào)度，將每個作業(yè)子集的完工時間及資源使用比反饋給上層的雙重禁忌搜索算法，通過不斷的循環(huán)迭代使目標(biāo)函數(shù)最小化。

2.1 雙層迭代算法整體步驟

步驟1根據(jù)非轉(zhuǎn)換期的項(xiàng)目拆分方案，依照進(jìn)入裝配線的順序進(jìn)行項(xiàng)目組合，構(gòu)造原始拆分方案，并利用最小最晚結(jié)束時間優(yōu)先級規(guī)則進(jìn)行串行調(diào)度，求解初始轉(zhuǎn)換期總時長C0，令Cbest=C0。

步驟2設(shè)置總迭代次數(shù)為E，初始迭代次數(shù)e=1。

步驟3計算各作業(yè)子集的完工時長Cmn，利用概率密度函數(shù)ψ(m，n，i)計算作業(yè)移動的起終點(diǎn)項(xiàng)目的選取概率，其中i表示同源作業(yè)子集之間的距離。

步驟4判斷是否有滿足特赦條件的起終點(diǎn)的選取概率，如果有，轉(zhuǎn)步驟6。

步驟5采用偏移隨機(jī)抽樣（RBRS）算法和相對禁忌表確定作業(yè)移動的起終點(diǎn)項(xiàng)目序號。

步驟6利用作業(yè)選取規(guī)則選取移動作業(yè)。

步驟7查詢移動后的項(xiàng)目關(guān)鍵鏈?zhǔn)欠裨诮^對禁忌表中，若在則重新選取移動作業(yè)。如果所有作業(yè)移動后的項(xiàng)目關(guān)鍵鏈均在絕對禁忌表中，就轉(zhuǎn)步驟5重新選擇起終點(diǎn)對。

步驟8采用最小最晚結(jié)束時間優(yōu)先級規(guī)則對各周期內(nèi)的拆分方案進(jìn)行串行調(diào)度，計算每個周期的完工時間Tm、各周期內(nèi)資源利用率fkm以及當(dāng)前迭代的轉(zhuǎn)換期總時長Ce，若Ce＜Cbest，則Cbest=Ce。

步驟9將起終點(diǎn)對加入相對禁忌表。

步驟10對移動后的拆分方案計算關(guān)鍵路徑長度，判斷是否要加入絕對禁忌表。

步驟11e=e+1，若e＜E，則轉(zhuǎn)步驟3。

步驟12輸出Cbest。

2.2 基于雙重禁忌搜索算法的作業(yè)移動

提出了一種雙重禁忌搜索算法，加入了相對禁忌表和絕對禁忌表來處理不同的禁忌情況。相對禁忌表即為常規(guī)禁忌搜索算法中的禁忌表，可持續(xù)更替。絕對禁忌表則存儲無法達(dá)到歷史最優(yōu)的解的特征，在搜索過程中不斷增加。相比傳統(tǒng)元啟發(fā)算法，該算法通過絕對禁忌表增加約束，縮減解集的搜索空間，利用相對禁忌表和啟發(fā)式規(guī)則來控制解的搜索方向，兩者相結(jié)合進(jìn)行最優(yōu)解的搜索。

2.2.1 作業(yè)起終點(diǎn)項(xiàng)目的選擇

首先計算出當(dāng)前每個作業(yè)子集Smn的完工時間Cmn，通過Cmn計算起點(diǎn)與終點(diǎn)的權(quán)重比ρmn。ρmn的計算式如下所示：

由于不同的作業(yè)子集間可能擁有同一個項(xiàng)目的繼承關(guān)系，因此僅有同源作業(yè)子集間可以進(jìn)行作業(yè)移動。同源作業(yè)子集有如下性質(zhì)：

性質(zhì)1對于一系列同源作業(yè)子集Smn，根據(jù)式（1），有m、n之差為常數(shù)。定義Smn的同源作業(yè)子集為S(m+i)(n+i)，i∈Z，i≠0。

在性質(zhì)1的基礎(chǔ)上引入i作為作業(yè)移動起終點(diǎn)作業(yè)子集在其整裝項(xiàng)目中的序號差，以確保選取的起終點(diǎn)作業(yè)子集為同源作業(yè)子集。設(shè)概率密度函數(shù)

式中：ε＞0為參數(shù)，用于保證ρmn=0的項(xiàng)目也有一定概率被選擇；α為用于控制過程隨機(jī)性的參數(shù)。ψ(m，n，i)的值決定作業(yè)子集Smn被選中起點(diǎn)并移動i個單位的概率。因同源作業(yè)子集間存在虛擬時序約束，因此每次移動時僅移動一個單位，i=±1，表示作業(yè)移動的方向與距離。

2.2.2 相對禁忌框架設(shè)計

（1）相對禁忌表

使用相對禁忌表的目的是跳出局部最優(yōu)，避免搜索選入循環(huán)。本研究中相對禁忌表記錄的是記錄之前若干次移動所選取的起終點(diǎn)作業(yè)子集序號Smn、S(m+i)(n+i)。

（2）相對禁忌長度

禁忌對象為起終點(diǎn)作業(yè)子集序號，禁忌對象的總數(shù)相對較少。如圖4所示，N=3時可選取的起終點(diǎn)對僅有4對，N=4時有12對，N=5時有24對。拆分?jǐn)?shù)量對于可移動的起終點(diǎn)影響很大，因此禁忌長度LTabu的選取也很關(guān)鍵。本研究中取LTabu=

圖4 不同拆分?jǐn)?shù)量下轉(zhuǎn)換期Fig.4 Transition process of different splitting numbers

N-2。

（3）特赦規(guī)則

對于完工時間最長的起點(diǎn)Smn，若其可移動的終點(diǎn)S(m+i)(n+i)的完工時間為（m+i)周期內(nèi)的最小值，且m和(m+i)周期內(nèi)的資源利用率分別為全周期內(nèi)最高和最低時，對Smn、S(m+i)(n+i)特赦。選取Smn、S(m+i)(n+i)為調(diào)整的起終點(diǎn)。若存在多個可特赦起終點(diǎn)項(xiàng)目對，則隨機(jī)選取一對起終點(diǎn)。

2.2.3 作業(yè)選取

定義4作業(yè)移動。對一個作業(yè)j∈Smn，將其從Smn移動至S(m+1)(n+1)，稱為作業(yè)右移；將其從Smn移動至S(m-1)(n-1)，稱為作業(yè)左移。

定義5松弛約束。作業(yè)j與作業(yè)q在移動前存在真實(shí)時序約束，在移動后真實(shí)時序約束轉(zhuǎn)化為虛擬時序約束，稱為松弛約束。

定義6綁定約束。作業(yè)j與作業(yè)q在移動前存在虛擬時序約束，在移動后虛擬時序約束轉(zhuǎn)化為真實(shí)時序約束，稱為綁定約束。

作業(yè)移動過程如圖5所示。當(dāng)目標(biāo)作業(yè)移動時，目標(biāo)作業(yè)與起點(diǎn)作業(yè)子集的其他作業(yè)松弛約束，真實(shí)時序約束變少，因此作業(yè)子集的關(guān)鍵鏈長度變短，對應(yīng)作業(yè)子集工期變短；目標(biāo)作業(yè)與終點(diǎn)作業(yè)子集的其他作業(yè)綁定約束，真實(shí)時序約束增加，因此作業(yè)子集的關(guān)鍵鏈長度變長，對應(yīng)作業(yè)子集工期變長。

圖5 作業(yè)左（右）移分析Fig.5 Analysis of job moving left(right)

作業(yè)移動的具體作業(yè)選取與時序約束的改變?nèi)缦拢?/p>

（1）當(dāng)作業(yè)左移時，只有無真實(shí)緊前時序約束的作業(yè)j可以被選中，參數(shù)γ1j表示目標(biāo)作業(yè)在移動前的真實(shí)緊后作業(yè)約束數(shù)量，參數(shù)γ2j表示目標(biāo)作業(yè)在移動后的真實(shí)緊前作業(yè)約束數(shù)量，Δγj=γ1j-γ2j。

（2）當(dāng)作業(yè)右移時，只有無真實(shí)緊后時序約束的作業(yè)j可以被選中，參數(shù)γ1j表示目標(biāo)作業(yè)在移動前的真實(shí)緊前作業(yè)約束數(shù)量，參數(shù)γ2j表示目標(biāo)作業(yè)在移動后的真實(shí)緊后作業(yè)約束數(shù)量，Δγj=γ1j-γ2j。

此外，作業(yè)是在項(xiàng)目轉(zhuǎn)換期內(nèi)不同周期間進(jìn)行作業(yè)移動，起點(diǎn)周期內(nèi)調(diào)度作業(yè)減少，資源約束松弛，對應(yīng)周期的整體工期變小；終點(diǎn)周期內(nèi)的調(diào)度作業(yè)增多，資源約束收緊，對應(yīng)周期的整體工期變大。因此，在選擇了作業(yè)移動的起終點(diǎn)后，將結(jié)合真實(shí)時序約束與資源約束2個方面來選取作業(yè)進(jìn)行移動。作業(yè)選取的權(quán)重參數(shù)δj=Δγj/J+uj，其中Δγj/J表示解綁的時序約束數(shù)量與總作業(yè)數(shù)的比值，uj=rj1(1-f1m)+…+rjK(1-fKm)為資源評估函數(shù)，其具體含義為作業(yè)j在周期m內(nèi)使用的資源與周期m所使用的全部資源的比值周期m資源k的使用率。δj將作業(yè)j移動的真實(shí)時序約束變化與資源變化同時納入考慮，默認(rèn)選取δj最大的作業(yè)進(jìn)行移動。當(dāng)存在δj相同的作業(yè)時，添加補(bǔ)充規(guī)則：作業(yè)左移時，選取序號最小的作業(yè)；作業(yè)右移時，選取序號最大的作業(yè)。

2.2.4 絕對禁忌規(guī)則

（1）絕對禁忌表

絕對禁忌表的目的是篩選所有不可能成為最優(yōu)解的可行解的特征，以此來減少解的搜索空間。本研究中，絕對禁忌表的禁忌對象為拆分方案的關(guān)鍵鏈。每次移動后，需計算移動后拆分方案的關(guān)鍵鏈，若關(guān)鍵鏈長度大于歷史最優(yōu)解Cbest時，將該關(guān)鍵鏈包含進(jìn)絕對禁忌表中。絕對禁忌表有如下性質(zhì)：

性質(zhì)2包含絕對禁忌表中關(guān)鍵鏈的拆分方案均不是最優(yōu)解。

證明絕對禁忌表中的關(guān)鍵鏈所對應(yīng)的解不是唯一的，所有包括這條關(guān)鍵鏈的項(xiàng)目拆分方案，其完工時間均大于關(guān)鍵鏈長度。又因?yàn)殛P(guān)鍵鏈的時長大于歷史最優(yōu)解Cbest，因此拆分方案完工時間C＞Cbest無法成為歷史最優(yōu)解。

因?yàn)榻^對禁忌表的性質(zhì)2，絕對禁忌表不受限于禁忌長度，所以絕對禁忌表不會解除禁忌。

（2）絕對禁忌規(guī)則

當(dāng)作業(yè)移動后，若移動后產(chǎn)生的新拆分方案中包含絕對禁忌表中的關(guān)鍵鏈，則新方案不被接受，返回作業(yè)選取步驟順次按權(quán)重δj選取下一個可移動作業(yè)。如果所有移動方案均在絕對禁忌表中，就跳過本次移動，選取新的項(xiàng)目調(diào)整起終點(diǎn)。

3 數(shù)值實(shí)驗(yàn)

3.1 實(shí)例驗(yàn)證

為了驗(yàn)證算法和模型的可行性，選用PSPLIB提供的算例作為某工廠所裝配的飛機(jī)項(xiàng)目G0、G1，使用Python3.7.0編程實(shí)現(xiàn)算法。數(shù)據(jù)測試平臺選用i5-4210U處理器，2.39 GHz主頻，8 G內(nèi)存。項(xiàng)目G0、G1各包括30個作業(yè)及2個虛擬作業(yè)，4種完成項(xiàng)目所需的可更新資源，具體數(shù)據(jù)如表2所示。某工廠需要將飛機(jī)移動生產(chǎn)線從G0轉(zhuǎn)換至G1，計算轉(zhuǎn)換的總工期并使得總時間最小化。采用所提出的模型及算法，對于G0、G1確定的拆分?jǐn)?shù)量N=3，算法參數(shù)設(shè)定α=1，ε=1，LTabu=1，E=100。

表2 項(xiàng)目數(shù)據(jù)Tab.2 Project data

為了進(jìn)一步驗(yàn)證本研究模型和算法的可行性，以同樣的轉(zhuǎn)換過程，與不進(jìn)行重拆分的調(diào)度方案初始解進(jìn)行對比。給定各類資源上限均為15，初始解的具體拆分方案如表3所示，本研究算法優(yōu)化的重拆分方案如表4所示，2種拆分方案的對比結(jié)果如表5所示?？梢钥闯?，采用本研究方案的項(xiàng)目時長顯著小于不經(jīng)過調(diào)整的方案。在實(shí)際生產(chǎn)中，使用本研究方案在轉(zhuǎn)換過程中進(jìn)行變節(jié)拍生產(chǎn)，可以提高生產(chǎn)線的生產(chǎn)效率。

表3 初始拆分方案Tab.3 Initial splitting plan

表4 轉(zhuǎn)換期拆分方案Tab.4 Transition splitting plan

表5 轉(zhuǎn)換期節(jié)拍時間對比Tab.5 Cycle time comparison during transition period

3.2 算法分析

選取參數(shù)ε=1以確保ψ(m，n，i)不為零，初始拆分方案依文獻(xiàn)［10］進(jìn)行計算，因?yàn)槌跏疾鸱址桨敢呀?jīng)是項(xiàng)目的最優(yōu)解，所以取迭代次數(shù)E=100，N=5，LTabu=3。對控制移動方向的隨機(jī)參數(shù)α進(jìn)行敏感性分析，選取標(biāo)準(zhǔn)算例庫中的3種作業(yè)規(guī)模J30、J60、J90的各40個項(xiàng)目進(jìn)實(shí)驗(yàn)。3種算例下，比較差值百分比的均值圖6是參數(shù)α的敏感性分析?？梢钥闯觯?dāng)α=1時值最小，所以實(shí)驗(yàn)時取α=1。

圖6 α對調(diào)度結(jié)果的影響Fig.6 Effect ofαon scheduling results

3.3 算法比較

由圖4分析可知，計算規(guī)模隨著拆分?jǐn)?shù)量的增加呈冪函數(shù)增長，常規(guī)的精確算法難以求解，故選取已有的項(xiàng)目拆分問題啟發(fā)式算法［10］結(jié)合項(xiàng)目節(jié)拍轉(zhuǎn)換過程，將遺傳算法與本研究算法進(jìn)行對比。引用標(biāo)準(zhǔn)算例庫PSPLIB中的3種作業(yè)規(guī)模J30、J60、J90，在N=3，4，5的情況下，分別隨機(jī)選取5對項(xiàng)目進(jìn)行項(xiàng)目轉(zhuǎn)換，參數(shù)設(shè)定α=1，E=100，LTabu=N-2。

表6～8列出了3種規(guī)模下3種拆分?jǐn)?shù)目結(jié)果的對比。GAPGA與GAPBASE的計算式分別如下所示：

式中：C為轉(zhuǎn)換期總時長；GA表示遺傳算法，BASE表示初始拆分方案，DTS表示本研究方案。表6～8中，t為求解時間。對于GA，取迭代次數(shù)100，初始種群數(shù)10，交叉概率0.8，變異概率0.2，對作業(yè)所屬項(xiàng)目進(jìn)行編碼。

表6 J30規(guī)模數(shù)值結(jié)果Tab.6 Numerical results of J30

表7 J60規(guī)模數(shù)值結(jié)果Tab.7 Numerical results of J60

通過表6～8可以得出，在求解小中大3種規(guī)模的算例時，本研究算法平均質(zhì)量均優(yōu)于對比算法GA，但對于部分項(xiàng)目，如J30、N=4、第4組項(xiàng)目時，本研究算法的求解效果不如對比算法。與對比算法差別較小的原因可能是兩者均在初始拆分方案的基礎(chǔ)上進(jìn)行進(jìn)一步搜索，因此搜索的方向相似。從整體上看，本研究算法與對比算法之間的GAP穩(wěn)定在3%以內(nèi)，并且平均求解質(zhì)量優(yōu)于GA約1%，這是由于雙重禁忌搜索限制了搜索空間，提高了搜索質(zhì)量。從與初始拆分方案的GAP值上來看，本研究算法對于初始拆分方案的優(yōu)化程度平均在10%左右，但是不同的項(xiàng)目間波動較大，最高值可達(dá)23.4%，最低值僅有1.1%，這是由于本研究算法是在已有的項(xiàng)目拆分方案上進(jìn)行進(jìn)一步優(yōu)化，可優(yōu)化區(qū)間主要來自于轉(zhuǎn)換的兩項(xiàng)目間的差異。對于相似的2個項(xiàng)目，初始拆分方案是類似的，在轉(zhuǎn)換期間對資源的需求和節(jié)拍時間的要求都相似，因此優(yōu)化的空間有限。對于差異性較大的項(xiàng)目，本研究算法的優(yōu)化空間更大。在不同規(guī)模的算例下，拆分?jǐn)?shù)并未對優(yōu)化結(jié)果產(chǎn)生顯著的影響，但是從約束角度分析，隨著拆分?jǐn)?shù)增大，被松弛的真實(shí)時序約束增多，作業(yè)調(diào)度的自由度就更高。當(dāng)拆分?jǐn)?shù)與作業(yè)數(shù)相等時，該問題將退化為一個沒有時序約束的項(xiàng)目調(diào)度問題。因此，隨著拆分?jǐn)?shù)的增大，每個周期的節(jié)拍時間有減小的趨勢。在算法的運(yùn)算速度方面，隨著項(xiàng)目規(guī)模和拆分?jǐn)?shù)的增加，本研究算法和GA的求解時間都在增大。在項(xiàng)目規(guī)模較小時，GA的求解時間略小于本研究算法，但是當(dāng)項(xiàng)目的規(guī)模數(shù)達(dá)到J60和J90時，本研究算法的求解時間顯著小于對比算法，這說明本研究算法對大規(guī)模項(xiàng)目的適應(yīng)性較好，而對于小規(guī)模算法求解速度較差。

表8 J90規(guī)模數(shù)值結(jié)果Tab.8 Numerical results of J90

4 結(jié)語

以RCPTTSP-PS為研究對象，建立了離散時間下的數(shù)學(xué)模型，提出了雙重禁忌搜索算法，并結(jié)合雙層迭代算法對問題進(jìn)行求解。在項(xiàng)目轉(zhuǎn)換階段，考慮了項(xiàng)目移動對起終點(diǎn)項(xiàng)目的共同影響，提出了起終點(diǎn)選取函數(shù)以及作業(yè)選取權(quán)重函數(shù)。同時，為了限制搜索空間，提出了相對禁忌規(guī)則和絕對禁忌規(guī)則，有助于避免算法陷入局部最優(yōu)，并利用絕對禁忌規(guī)則限制搜索空間，提高了搜索速度。在數(shù)值實(shí)驗(yàn)中，本研究算法的求解質(zhì)量略優(yōu)于對比算法，與對比算法的GAP值在1%左右。在求解速度方面，本研究算法在大規(guī)模項(xiàng)目的求解速度明顯優(yōu)于對比算法。因此，本研究算法對于飛機(jī)脈動生產(chǎn)線這類大規(guī)模項(xiàng)目調(diào)度問題具有良好的效果。同時，相較于初始拆分方案，本研究算法對于轉(zhuǎn)換期時長的優(yōu)化程度在1.1%～23.4%之間，與初始拆分方案的GAP值方差較大，這是由不同項(xiàng)目網(wǎng)絡(luò)之間的差異引起的。在未來的研究中，可以對RCPTTSP-PS中不同項(xiàng)目的關(guān)聯(lián)性進(jìn)行進(jìn)一步研究，有助于提高生產(chǎn)線節(jié)拍轉(zhuǎn)換過程的時間優(yōu)化，對于生產(chǎn)線上的實(shí)際應(yīng)用也有一定幫助。