姜 鵬,高美鳳

(江南大學 物聯(lián)網工程學院,無錫 214122)

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

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

1 問題描述

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

圖1 剎車片生產主要流程

2 數(shù)學模型

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

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

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

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

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

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

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

(7)一個產品只能在一臺熱壓機上生產一次.

2.1 目標函數(shù)

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

第i臺熱壓機總的加工時間Ti為：

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

則用時最長的熱壓機生產時間Tmax為：

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

2.2 約束條件

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

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

式中,Tc表示單個生產班次內一臺熱壓機允許的最長生產時間.

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

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

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

3.1 均值排產

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

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

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

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

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

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

3.2 遺傳算法排產

經過均值排產后,剩余的產品為

沒有安排生產的熱壓機為

此時,利用遺傳算法對剩余的機器和產品進行排產,以獲得最佳排產結果.

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

具體的排產步驟如下：

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

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

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

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

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

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

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

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

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

4 仿真實驗與分析

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

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

表1 實例數(shù)據表

表2 實例1 排產計劃

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

表3 實例2 排產計劃

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

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

表6 實際排產與理想排產時間差值表

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

5 結束語

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