遺傳算法在剎車片生產(chǎn)計劃排產(chǎn)中的應(yīng)用與實踐①

姜 鵬,高美鳳

(江南大學(xué) 物聯(lián)網(wǎng)工程學(xué)院,無錫 214122)

由于汽車剎車片生產(chǎn)工序相對其它復(fù)雜產(chǎn)品工序較少,因而以往剎車片生產(chǎn)計劃的排產(chǎn)主要依靠人工來完成.但是隨著剎車片市場對剎車片品種的多樣化和個性化需求不斷增加,使得剎車片的種類日益增多,從而逐漸形成一種多品種變批次的生產(chǎn)模式[1-3].這使得之前依靠人工進(jìn)行剎車片生產(chǎn)計劃排產(chǎn)的模式不能高效適用于新的生產(chǎn)模式,且生成的排產(chǎn)計劃難以合理分配生產(chǎn)資源,給企業(yè)帶來不必要的生產(chǎn)資源浪費.

多品種變批次生產(chǎn)模式的排產(chǎn)問題屬于NPhard 問題[4-6],其中NP 是指非確定性多項式,這類問題無法通過公式推導(dǎo)來精確求解,只能通過“猜測”來間接地獲取結(jié)果,因此僅通過人工來解決該問題,很難求得最優(yōu)解.另外目前針對剎車片生產(chǎn)計劃的排產(chǎn)問題的研究很少,因此,有必要對剎車片生產(chǎn)計劃的排產(chǎn)問題進(jìn)行深入的研究.

1 問題描述

剎車片生產(chǎn)的主要工序有：配料、沖壓和熱壓成型,其分別在配料車間、沖壓車間和熱壓成型車間內(nèi)進(jìn)行.其中配料和沖壓工序是服務(wù)于熱壓成型工序,另外配料車間和沖壓車間有各自的配套倉庫,且生產(chǎn)設(shè)備少產(chǎn)量大,可以直接使用針對熱壓車間生成的排產(chǎn)計劃來提前指導(dǎo)配料車間和沖壓車間的生產(chǎn).而熱壓成型工序時間較長,且熱壓機(jī)數(shù)量多,因此合理利用熱壓機(jī)對提高剎車片的產(chǎn)量至關(guān)重要.因此,本文重點對熱壓機(jī)的多品種變批次生產(chǎn)模式的排產(chǎn)問題進(jìn)行研究.剎車片生產(chǎn)主要的流程如圖1所示.

圖1 剎車片生產(chǎn)主要流程

2 數(shù)學(xué)模型

在建立數(shù)學(xué)模型之前,做出如下合理假設(shè)：

(1)在車間開始排產(chǎn)前,車間單個生產(chǎn)班次的訂單已經(jīng)生成,且不再發(fā)生變化.

(2)在熱壓機(jī)進(jìn)行生產(chǎn)時,各種物料已經(jīng)齊套,不需要考慮物料齊套的運輸問題.

(3)在產(chǎn)品開始熱壓前需要一定的準(zhǔn)備時間ts,來調(diào)整熱壓機(jī)生產(chǎn)參數(shù)和熱壓配套工具等,這里認(rèn)為每種產(chǎn)品準(zhǔn)備時間是相同的且熱壓機(jī)在生產(chǎn)不同的產(chǎn)品前都需要準(zhǔn)備時間.

(4)每臺熱壓機(jī)在生產(chǎn)過程中是連續(xù)生產(chǎn)的,生產(chǎn)過程中不會出現(xiàn)中斷.

(5)每一種產(chǎn)品在開始熱壓前,熱壓工藝已經(jīng)確定,在單個生產(chǎn)班次中不會發(fā)生變化.

(6)在單個生產(chǎn)班次內(nèi)生產(chǎn)的產(chǎn)品是沒有優(yōu)先級的.

(7)一個產(chǎn)品只能在一臺熱壓機(jī)上生產(chǎn)一次.

2.1 目標(biāo)函數(shù)

剎車片生產(chǎn)計劃的排產(chǎn)問題描述為：有m臺功能相同的熱壓機(jī),n種不同的剎車片,單個生產(chǎn)班次訂單中每種剎車片的數(shù)量為Cmjaxj=1 ,2,···,n剎車片車間的排產(chǎn)任務(wù)是將n種不同的產(chǎn)品分配到m臺機(jī)器上,因此得到如下車間排產(chǎn)模型.

第i臺熱壓機(jī)總的加工時間Ti為：

式中,tj表示產(chǎn)品j的熱壓時間,同型號剎車片在不同的熱壓機(jī)上生產(chǎn)時間是相同的；c(j,i)表示產(chǎn)品j在熱壓機(jī)i上的生產(chǎn)數(shù)量；x(j,i)只有1 和0 兩種取值,產(chǎn)品j在熱壓機(jī)i上進(jìn)行生產(chǎn)時等于1,否則等于0；ts表示每種產(chǎn)品開始生產(chǎn)前的準(zhǔn)備時間,這里ts是常數(shù).

則用時最長的熱壓機(jī)生產(chǎn)時間Tmax為：

本次排產(chǎn)設(shè)計的目標(biāo)是獲取整個生產(chǎn)過程最小加工時間的排產(chǎn)計劃,即求m臺熱壓機(jī)中生產(chǎn)時間最長的熱壓機(jī)生產(chǎn)時間最小值,因此目標(biāo)函數(shù)為：

2.2 約束條件

本文建立的數(shù)學(xué)模型是由實際生產(chǎn)現(xiàn)場抽象而來,所以該數(shù)學(xué)模型應(yīng)該和實際生產(chǎn)現(xiàn)場一樣會受到生產(chǎn)能力的約束[7,8],其約束條件如下：

(1)機(jī)器加工時間約束：

式中,Tc表示單個生產(chǎn)班次內(nèi)一臺熱壓機(jī)允許的最長生產(chǎn)時間.

(2)每種產(chǎn)品的總數(shù)量約束：在單個班次內(nèi),每種產(chǎn)品生產(chǎn)的數(shù)量應(yīng)該等于該生產(chǎn)班次訂單中每種剎車片的數(shù)量,即

3 基于聯(lián)合均值-遺傳算法(CMG)算法的排產(chǎn)方案設(shè)計

在產(chǎn)品種類和熱壓機(jī)數(shù)量比較少時,目標(biāo)函數(shù)的非線性程度低,解空間比較小,此時僅僅使用傳統(tǒng)的遺傳算法來求解排產(chǎn)問題,能夠得到比較理想的結(jié)果；但在熱壓機(jī)數(shù)量比較多時,目標(biāo)函數(shù)的非線性程度和解空間都變的比較大,很難得到比較理想的結(jié)果.因此本文針對熱壓成型車間設(shè)計了一種聯(lián)合均值-遺傳算法來解決排產(chǎn)問題,算法首先利用單個生產(chǎn)班次內(nèi)分配在每臺熱壓機(jī)上的理想加工時間進(jìn)行排產(chǎn),即均值排產(chǎn)；然后基于均值排產(chǎn)的結(jié)果再利用遺傳算法繼續(xù)排產(chǎn),即遺傳算法排產(chǎn).較單純使用遺傳算法求解,本文設(shè)計的聯(lián)合均值-遺傳算法將排產(chǎn)問題分兩步進(jìn)行求解,能夠有效的降低目標(biāo)函數(shù)的非線性程度和解空間的復(fù)雜度,從而得到比較理想的排產(chǎn)方案.

3.1 均值排產(chǎn)

單個生產(chǎn)班次內(nèi)分配在每臺熱壓機(jī)上的理想加工時間是車間最小的整體生產(chǎn)時間,所以將單個生產(chǎn)班次內(nèi)分配在每臺熱壓機(jī)上的理想加工時間作為最優(yōu)方案的參考值.為了減少生產(chǎn)準(zhǔn)備時間和物料齊套運輸?shù)某杀?應(yīng)該盡量讓一種產(chǎn)品在一臺機(jī)器上進(jìn)行連續(xù)生產(chǎn),所以首先利用均值進(jìn)行排產(chǎn).具體步驟如下：

(1)首先計算出單個生產(chǎn)班次內(nèi)分配在每臺熱壓機(jī)上理想的加工時間Tmean：

(2)根據(jù)Tmean計算出在該時間段內(nèi)能夠連續(xù)生產(chǎn)產(chǎn)品j的最大數(shù)量Pj：

(3)Pj為在Tmean時間段中產(chǎn)品j在熱壓機(jī)連續(xù)生產(chǎn)的最大數(shù)量,所以首先以Pj為指標(biāo)進(jìn)行均值排產(chǎn).

式中,Hj是產(chǎn)品j在均值排產(chǎn)過程中分配的熱壓機(jī)數(shù)目.

綜上,在均值排產(chǎn)過程中產(chǎn)品j已完成排產(chǎn)的數(shù)量Cj和m臺熱壓機(jī)中已完成排產(chǎn)的總熱壓機(jī)數(shù)量f,如式(9)所示.剩余的沒有在均值排產(chǎn)中排產(chǎn)的熱壓機(jī)與產(chǎn)品將由遺傳算法進(jìn)行排產(chǎn).

3.2 遺傳算法排產(chǎn)

經(jīng)過均值排產(chǎn)后,剩余的產(chǎn)品為

沒有安排生產(chǎn)的熱壓機(jī)為

此時,利用遺傳算法對剩余的機(jī)器和產(chǎn)品進(jìn)行排產(chǎn),以獲得最佳排產(chǎn)結(jié)果.

遺傳算法的主要運算過程包括：編碼、選擇、交叉、變異和迭代[9-11].編碼是遺傳算法的第一步,是整個算法的基礎(chǔ),目前比較流行的編碼規(guī)則有,矩陣編碼、二進(jìn)制編碼、樹形編碼和量子比特編碼等[12].結(jié)合由熱壓成型車間抽象出來的數(shù)學(xué)模型,本文編碼選擇矩陣編碼,其歸屬于實數(shù)編碼,矩陣編碼在求解大規(guī)模數(shù)據(jù)問題和高維度數(shù)據(jù)問題上具有明顯的優(yōu)勢[13].選擇的目的是在種群中選擇合適個體,常見的選擇算子有錦標(biāo)賽算法、隨機(jī)遍歷抽樣法、比例選擇、排序選擇與無回訪隨機(jī)選擇等.本文以熱壓機(jī)生產(chǎn)時間為指標(biāo),將錦標(biāo)賽算法與隨機(jī)遍歷抽樣法相結(jié)合來對種群進(jìn)行選擇,這樣能夠在一定程度上保證在算法快速收斂的同時避免陷入局部最優(yōu).交叉是模擬自然界生物雜交的過程,通過個體間的染色體交叉,會不斷產(chǎn)生新的個體,從而增加種群的多樣性,擴(kuò)展問題的解空間.目前幾種比較常用的適用于實數(shù)編碼的交叉算子有：單點交叉、兩點交叉、均勻交叉等[14].本文為了更好的模擬自然界的染色體交叉,采用一種隨機(jī)交叉方式.變異是自然界的生物繁衍時發(fā)生的一種小概率事件,在遺傳算法中對種群中的個體進(jìn)行變異的主要目的是保持種群的多樣性,同時在一定程度上防止算法陷入局部最優(yōu)[15].最后一步是迭代,通過迭代選擇、交叉與變異,選出最優(yōu)個體.

具體的排產(chǎn)步驟如下：

(1)編碼：首先根據(jù)矩陣編碼規(guī)則,隨機(jī)生成一個個體,然后依照單個個體的編碼規(guī)則,隨機(jī)生成一個種群.單個矩陣的具體編碼規(guī)則如下：

在隨機(jī)生成c(j,i)時,隨機(jī)數(shù)的生成范圍通過單個生產(chǎn)班次理想生產(chǎn)時間Tmean來控制,即滿足：

(2)選擇：按照概率Rg選出前Q個比較優(yōu)秀的個體,同時按概率Rb在除去前Q個體的種群中隨機(jī)選擇出比較差的個體.由于是隨機(jī)選擇個體進(jìn)入下一代,無法具體控制下一代的種群數(shù)量,因此本文設(shè)計的選擇算子中的概率Rg具有一定的自適應(yīng)性,具體自適應(yīng)規(guī)則為：

式中,R1、R2是兩個常量概率,且R1＜R2,S為當(dāng)前迭代的種群數(shù)量,IT代表迭代開始時的初始迭代種群數(shù)量.

(3)交叉：首先根據(jù)種群大小利用隨機(jī)函數(shù)無放回的在種群中隨機(jī)選取一對個體,然后利用隨機(jī)函數(shù)隨機(jī)產(chǎn)生的交叉位置進(jìn)行交叉,最后重復(fù)上述過程,直到整個種群全部完成交叉.因為式(4)和式(5),交叉時應(yīng)該以矩陣的行為單位進(jìn)行平行交叉,即兩個矩陣相同位置處的行進(jìn)行互換.以下為單次交叉的結(jié)果,即隨機(jī)選取的第j行個體進(jìn)行了交叉.

其中,cs(j,i)和cx(j,i)代表隨機(jī)選出的兩個隨機(jī)個體.

(4)變異：首先使用概率Rb用來隨機(jī)選取要進(jìn)行變異的個體,然后利用隨機(jī)函數(shù)隨機(jī)產(chǎn)生的變異位置進(jìn)行變異.同樣因為式(4)和式(5),變異的位置以行為單位.

(5)迭代：綜上4 步,在完成步驟(1)后,通過循環(huán)按順序反復(fù)進(jìn)行(2)、(3)和(4)步驟,通過Tmean值來動態(tài)控制迭代次數(shù),具體控制步驟如下：

式中,Td表示Tmax與Tmean最大允許偏差；L表示當(dāng)前已經(jīng)累計的迭代次數(shù),Lmax表示最大允許的迭代次數(shù).如果循環(huán)同時滿足式(14)和式(15),表示已經(jīng)產(chǎn)生最優(yōu)解,則停止循環(huán),取出最優(yōu)解.如果不滿足式(15),表示算法過早收斂,則刪除當(dāng)前種群重新進(jìn)行步驟(1)到步驟(5).

4 仿真實驗與分析

本文采用處理器為Intel i3-2348M 的計算機(jī),利用Python 在Spyder 上進(jìn)行仿真實驗,利用三個實例來驗證算法的性能.

假設(shè)單個生產(chǎn)班次內(nèi)一臺熱壓機(jī)最大允許生產(chǎn)時間Tc= 400 min,每種產(chǎn)品生產(chǎn)準(zhǔn)備時間均為ts= 6 min,排產(chǎn)實際時間與理想時間允許偏差Td= 9 min.三個實例的具體參數(shù)如表1所示,優(yōu)化排產(chǎn)后的結(jié)果分別如表2、表3、表4和表5所示.

表1 實例數(shù)據(jù)表

表2 實例1 排產(chǎn)計劃

表2中前8 臺熱壓機(jī)排產(chǎn)結(jié)果是均值排產(chǎn)結(jié)果,后2 臺是遺傳算法排產(chǎn)結(jié)果.在表3中前17 臺熱壓機(jī)排產(chǎn)結(jié)果是均值排產(chǎn)結(jié)果,后3 臺是遺傳算法排產(chǎn)結(jié)果.在表4及表5中前25 臺熱壓機(jī)排產(chǎn)結(jié)果是均值排產(chǎn)結(jié)果,后5 臺是遺傳算法排產(chǎn)結(jié)果.根據(jù)式(6)求得三個實例的理想生產(chǎn)時間Tmean分別為78 min、328.5 min 和281 min.而利用本文算法所得到的生產(chǎn)時間Tmax分別為83 min、335 min 和286 min；另外,通過優(yōu)化排產(chǎn)得到的生產(chǎn)時間與理想生產(chǎn)時間的偏差均小于9 min,由此可見三個實例的排產(chǎn)結(jié)果都能夠滿足要求.

表3 實例2 排產(chǎn)計劃

表4 實例3 排產(chǎn)計劃(一)

遺傳算法是模仿自然界生物進(jìn)化的仿生算法,求解結(jié)果具有一定的隨機(jī)性.為了驗證算法的穩(wěn)定性,本文對三個實例分別進(jìn)行了100 次仿真實驗,求得優(yōu)化排產(chǎn)的生產(chǎn)時間與理想生產(chǎn)時間的平均誤差如表6所示.

表6 實際排產(chǎn)與理想排產(chǎn)時間差值表

從表6可見：三個實例的平均誤差都小于9 min,所以本文設(shè)計的排產(chǎn)算法是穩(wěn)定的.

5 結(jié)束語

本文設(shè)計了一種聯(lián)合均值-遺傳算法來解決剎車片生產(chǎn)計劃的排產(chǎn)問題.首先對熱壓成型車間的實際生產(chǎn)現(xiàn)狀進(jìn)行分析,建立了相應(yīng)的生產(chǎn)數(shù)學(xué)模型,然后針對已經(jīng)建立的數(shù)學(xué)模型,設(shè)計了利用聯(lián)合均值-遺傳算法進(jìn)行排產(chǎn)的優(yōu)化方案,最后利用三個實例驗證了算法的性能,得出本文設(shè)計的排產(chǎn)方案可以有效地應(yīng)用于熱壓成型車間.