趙 婧， 包偉華

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

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

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

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

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

1 生產(chǎn)過程瓶頸分析及其模型建立

在生產(chǎn)過程的基礎(chǔ)上，針對生產(chǎn)過程分析瓶頸工序和建模是排產(chǎn)優(yōu)化的重要組成部分。

1.1 壓力變送器生產(chǎn)過程描述

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

圖1 壓力變送器生產(chǎn)流程圖Fig.1 Production flow chart of pressure transmitters

1.1.1 半杯體的制作

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

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

1.1.2 膜盒的制作

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

1.1.3 傳感頭裝配

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

1.1.4 溫度補(bǔ)償

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

1.1.5 總裝

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

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

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

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

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

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

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

(6) 同一道工序，不同機(jī)器的生產(chǎn)時間一致；

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

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

本文還將考慮，在已知某1個或幾個機(jī)器壞的情況下，排產(chǎn)模型需要遵循以下假設(shè)：

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

(2) 機(jī)器故障是排產(chǎn)前已知的；

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

1.2 瓶頸分析及模型建立

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

表1普通量程生產(chǎn)過程及時間

Tab.1 The process and time of general range productionh

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

表2特殊量程生產(chǎn)過程及時間

Tab.2 The process and time of special range productionh

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

表3每個成品和半成品的生產(chǎn)過程及時間

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

2 遺傳算法設(shè)計

遺傳算法采用染色體上的基因?qū)ふ液玫娜旧w來求解問題，具有隱含并行性和全局解空間搜索的特點，在生產(chǎn)調(diào)度中得到廣泛的應(yīng)用。遺傳算法包括5個關(guān)鍵要素：編碼和解碼、適應(yīng)度函數(shù)、初始化種群、遺傳操作(交叉和變異)和參數(shù)設(shè)置。

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

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

(1)

根據(jù)工序的特點，且半加工產(chǎn)品可賣，將采用分步遺傳算法。即將訂單為普通量程的整機(jī)和特殊量程的整機(jī)作為第1環(huán)節(jié)，利用遺傳算法進(jìn)行調(diào)度生產(chǎn)，其次訂單為普通量程的傳感頭和特殊量程的傳感頭作為第2環(huán)節(jié)進(jìn)行調(diào)度生產(chǎn)，最后訂單為普通量程膜盒和特殊量程膜盒作為第3環(huán)節(jié)進(jìn)行工序安排。

2.1 編碼與解碼

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

2.2 初始化種群

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

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

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

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

h(k)=k%p

(2)

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

(i1,i2,…,ij,…)

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

(3)

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

(…,im,…)

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

Tk=∑TOj

(4)

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

(5)

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

2.3 分層交叉選擇

2.3.1 分層交叉

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

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

(6)

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

2.3.2 選擇

針對待改善層的選擇采用錦標(biāo)賽的方式進(jìn)行基因的選擇隨機(jī)產(chǎn)生1個[0, 1]的數(shù)，如果>0.5，則勝者留下來,如果<0.5，則敗者留下來[10]。

最終得到新的排產(chǎn)序列矩陣{im}及與之對對應(yīng)的時間矩陣{TOm}，和最小總時間矩陣{Tk}：

(7)

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

2.4 分步遺傳算法

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

(8)

將得到的整個時間序列進(jìn)行排序，即獲得整體生產(chǎn)時間最小的生產(chǎn)時間

(9)

式中，T1表示第1組序列對應(yīng)的時間總和。

進(jìn)而得到對應(yīng)最小生產(chǎn)時間Tmin的時間訂單生產(chǎn)序列{im}和時間序列{TOm}：

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

(10)

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

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

(1) 基于訂單數(shù)量和種類標(biāo)識將同種類型訂單以45個為1組進(jìn)行分組編碼。

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

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

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

(5) 經(jīng)過選擇后，產(chǎn)生新的50組生產(chǎn)序列，在此基礎(chǔ)上，增添前1道工序，重復(fù)步驟(2)。

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

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

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

3 仿真算例

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

訂單詳情如表4所示。

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

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

生產(chǎn)普通量程的整機(jī)和特殊量程的整機(jī)序列為

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

生產(chǎn)普通量程的傳感頭和特殊量程的傳感頭序列為

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

生產(chǎn)普通量程的膜盒和特殊量程的膜盒序列為

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

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

(11)

所對應(yīng)的訂單序列如下：

生產(chǎn)普通量程的整機(jī)和特殊量程的整機(jī)序列為

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

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

生產(chǎn)普通量程的傳感頭和特殊量程的傳感頭序列為

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

生產(chǎn)普通量程的膜盒和特殊量程的膜盒序列為

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

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

圖3 生產(chǎn)普通整機(jī)和特殊整機(jī)的甘特圖Fig.3 Gantt chart for general products and special products

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

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

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

表5根據(jù)工廠原先生產(chǎn)調(diào)度規(guī)則每個訂單所需時間

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

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

4 結(jié) 語

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