基于摹加代數優化的裝配線平衡方法

李 平,夏緒輝,唐秋華

(1.武漢科技大學機械自動化學院,湖北武漢,430081;2.黃岡師范學院信息與計算科學學院,湖北黃岡,438000)

要完成作業空間狹小、操作間幾何及功能約束關系復雜的裝配操作,除了智能判斷和柔性操作能力外,還需要自動化裝配的速度和精度與之匹配[1]。利用裝配線平衡技術,可確保生產過程的連續、平行、比例、均衡和準時。裝配線平衡的常規求解方法一般分為3類:①作業測定方法[2],用于制定整個裝配線工時標準,但由于缺乏精確的數學模型及算法作基礎,故不適用于大規模裝配線平衡問題的求解;②基于數學規劃求解[3],建立線性規劃或動態規劃模型,利用模型求解結果對生產線進行優化,但該方法用于解決離散問題時受限于問題的規模;③基于啟發式方法求解[4],這類方法具有某些共同特點,譬如都是隨機產生一組可行解作為初始種群,并以此為基礎采用迭代改進的策略逼近問題的最優解,因而能很好地解決一些NP問題,其主要算法有遺傳算法、模擬退火算法、蟻群算法、神經網絡算法[5-7]等。

本文在秦裕瑗方法[8-9]的基礎上,提出一種新的求解裝配線平衡問題的方法——取整摹加算法,將裝配線平衡問題轉化為取整摹加意義上等價的TSP問題,借用TSP問題求解方法進行求解。

1 裝配線平衡問題及其求解框架

1.1 問題描述

將滿足裝配優先約束關系的一組操作均衡分配于裝配線各工位即為裝配線平衡問題。裝配線平衡問題示意圖如圖1所示。

圖1 裝配線平衡問題示意圖Fig.1 Schematic diagram of assembly line balancing

在反映裝配約束的優先關系圖中,每個操作節點i∈E對應一個ti(i=1,2,3,…,n),ti表示完成該操作所需的時間。裝配線平衡問題就是求節點集E的一個劃分使得操作集合在這種劃分下能達到一個或多個優化目標,同時又不違反以下約束條件:

(4)滿足操作間的優先關系約束,即當Pij=1,操作i必須分配至j操作之前。

將裝配線平衡問題分為3類:①給定生產節拍CT,在滿足操作優先關系的前提下最小化工位數量;②給定工位數量,在滿足操作優先關系的前提下最小化生產節拍;③給定工位數量,使得負荷分布均勻化。本文求解的是第1類裝配線平衡問題。

1.2 基于取整代數優化的求解框架

本文通過定義取整摹加運算,將裝配線平衡問題轉換為混合圖中指定起點和終點的TSP問題,將優先約束關系圖轉換為混合圖,導出混合圖遍歷所有節點的最短路徑,亦即最優操作序列。一定條件下,該操作序列等價于混合圖中遍歷所有節點的最短路徑。裝配線平衡問題求解框圖如圖2所示。

圖2 裝配線平衡問題求解框圖Fig.2 Assembly line balancing solving framework

1.3 TSP問題的改進遺傳算法

在眾多求解TSP問題的方法中,考慮到遺傳算法不依賴于適應度函數的特點,本文選用改進的遺傳算法作為求解工具。圖3為混合圖TSP問題的改進遺傳算法框圖。首先在混合圖中得到一定數量的可行路徑,然后以這些可行路徑作為初始種群,以摹加意義下的路徑長度作為適應度值進行遺傳操作。在進行交叉及變異操作時,需要判斷子代個體是否是混合圖中的可行路徑,然后判斷是否符合結束條件,如果符合,則終止迭代輸出結果。

圖3 混合圖TSP問題的改進遺傳算法框圖Fig.3 Improved genetic algorithm framework for m ixed graph TSP problems

2 取整摹加運算定義及證明

2.1 有向圖、完全圖和混合圖

裝配線平衡問題基本數據如表1所示。反映在圖像上可形成圖4所示的賦權有向圖、完全圖和混合圖。表1所示某生產過程基本數據反映在圖4(a)的賦權有向圖中(圖4中增加了1個虛擬起始節點0,該節點不包含操作工時)。完全圖是指在圖中任意兩個節點之間均有邊連接的圖,如對于圖4(a)的賦權有向圖來說,其對應的完全圖如圖4(b)所示。其中完全圖中的無向邊等價于兩條方向相反的有向邊。把圖4(b)中符合下列條件的邊刪除,得到一個新的混合圖(可能同時包含有向邊和雙向邊,但雙向邊中包含的兩條邊權值有可能不同),如圖4(c)所示。刪除邊的規則是:圖4(a)中直接前序和直接后序之間有向邊的逆向邊;圖4(a)中間接前序與間接后序之間的雙向邊。圖4(b)中符合刪除條件的邊有:

表1 裝配線平衡問題基本數據Table 1 Basic data of assembly line

圖4 裝配線平衡問題有向圖、完全圖和混合圖Fig.4 Directed graph,complete graph and mixed graph

混合圖與賦權有向圖比較而言,增加的邊其權值設置規則為:新增邊ij權值等于原有邊kj權值。kj表示與ij有共同后續節點的原賦權有向圖中的邊(k、i、j均表示節點標號)。

TComp,i為補償后的樣品溫度值,TTc,i-1和TTc,i為相鄰Δt秒內溫度傳感器的兩次采樣值。根據絕熱加速量熱儀的工作原理,反應過程中為保證絕熱,系統會控制爐體各部分加熱器,使爐體溫度緊跟補償后樣品溫度TComp,i,但由于爐體加熱系統受材質影響,時滯性很大,需要給它增加擾動來提高動態響應。設反應Δt秒后對爐體施加的擾動信號TTarget,Δt秒前爐體溫度為TOver,i-1,具體關系為:

2.2 取整摹加運算定義

定義 取整摹加運算是指滿足下列條件的從實數域到實數域的二元運算。

式中:ceil(a)為對正實數a的向上取整運算,如ceil(1.5)=2。

命題 有向圖所表示的裝配線平衡問題等價于對應混合圖的取整摹加意義上的指定起點及終點的遍歷所有節點最短路問題(即TSP問題)。

2.3 取整摹加運算證明

證明1 完全圖中減去“刪除邊”,剩下的是可行邊。

設1次加工過程中經過的有向邊為ij,其中i和j表示兩個相鄰節點,則它們之間的關系有5種可能:①i是j的直接前序;②i是j的間接前序;③i是j的直接后序;④i是j的間接后序;⑤i和j無前后序關系。

違反加工規則的操作是指出現前后序倒裝的操作。根據由完全圖到混合圖的步驟可知,刪除的邊為②、③、④三類情況,在剩下的①、⑤中無前后序倒裝情形出現。因此完全圖中減去刪除邊后,剩下的都是可行邊。證畢。

證明2 沿可行邊走完所有節點恰好完成1次加工。

根據有向邊賦值規則可知,以同一頂點作為后續節點的有向邊其權值相同,代表同一加工步驟,當沿可行邊走完所有節點,也即把所有加工步驟都進行1次且僅進行1次操作。因此,沿可行邊走完所有節點,恰好完成1次加工。證畢。

證明3 取整摹加意義下的最短路即為工位最少時操作序列。

假設加工過程進行到了第i個步驟,共耗時nCT+a表示已經過了n個節拍時間,并在第n+1個節拍中經過了時間a,第i+1個步驟需要b單位時間。記

則ceil(a′)與ceil(b′)的大小關系有以下兩種可能:

(1)ceil(a′)n+1。即第i+1個加工步驟無法在n+1個節拍中完成。因此,總加工時間為

(2)ceil(a′)

因此,按照式(1),定義的取整摹加可以表示裝配線平衡問題中的總時間累加規則(相差1個節拍常數作為系數)。在此意義下對混合圖中得到的遍歷所有節點的最短路徑,即對應了使得節拍最小的加工過程。證畢。

3 算例

3.1 案例1

某含6個操作的裝配線,其生產節拍為20,操作優先關系及各操作時間如表2及圖5所示,求最小工位數。

表2 含6個操作的裝配線基本數據Table 2 Basic data of assembly line containing 6 operations

圖5 含6個操作的裝配線賦權有向圖及混合圖Fig.5 Empowerment digraph and mixed graph of assembly line containing 6 operations

6個操作的工時之和為52 min,該生產線的理論最小工位數為3,其目標函數為使得工位數最小。對應混合圖中有向邊的權值系數如表3所示。

表3 6個操作的裝配線混合圖權值系數表Table 3 Coefficients of mixed graph of assembly line containing 6 operations

對圖5進行取整摹加意義上的遍歷所有節點的最短路徑求解運算,得最優解為→①→②→④→③→⑤→⑥。在生產節拍數為20的約束條件下,最小制造周期為58 min。

3.2 案例2

含30個操作的裝配生產線,其生產節拍為65,操作優先關系及各操作時間如圖6所示,求最小工位數。

圖6 含30個操作的裝配線操作優先關系圖Fig.6 Precedence graph of assembly operation

30個操作的工時之和為517 min,該生產線的理論最小工位數為8,其目標函數為使得工位數最小:

按照改進的遺傳算法,令初始種群的規模為20,交叉率取0.5,變異率取0.08,經過500次迭代,得到最佳生產排序方案。迭代過程中,可行解的目標函數值的變化范圍在[8,9.56]之間;某一次迭代中,一旦目標函數值的最優值小于或等于上一代的最優值,則更新最優解,對于500次迭代,情形大都如此;迭代次數在200次左右開始穩定,此時的目標函數值基本穩定在8.9～9之間,并且群體的平均值趨近于最優值,說明群體的適應性趨向穩定。

對應于最優值工位數為9的操作排序(符合工位數為9的排序不止1個)之一為:①→④→②→③→⑤→⑥→⑦→⑧→⑨→⑩→[11]→[12]→[13]→[14]→[15]678→[19]→[20]→[21]→[22]→[23]→[25]→[24]→[26]→[27]→[28]→[29]→[30]。求解過程中每一代的最優值與平均值及均方差圖如圖7所示。

圖7 最優值與平均值、均方差Fig.7 Optimum value,mean value and deviation

4 結語

將滿足裝配優先約束關系的一組操作均衡地分配于裝配線各工位,提出基于取整摹加優化求解裝配線平衡問題的理論框架,將裝配線平衡問題轉換為TSP問題,定義取整摹加運算加法算子,采用改進的遺傳算法求解轉換后的TSP問題。案例演示證明了算法求解的有效性。

[1] Gutjahr A L,Nemhauser GL.An algorithm for the line balancing problem[J].Management Science,1964,11(2):308-315.

[2] 肖中華.基于改進遺傳算法的汽車裝配線平衡問題研究[D].武漢:武漢科技大學,2009.

[3] 杜運普,楊月新.裝配線生產線的平衡問題研究[J].機械設計與制造,2003(2):104-106.

[4] Ponnambalam S G,A ravindan P,Rao P S.Comparative evaluation of genetic algorithms for job-shop scheduling[J].Production Planning&Control,2001,12(6):560-574.

[5] 鄭大鐘,趙千川.離散事件動態系統[M].北京:清華大學出版社,2001.

[6] 陳進,呂新峰,王濱濱,等.基于極大極小代數法的最優調度方法[J].機械制造,2005,43(495):36-38.

[7] 李妍峰,李軍,趙達.用動態搜索算法求解時間依賴型旅行商問題[J].西南交通大學學報,2008,43(2):187-193.

[8] 秦裕瑗.離散動態規劃與bellman代數[M].北京:科學出版社,2009.

[9] 秦裕瑗.最優路問題——極優代數方法[M].上海:上海科學技術出版社,2009.