基于分步遺傳算法的壓力變送器排產優化

趙 婧， 包偉華

(1. 上海電力學院， 自動化工程學院， 上海 200090； 2. 上海自動化儀表有限公司， 技術中心， 上海 200072)

車間調度是優化生產的關鍵，是指在盡可能滿足約束條件(如工藝路線、資源情況、交貨期)的前提下，通過下達生產指令，安排其組成部分(操作)所使用的資源，加工時間及加工的先后順序，獲得產品制造時間或成本等的最優化。由于儀表類訂單主要的特點為批量小，品種多，單臺產品生產周期較長，且存在半成品可銷售的情況，故采用部分庫存準備。這種半成品可銷售可庫存的車間生產模式，突破了工序唯一性限制，從而使得作業車間調度問題更復雜。

基于瓶頸分析思想構建的啟發式算法[1]，已經用于許多車間調度問題的求解。在解決生產調度問題和其他復雜的組合優化問題中，元啟發式智能算法是很有效的方法，其中包括遺傳算法、粒子群優化算法、模擬退火算法等。其中，遺傳算法是通過模擬自然界生物遺傳過程和選擇過程，通過產生編碼，初始種群，交叉遺傳，變異等適者生存的過程，產生優化解。因其通用性強，計算性能優良，隱含并行性好，全局搜索能力佳等諸多特點，遺傳算法廣泛應用于車間調度問題的求解。Li等[2]提出針對車間生產的特殊性，通過設計基于動態過程編碼的遺傳算子，保留最優指標，實現柔性作業的標準遺傳算法，滿足靈活的工作任務調度要求。趙詩奎等[3]提出了基于工序的染色體編碼方式，染色體中的工序位置順序和實際的調度工序實際加工順序一致，從而能夠體現每臺機器上的工序實際加工順序。田旻等[4]提出采用分層混合遺傳算法，在初始化種群時根據目標函數分為不同質的2層，即精英層和普通層，針對2層采用不同的災變和鄰域搜索求解，提高了遺傳算法局部領域搜索能力和增強種群的多樣性。

在實際生產中在訂單生產周期長、批量小的情況下，如果不考慮訂單組合生產的情況，就有可能會丟失一部分可行解。并且在壓力變送實際生產過程中，存在多種量程器件，某個工序階段不使用同種設備，需要在初始化階段進行處理。在實際生產過程中，一旦分配好了工序，就將該車間調度問題轉化為傳統車貸的調度問題，從而降低了算法的復雜度。

本文在研究分析某廠壓力變送器生產過程及對工序瓶頸分析的基礎上，提出基于傳感器部件的量程分類件進行哈希除去余數法插入種群初始化，并基于工序和數量進行編碼的分層分步遺傳算法，降低此車間調度問題的復雜度，將其轉換為類似流水車間調度問題。與原工廠排產策略相比，減少了訂單最小完成時間，提高了生產效率。

1 生產過程瓶頸分析及其模型建立

在生產過程的基礎上，針對生產過程分析瓶頸工序和建模是排產優化的重要組成部分。

1.1 壓力變送器生產過程描述

壓力變送器的生產存在訂單批量小，規格品種多，單臺生產時間周期長的特點，并且在半杯體生產過程中，半杯體的量程存在不確定性的問題。壓力變送器具體生產過程如圖1所示。

圖1 壓力變送器生產流程圖Fig.1 Production flow chart of pressure transmitters

1.1.1 半杯體的制作

半杯體制作可以分為燒制、檢驗分類、精加工3個階段。燒制一般為批量生產,1批生產 4 500 個，燒制后根據人工檢驗將量程粗分為3個等級，普通量程4的數量較多，特殊量程3和5的數量較少。經過精加工以后，普通量程4的半杯體可覆蓋6種規格傳感器，特殊量程3的半杯體可覆蓋2種規格傳感器，而特殊量程5僅可覆蓋1種規格傳感器。

每個半杯體的人工檢驗分類，平均花費約5 min，且不存在機器損壞情況。

1.1.2 膜盒的制作

2個相同量程等級的半杯體為膜盒的原料，膜盒制作分為鍍膜、膜片成型、抽氣、灌油、油量測試、疲勞測試等工序。每個工序至少有2臺機器同時工作，但必須嚴格按照工序加工，鍍膜工序需要 5 min；膜片成型工序需要10 min；抽氣工序需要 3 h，但無需考慮數量限制；灌油工序1次最多45個，每次需要6 h；油量測試工序需要5 min；疲勞測試工序需要5 min。膜片成型工序存在 1.5% 的報廢率，灌油工序存在4%的報廢率。膜盒可以作為產品進行單獨銷售。

1.1.3 傳感頭裝配

傳感頭裝配包括打壓測試和焊接等工序，每個工序有2臺機器同時工作，每件傳感頭在打壓測試和焊接工序各需要花費約10 min。

1.1.4 溫度補償

傳感頭的溫度補償工藝，要求在3個溫度點(20 ℃，-20 ℃，70 ℃)進行全量程范圍壓力(包括：0%，25%，50%，75%，100%)的檢測及標定。從一個到另一溫度點的穩定時間約為2 h，每個溫度點的壓力檢測時間約為10 min，因此每個傳感頭的溫度補償過程一般需要5～6 h。

1.1.5 總裝

每臺壓力變送器的總裝及檢驗需要15 min，由1人完成，不存在機器損壞情況。

在所有機器運行正常的情況下，其中排產模型還需要遵循以下約束條件和前提[5]：

(1) 每個工件都必須在原料準備好的情況下才能加工；

(2) 每個量程等級的每個工序結束后，成品或半成品都服從離散正態分布；

(3) 本道工序必須在前一道工序有足夠的成品或半成品，或前一道工序完成后才能進行；

(4) 同一時刻同一機器只能加工1個工件；

(5) 將半杯體檢驗分類以后的半成品視為原材料；

(6) 同一道工序，不同機器的生產時間一致；

(7) 在加工過程中，機器正常運行(不會存在故障情況)；

(8) 排產前已知半成品和每個量程等級的半杯體的數量。

本文還將考慮，在已知某1個或幾個機器壞的情況下，排產模型需要遵循以下假設：

(1) 不會出現同一工序所有機器都損壞的情況；

(2) 機器故障是排產前已知的；

(3) 加工中不存在機器損壞的情況。

1.2 瓶頸分析及模型建立

根據上述生產過程分析，本模型將壓力變送器整機和半成品可賣期間分為普通量程和特殊量程，由于抽氣和灌油單次不能多于45個，且45個一起完成，其他工藝可單個生產，且用時較短，因此認定抽氣和灌油工序，在此生產過程為制約生產的瓶頸工藝，在考慮報廢率的基礎上，以42個實際完成工件為1組進行生產，并且根據半成品是否可賣，加工時間，將工序簡化。以普通量程4的壓力變送器為例，簡化后每道工序及其所需的時間如表1所示。

表1普通量程生產過程及時間

Tab.1 The process and time of general range productionh

特殊量程3和5的壓力變送器，由于需求少(假設每個訂單不會超過45個)，抽氣和灌油則1個訂單為準，加工時間相對較長，則按訂單進行生產，特殊量程簡化后生產工序時間如表2所示。

表2特殊量程生產過程及時間

Tab.2 The process and time of special range productionh

根據訂單情況，將成品和半成品分為6類：普通量程膜盒，特殊量程膜盒，普通量程傳感頭，特殊量程傳感頭，普通量程壓力變送器，特殊量程壓力變送器，分別用W1～W6表示。

表3每個成品和半成品的生產過程及時間

Tab.3 The process and time of products and semi-finished productsh

2 遺傳算法設計

遺傳算法采用染色體上的基因尋找好的染色體來求解問題，具有隱含并行性和全局解空間搜索的特點，在生產調度中得到廣泛的應用。遺傳算法包括5個關鍵要素：編碼和解碼、適應度函數、初始化種群、遺傳操作(交叉和變異)和參數設置。

經典的遺傳算法應用于調度問題，步驟如下：首先基于工序進行編碼[6]，其次隨機產生N個可行解，N種群規模，然后計算個體的適應度，評價個體的使用度，判斷是否達到終止條件，若滿足，則輸出搜索解，否則按選擇策略選擇下一代種群規模N，按交叉概率PC執行交叉操作，按變異概率PM執行變異操作，產生新的種群。返回到計算個體的使用度步驟循環直到得到滿足適應度的優質解[7]。

本文以訂單為基礎,以最小完成時間為目標函數。訂單集合為O:{O1,O2,…},其中每個訂單信息,包括2個元素:On{產品類型wi，生產時間Ti},每個訂單可含多個產品類型。本文以完成訂單為目標,可建立以下目標函數：

(1)

根據工序的特點，且半加工產品可賣，將采用分步遺傳算法。即將訂單為普通量程的整機和特殊量程的整機作為第1環節，利用遺傳算法進行調度生產，其次訂單為普通量程的傳感頭和特殊量程的傳感頭作為第2環節進行調度生產，最后訂單為普通量程膜盒和特殊量程膜盒作為第3環節進行工序安排。

2.1 編碼與解碼

基于訂單數量和種類標識對每個訂單進行分組編碼，基于瓶頸工藝中灌油最多為45個，考慮到不良率為4%～6%，將相同的產品訂單以42個為單位分組，如果42個產品都來自同一訂單，則采用2位數編碼，例如11、12、21等，十位數表示來自第幾個訂單(先將訂單按交貨時間，進行排序)。個位數1、2、3、4、5、6分別表示普通量程膜盒、特殊量程膜盒、普通量程傳感頭、特殊量程傳感頭、普通量程壓力變送器，特殊量程壓力變送器。若42個產品來自于2個訂單，則采用5位數編碼機制，例如 12281，萬位數和百位數表示來自第幾個訂單，千位數和十位數表示2種產品分別占總的比例，個位代表產品類型。12281 表示這個組產品中第1個訂單的數量為42的20%、第2個的訂單數量為42的80%，只保留1位小數。染色體采用單鏈編碼的方式(11，12，13，21，22，23，11，22，12281)，11出現2次說明1號訂單需要84個膜盒，分為2組進行處理調度排產。

2.2 初始化種群

(1) 基于溫度補償環節，特殊量程的器件和普通量程的器件可以分別在 1151 溫度補償裝置和 3151 溫度補償裝置上同時進行補償，因此盡可能使得特殊量程和普通量程交替生產，基于訂單將需要溫補的特殊量程和普通量程分別進行，隨機產生50個序列：

(a1,a2,…,aj,…)，(b1,b2,…,bj,…)

其中：aj表示第j個普通量程的器件，bj表示第j個特殊量程的器件。

(2) 采用哈希算法中除去余數法：

h(k)=k%p

(2)

根據式(2)將序列(b1,b2,…,bj,…)插入到序列(a1,a2,…,aj,…)中，得到整體初始化序列{ij}：

(i1,i2,…,ij,…)

并計算每個訂單所需時間：

(3)

式中：TOj表示第j個訂單O所需要的時間。然后計算這批訂單總的時間，選擇出總時間最小的序列：

(…,im,…)

im代表1個訂單編碼，在式(3)的基礎上計算每組序列時間總和

Tk=∑TOj

(4)

迭代50次，得到序列矩陣{im}，序列對應的時間矩陣{TOm}和總時間矩陣{Tk}：

(5)

式中：im代表1個訂單編碼；TOm表示第m個訂單O所需要的時間；T1表示第1組序列對應的時間總和。

2.3 分層交叉選擇

2.3.1 分層交叉

根據總時間將矩陣分為精英層和待改善層[8]，如果采用雙親染色體交換，則會產生出現工件工序重復或缺失情況[9]。因此，采用單親交叉的方式，將待改善層對應序列進行單親交叉，即隨機交換2個訂單序列的位置，如下式所示：

(i1,i2,…,im,…,in,…)→(i1,i2,…,in,…,im,…)

(6)

將第m個訂單序列和第n個訂單序列進行交換，其中im表示某個訂單的編碼。

2.3.2 選擇

針對待改善層的選擇采用錦標賽的方式進行基因的選擇隨機產生1個[0, 1]的數，如果>0.5，則勝者留下來,如果<0.5，則敗者留下來[10]。

最終得到新的排產序列矩陣{im}及與之對對應的時間矩陣{TOm}，和最小總時間矩陣{Tk}：

(7)

式中：im代表1個訂單編碼；TOm表示第m個訂單O所需要的時間；T1表示第1組序列對應的時間總和。

2.4 分步遺傳算法

采用分步遺傳，每一環節的初始化是基于前一環節的算法結果。基于上述遺傳算法流程和壓力變送器生產流程及產品出售情況，將整個調度排產進行分步遺傳計算，首先利用上述遺傳算法，將整機生產訂單進行排序及時間計算，即將編碼以5、6結尾的2位數和編碼以5、6開頭的5位數的訂單序列，進行排序及時間計算。在計算結果的基礎上，加入編碼以3、4結尾的2位數和編碼以3、4開頭的訂單序列，進行排序及時間的計算，在此基礎上，再加入編碼以1、2結尾的2位數和編碼以1、2開頭的5位數的訂單序列，進行排序及時間計算。最終將50組計算結果分為精英層和待改善層，針對待改善層，進行選擇交叉。最終得到整批訂單的生產序列矩陣{im}，序列對應的時間矩陣{TOm}和總時間矩陣{Tk}：

(8)

將得到的整個時間序列進行排序，即獲得整體生產時間最小的生產時間

(9)

式中，T1表示第1組序列對應的時間總和。

進而得到對應最小生產時間Tmin的時間訂單生產序列{im}和時間序列{TOm}：

(i1,i2,…,im,…)(TO1,TO2,…,TOm,…)

(10)

式中：im代表1個訂單編碼，TOm表示第m個訂單O所需要的時間。

綜上所述，分步分層遺傳算法步驟如下：

(1) 基于訂單數量和種類標識將同種類型訂單以45個為1組進行分組編碼。

(2) 將特殊的器件和普通量程的器件進行分別初始化，隨機產生50組訂單生產序列{ai}，{bi}，再采用哈希算法中除去余數法,將{bi}插入到{ai},得到最終的初始化訂單生產序列{ij}。

(3) 根據目標函數計算每組序列的生產總的時間Tk=∑TOj，根據總的生產時間將訂單生產序列分為精英組和待改善組。

(4) 針對待改善層隨機交換2個序列的順序，產生新的訂單生產序列，再采用錦標賽的方式進行基因選擇隨機產生1個[0, 1]的數，如果>0.5，則勝者留下來,如果<0.5，則敗者留下來。

(5) 經過選擇后，產生新的50組生產序列，在此基礎上，增添前1道工序，重復步驟(2)。

(6) 當所有工序都添加完成，并經過上述算法，最終得到整體的訂單生產工序{im}和對應的生產時間{Tk}，將生產時間進行排序得到最小的生產時間Tmin。

分步遺傳算法流程圖如圖2所示。

圖2 分步分層遺傳算法流程圖Fig.2 Flow chart of step-by-step hierarchical genetic algorithm

3 仿真算例

以某天實際獲得的訂單為例，采用上述算法，對訂單進行排序與時間計算，分別求得這批訂單的總體所需要花費的時間，驗證算法的可行性。

訂單詳情如表4所示。

表4 仿真模擬訂單詳情Tab.4 Simulated order details 個

在Matlab2013的平臺上，對上述遺傳算法進行仿真，并且為了方便測試，直接將這批訂單利用基于遺傳標識訂單數量和種類編碼方式拆分好的訂單序列，再基于分步規則，將訂單序列分為如下情況：

生產普通量程的整機和特殊量程的整機序列為

(15，25，25，55，65，95，95，51 374，16，16，16，26，66，66，76，86，86，86)

生產普通量程的傳感頭和特殊量程的傳感頭序列為

(13，13，23，63，63，63，63，73，83，14，14，24，24，64，94，41 347)

生產普通量程的膜盒和特殊量程的膜盒序列為

(11，31，61，81，13 723，22，22，32，32，52，92)

將這些序列作為分步遺傳算法的輸入，這里將基于分步遺傳算法得到50組訂單序列矩陣和時間序列矩陣，獲得整體生產時間最小的生產時間：

(11)

所對應的訂單序列如下：

生產普通量程的整機和特殊量程的整機序列為

(26，55， 66，25，16，25，66，15，76，15，86，95，16，

95，66，65，66，51 374，86，65，16，55)

生產普通量程的傳感頭和特殊量程的傳感頭序列為

(24，83，24，13，14，13，64，23，14，73，94，63，41 347，63，63)

生產普通量程的膜盒和特殊量程的膜盒序列為

(52，61，31，22，13 723，32，22，11，92，81，32)

總體耗時為765 h，將最小生產時間對應的訂單序列和時間序列，在Teambition中轉化為甘特圖如圖3～5所示。

圖3 生產普通整機和特殊整機的甘特圖Fig.3 Gantt chart for general products and special products

圖4 生產普通傳感頭和特殊傳感頭的甘特圖Fig.4 Gantt chart for general sensing head and special sensing head

圖5 生產普通膜盒和特殊膜盒的甘特圖Fig.5 Gantt chart for general capsule and special capsule

車間原先采用排產的規則為先到的訂單先生產，即先生產訂單1，再生產訂單2，依次類推。如相同訂單，遵循原先排產策略，則每個訂單時間花費如表5所示。

表5根據工廠原先生產調度規則每個訂單所需時間

Tab.5 The time required for each order according to the factory's original production scheduling rulesh

同一批訂單，若按工廠原先生產調度原則，所需要的時間為 1 049.5 h，基于本文提出的分步遺傳算法進行調度，所需時間為765 h，生產效率提高了 27.10%。仿真驗證結果表明，此算法可以提高生產效率，優化車間生產調度。

4 結 語

本文針對開放式生產過程的壓力變送器生產流程，在分析瓶頸工藝的基礎上，采用分步分層遺傳算法，將原來復雜的開放式生產過程轉化為流式生產過程，使得排產過程變得相對簡便，另外Matlab仿真驗證結果表明，與原來根據訂單順序決定生產順序的生產調度策略相比，本文提出的基于分布分層遺傳算法的生產調度策略，提高了車間生產效率，有利于進一步提高準時交貨率，提高產品的競爭力。