資源受限的飛機總裝脈動生產(chǎn)線節(jié)拍轉(zhuǎn)換調(diào)度建模

陸志強，王浩宇

（同濟大學機械與能源工程學院，上海201804）

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

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

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

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

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

1.1 問題描述

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

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

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

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

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

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

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

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

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

1.2 數(shù)學模型

根據(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è)的真實時序約束，若作業(yè)p是作業(yè)j的緊前作業(yè)，并且拆分后在同一個作業(yè)子集Smn中，則zpjmn=1，否則zpjmn=0。

（2）目標函數(shù)

式（1）是目標函數(shù)，即要求轉(zhuǎn)換過程的總時間最小。式（2）和式（3）表達了4個參數(shù)g、v、m、n之間的關(guān)系，如圖3所示。圖3中，一個圓角矩形表示一個作業(yè)子集，該作業(yè)子集所屬的飛機類型g與項目序號v用于確定作業(yè)子集在生產(chǎn)計劃中的位置，具有相同g、v的作業(yè)子集屬于同一飛機，互為同源作業(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）表示真實時序約束zpjmn與項目拆分決策變量yjmn的關(guān)系，當作業(yè)與其緊前作業(yè)被同時分配到同一個作業(yè)子集時，真實時序約束生效；式（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è)拆分方案進行搜索，在作業(yè)子集之間進行作業(yè)的移動以搜索最優(yōu)的拆分決策；下層使用基于最小最晚結(jié)束時間（MIN LFT）的優(yōu)先級規(guī)則并結(jié)合串行調(diào)度生成機制進行調(diào)度，將每個作業(yè)子集的完工時間及資源使用比反饋給上層的雙重禁忌搜索算法，通過不斷的循環(huán)迭代使目標函數(shù)最小化。

2.1 雙層迭代算法整體步驟

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

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

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

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

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

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

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

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

步驟9將起終點對加入相對禁忌表。

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

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

步驟12輸出Cbest。

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

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

2.2.1 作業(yè)起終點項目的選擇

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

由于不同的作業(yè)子集間可能擁有同一個項目的繼承關(guān)系，因此僅有同源作業(yè)子集間可以進行作業(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è)移動起終點作業(yè)子集在其整裝項目中的序號差，以確保選取的起終點作業(yè)子集為同源作業(yè)子集。設(shè)概率密度函數(shù)

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

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

（1）相對禁忌表

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

（2）相對禁忌長度

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

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

N-2。

（3）特赦規(guī)則

對于完工時間最長的起點Smn，若其可移動的終點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)整的起終點。若存在多個可特赦起終點項目對，則隨機選取一對起終點。

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在移動前存在真實時序約束，在移動后真實時序約束轉(zhuǎn)化為虛擬時序約束，稱為松弛約束。

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

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

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

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

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

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

此外，作業(yè)是在項目轉(zhuǎn)換期內(nèi)不同周期間進行作業(yè)移動，起點周期內(nèi)調(diào)度作業(yè)減少，資源約束松弛，對應(yīng)周期的整體工期變??；終點周期內(nèi)的調(diào)度作業(yè)增多，資源約束收緊，對應(yīng)周期的整體工期變大。因此，在選擇了作業(yè)移動的起終點后，將結(jié)合真實時序約束與資源約束2個方面來選取作業(yè)進行移動。作業(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移動的真實時序約束變化與資源變化同時納入考慮，默認選取δj最大的作業(yè)進行移動。當存在δj相同的作業(yè)時，添加補充規(guī)則：作業(yè)左移時，選取序號最小的作業(yè)；作業(yè)右移時，選取序號最大的作業(yè)。

2.2.4 絕對禁忌規(guī)則

（1）絕對禁忌表

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

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

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

因為絕對禁忌表的性質(zhì)2，絕對禁忌表不受限于禁忌長度，所以絕對禁忌表不會解除禁忌。

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

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

3 數(shù)值實驗

3.1 實例驗證

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

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

為了進一步驗證本研究模型和算法的可行性，以同樣的轉(zhuǎn)換過程，與不進行重拆分的調(diào)度方案初始解進行對比。給定各類資源上限均為15，初始解的具體拆分方案如表3所示，本研究算法優(yōu)化的重拆分方案如表4所示，2種拆分方案的對比結(jié)果如表5所示?？梢钥闯?，采用本研究方案的項目時長顯著小于不經(jīng)過調(diào)整的方案。在實際生產(chǎn)中，使用本研究方案在轉(zhuǎ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)不為零，初始拆分方案依文獻［10］進行計算，因為初始拆分方案已經(jīng)是項目的最優(yōu)解，所以取迭代次數(shù)E=100，N=5，LTabu=3。對控制移動方向的隨機參數(shù)α進行敏感性分析，選取標準算例庫中的3種作業(yè)規(guī)模J30、J60、J90的各40個項目進實驗。3種算例下，比較差值百分比的均值圖6是參數(shù)α的敏感性分析?？梢钥闯?，當α=1時值最小，所以實驗時取α=1。

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

3.3 算法比較

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

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

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

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

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

4 結(jié)語

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