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

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

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

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

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

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

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

1.1 問(wèn)題描述

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

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

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

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

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

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

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

圖2 轉(zhuǎn)換過(guò)程拆分方式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ù)以上問(wèn)題描述，給出具體參數(shù)定義。模型中部分參數(shù)如表1所示。

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

（1）決策變量

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

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

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

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

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

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

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

2 算法框架

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

2.1 雙層迭代算法整體步驟

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

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

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

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

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

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

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

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

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

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

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

步驟12輸出Cbest。

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

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

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

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

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

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

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

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

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

（1）相對(duì)禁忌表

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

（2）相對(duì)禁忌長(zhǎng)度

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

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

N-2。

（3）特赦規(guī)則

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

2.2.3 作業(yè)選取

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

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

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

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

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

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

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

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

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

2.2.4 絕對(duì)禁忌規(guī)則

（1）絕對(duì)禁忌表

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

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

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

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

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

當(dāng)作業(yè)移動(dòng)后，若移動(dòng)后產(chǎn)生的新拆分方案中包含絕對(duì)禁忌表中的關(guān)鍵鏈，則新方案不被接受，返回作業(yè)選取步驟順次按權(quán)重δj選取下一個(gè)可移動(dòng)作業(yè)。如果所有移動(dòng)方案均在絕對(duì)禁忌表中，就跳過(guò)本次移動(dòng)，選取新的項(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ù)測(cè)試平臺(tái)選用i5-4210U處理器，2.39 GHz主頻，8 G內(nèi)存。項(xiàng)目G0、G1各包括30個(gè)作業(yè)及2個(gè)虛擬作業(yè)，4種完成項(xiàng)目所需的可更新資源，具體數(shù)據(jù)如表2所示。某工廠需要將飛機(jī)移動(dòng)生產(chǎn)線從G0轉(zhuǎn)換至G1，計(jì)算轉(zhuǎn)換的總工期并使得總時(shí)間最小化。采用所提出的模型及算法，對(duì)于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)換過(guò)程，與不進(jìn)行重拆分的調(diào)度方案初始解進(jìn)行對(duì)比。給定各類資源上限均為15，初始解的具體拆分方案如表3所示，本研究算法優(yōu)化的重拆分方案如表4所示，2種拆分方案的對(duì)比結(jié)果如表5所示?？梢钥闯?，采用本研究方案的項(xiàng)目時(shí)長(zhǎng)顯著小于不經(jīng)過(guò)調(diào)整的方案。在實(shí)際生產(chǎn)中，使用本研究方案在轉(zhuǎn)換過(guò)程中進(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é)拍時(shí)間對(duì)比Tab.5 Cycle time comparison during transition period

3.2 算法分析

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

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

3.3 算法比較

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

式中：C為轉(zhuǎn)換期總時(shí)長(zhǎng)；GA表示遺傳算法，BASE表示初始拆分方案，DTS表示本研究方案。表6～8中，t為求解時(shí)間。對(duì)于GA，取迭代次數(shù)100，初始種群數(shù)10，交叉概率0.8，變異概率0.2，對(duì)作業(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

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

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

4 結(jié)語(yǔ)

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