電梯層站指示器裝配車間調度優化算法*

鐘臻怡,楊家榮

上海電氣集團股份有限公司中央研究院 上海 200070

1 研究背景

電梯行業具有定制化生產、產品種類多、產品精度高、生產壓力大等特點。大多數電梯生產過程中的調度問題已被證明是NP難問題,進而給電梯生產系統建模和優化調度帶來較大困難。電梯生產過程中的調度問題是學術界和工程界的研究熱點。

目前,電梯行業在生產調度管理和智能排程領域的研究仍處于發展階段。趙瑛[1]對電梯產品鈑金車間的調度問題進行研究,提出了基于工藝流程矩陣的靜態調度優化方案,并引入周期性設備狀態査詢方案,建立動態調度優化模型。張靜[2]通過生產排產知識、約束理論及現場管理理論,在排產前確認瓶頸工序,設定系統緩沖,進而優先確定瓶頸工序排程計劃和非瓶頸工序排產計劃。孫加洲等[3]運用啟發式算法,動態進行主生產計劃排程,解決了電梯生產過程中多個工作中心生產的同期成套問題和生產負荷平準問題。李彥君[4]提出一種基于生產計劃驅動,合理考慮生產資源負載狀況的生產管理系統,按生產計劃和設定的原則進行調度排產計算,均衡分配生產任務。豆之敬[5]研究了電梯轎廂生產車間調度策略,采用階段進化的自適應遺傳模擬退火算法,可以避免傳統遺傳算法過早收斂及后期搜索效率低等問題。曹成輝[6]以山東某電梯公司機械加工車間為研究對象,對柔性作業車間調度問題進行深入分析,提出自適應文化遺傳算法。試驗結果表明,這一算法可以有效解決調度問題。孫斌[7]對單目標柔性作業車間調度問題進行研究,采用基于工序和機器的雙層編碼方式,以及分步更新的策略,進行螢火蟲位置的更新,并采用病毒感染操作加強群體的協作能力和動態搜索能力。通過與遺傳算法、粒子群優化算法進行比較,驗證了這一方法的有效性。陳少[8]分析了電梯零部件排產過程的特點,提出通過改進鳥群算法求解柔性化電梯零部件排產問題,并利用調度規則求解動態擾動后的重排產問題,同時采用反向傳播神經網絡作為推理手段,選擇出適合生產情況的最佳調度規則。

通過對上述電梯行業車間調度文獻進行分析可知,在問題域方面,文獻主要以柔性作業車間的電梯調度問題作為研究對象,如電梯轎廂生產車間、電梯機械加工車間等,且暫無研究電梯層站指示器裝配車間的調度問題。在排程方法方面,上述文獻使用了基于經驗規則的啟發式算法或以遺傳算法為代表的元啟發式算法。筆者針對電梯層站指示器的特點,將啟發式規則和元啟發式算法相結合。利用啟發式規則對具有相似產品結構的訂單進行合并,以此降低物料切換頻率,縮短配料時間。使用分布估計算法進行優化調度,解決電梯層站指示器多訂單、小批量、物料切換頻繁、備料時間長等問題,提高車間的裝配效率,有效縮短訂單的總完成時間。

2 調度問題描述

電梯層站指示器車間裝配線上共有J種不同類型的訂單待裝配,有M條處理訂單能力不同的裝配線,每種訂單的產品大小不同,裝配時間也不同。訂單在物料到達之后和裝配之前首先需要進行配料,并且不同訂單種類物料到達時間和配料時間也均不相同。

在本調度問題中,假設J種訂單中的每一種均可由M條裝配線中的一條完成裝配任務,每條裝配線在每一時刻只能裝配一種訂單,一種訂單一旦在裝配線上進行裝配,就不能中斷,直至裝配完成。

針對這一電梯層站指示器裝配車間調度問題,通過合并訂單縮短配料時間,并以實現最短加工周期為調度目標,進行裝配車間的調度優化。

3 數學模型

在研究中,定義相關參數符號。i、j、k為訂單序號,m為裝配線序號,aj為訂單j的物料到達時間,pj為訂單j的配料時間,tjm為訂單j在裝配線m上的裝配時間。

定義決策變量xij。如果訂單j在同一條裝配線上接著訂單i裝配,那么xij為1,否則xij為0。虛擬變量job0表示物料到達時間、配料時間和裝配處理時間均為零的工件,這樣就能夠表示一條裝配線開始裝配和結束裝配的狀態。

根據上述問題描述、模型假設、參數、決策變量等,對所研究的梯層站指示器裝配車間調度問題進行建模。

目標函數為生產過程時間最短,即minCmax。

約束條件式(1)、式(2)表明裝配線開始和結束的狀態出現次數總和均不大于M,即訂單被分配到M條裝配線中的一條:

(1)

(2)

約束條件式(3)、式(4)表明在任意訂單的緊前、緊后,訂單有且僅有一個,用于分配裝配線及訂單在同一條裝配線上的順序:

(3)

(4)

約束條件式(5)表明訂單i完成時間Ci的范圍:

?i∈J,?j∈J:j≠0,i≠j

(5)

式(5)中Q滿足:

(6)

4 算法構建

4.1 啟發式規則

由于電梯層站指示器物料種類繁多,每種訂單所需的物料型號及數量均不相同,因此配料時需要進行頻繁的物料切換,從而導致大量分揀操作。筆者根據計劃訂單物料清單一級分解表,利用啟發式規則對具有相似產品結構的訂單進行合并,降低物料配送頻率,從而大大縮短配料時間。

在電梯層站指示器訂單編碼中,具有產品參數、印板圖號、印板參數、按鈕參數等信息。為了降低物料配送頻率,設計啟發式規則對印板圖號和印板參數一致的訂單進行合并,從而將印板相同的產品合并成一種訂單集中裝配,縮短印板的切換和配料時間。

4.2 分布估計算法

分布估計算法是一種新穎的進化算法,在優化過程中應用了概率分布模型[9]。

在訂單完成合并后,筆者運用分布估計算法進行調度優化。

(1) 編碼。訂單序號的排列作為本調度問題的一個解,π={π1,π2,…,πj}表示訂單裝配順序,πj為第j種待裝配的訂單。

(2) 解碼。按照裝配線分配規則依次完成所有訂單,裝配線分配規則為選擇訂單最早結束裝配的裝配線。假設rm為裝配線m最早未占用的時間,則最早結束裝配的時間為min{max{rm,aj}+pj+tjm}。

(3) 初始化種群。為了保證初始種群的分散性,采用隨機初始化方法產生均勻分布的N個個體作為初始種群。

(4) 概率模型。分布估計算法通過對概率模型采樣產生下一代。概率模型用概率矩陣P表示。元素phj(G)為第G次迭代中訂單j在第h個位置上或之前出現的概率。算法選擇種群中目標值最小的S個個體作為優勢群體,S為η與N的乘積,η為優勢種群占整個種群的比例。概率矩陣P根據式(7)進行初始化:

(7)

(5) 概率模型的更新。采樣產生N個新個體之后,選擇目標值最小的S個個體作為優勢群體,并根據式(8)更新概率矩陣P:

phj(G+1)=(1-α)phj(G)

(8)

式中:α為概率矩陣P的學習速率,α∈(0,1)。

(6) 基于Insert函數和首次改進跳出原則進行局部搜索。為了平衡算法的全局和局部搜索能力,基于Insert函數和首次改進跳出原則局部搜索。

算法流程如下:

步驟1,編碼并初始化種群,初始化概率矩陣P;

步驟2,解碼并產生新種群,選擇優勢群體;

步驟3,更新概率矩陣P;

步驟4,進行局部搜索;

步驟5,如果終止條件沒有滿足,那么重做步驟2,否則停止。

5 試驗分析

5.1 參數設計

試驗通過加工周期值和中央處理器占用時間來衡量結果,設最大迭代次數為300。

筆者對計劃下達的訂單進行合并,大大減少了訂單種類,由此縮短了配料時間。試驗通過遺傳算法[10]、粒子群優化群法和筆者提出的分布估計算法來求解各種不同規模的電梯層站指示器裝配車間調度問題的性能。問題實例隨機產生如下:訂單種類集合為{10,20,50},裝配線個數集合為{2,4,6}。每種訂單的數量、裝配時間分別由[1,20],[2,6]離散均勻分布隨機產生。共有九種規模,對每種規模隨機產生和測試十個不同的實例,因此本試驗共產生和使用90個測試實例。

5.2 試驗結果

試驗結果見表1和表2。加工周期試驗結果中,分布估計算法平均值為3 779.32,遺傳算法平均值為3 893.17,粒子群優化算法平均值為3 878.38。中央處理器占用時間試驗結果中,分布估計算法平均值為53.21 s,遺傳算法平均值為16.34 s,粒子群優化算法平均值為16.58 s。

表1 加工周期試驗結果

表2 中央處理器占用時間試驗結果

表2中,遺傳算法和粒子群優化算法在中央處理器運行時間方面更有優勢,這是由于遺傳算法和粒子群優化算法產生下一代的復雜度為線性,而分布估計算法的復雜度為二次方。表1中,分布估計算法在解的質量方面優于遺傳算法和粒子群優化算法。可見,分布估計算法針對所有規模問題在三個算法中都表現得最好,并且中央處理器占用時間也是可以接受的。

6 結束語

筆者以電梯層站指示器裝配車間調度問題為研究對象,針對裝配車間訂單多類型、小批量、物料切換頻繁、備料時間長等特點,提出了電梯層站指示器裝配車間調度的問題域,建立了以加工周期最短為目標的數學規劃模型,利用啟發式規則對具有相似產品結構的訂單進行合并,以此降低物料切換頻率,縮短配料時間。在研究中,提出了基于分布估計算法的調度優化方法,設計了針對裝配車間調度優化的解碼規則,并引入了基于Insert函數和首次改進跳出原則的局部搜索功能。試驗結果表明,這一分布估計算法在各種規模下均能比遺傳算法和粒子群優化算法更有效地解決電梯層站指示器裝配車間調度問題。