面向訂單的混流裝配線多目標(biāo)調(diào)度研究*

解占新,閆璽鈴,陸春月*

(1.晉中學(xué)院 機(jī)械系,山西 晉中 030619;2.中北大學(xué) 機(jī)械工程學(xué)院,山西 太原 030051)

0 引 言

隨著個性化市場的發(fā)展,越來越多的企業(yè)采用訂單式生產(chǎn)模式來滿足客戶需求[1]。

為了以大規(guī)模生產(chǎn)的成本滿足個性化定制的要求,企業(yè)需要在多品種的基礎(chǔ)上來提高生產(chǎn)效率,又由于采用定制化生產(chǎn),交貨期相對較難確定,這就要求企業(yè)在產(chǎn)品品種、產(chǎn)量、工時、設(shè)備負(fù)荷均衡的前提下,利用一條流水線,科學(xué)地編排投產(chǎn)順序,實(shí)行有節(jié)奏、按比例的混合連續(xù)流水生產(chǎn)。大部分產(chǎn)品一般需要經(jīng)過部件裝配,再進(jìn)行總裝,由于不同部件生產(chǎn)節(jié)拍不同,會在總裝環(huán)節(jié)產(chǎn)生庫存積壓或缺料,靠傳統(tǒng)的人工排產(chǎn)很難實(shí)現(xiàn)總裝分裝系統(tǒng)的生產(chǎn)流暢,需要對總裝線和多條分裝線進(jìn)行協(xié)同計劃與調(diào)度,才能有效地解決上述問題[2]。

目前,關(guān)于混流裝配調(diào)度方面的研究較多,一般集中在裝配線的平衡性及調(diào)度效率方面,優(yōu)化目標(biāo)多為裝配周期、完工時間、成本等指標(biāo)[3-6],優(yōu)化算法大致可歸為數(shù)學(xué)規(guī)劃、啟發(fā)式算法和智能算法[7]。訂單交付的準(zhǔn)時性在實(shí)際生產(chǎn)中很受重視,但這方面的研究較少。PENG Y F等[8]設(shè)計了一種以準(zhǔn)時交付為目標(biāo)的混流裝配線啟發(fā)式算法,比傳統(tǒng)的周期交付算法更具優(yōu)越性,但該研究為基于產(chǎn)線整體的單目標(biāo)優(yōu)化調(diào)度算法。實(shí)際生產(chǎn)中多條流水線協(xié)同組織生產(chǎn),一般進(jìn)行分裝然后進(jìn)行總裝,因此該模型不能很好地描述混流裝配線生產(chǎn)的實(shí)際過程。

本文將混流生產(chǎn)裝配分為子裝配和總裝配兩個階段,并用兩個目標(biāo)函數(shù)來描述上述問題,通過改進(jìn)社會粒子群算法對此進(jìn)行求解驗(yàn)證。

1 面向訂單的混流生產(chǎn)線建模

1.1 問題特點(diǎn)及描述

混流生產(chǎn)線的生產(chǎn)組織方式有兩種:現(xiàn)貨生產(chǎn)(MTS)和訂單生產(chǎn)(MTO)。現(xiàn)貨的需求量與交貨期是確定的;訂單生產(chǎn)的需求量與交貨期事先是無法確定的。

本文研究按訂單生產(chǎn)的產(chǎn)品,裝配時先由零件裝配成子裝配,再將各子裝配進(jìn)行總裝。對于不同的訂單,其裝配工藝流程、裝配作業(yè)方法以及裝配作業(yè)設(shè)備是相似的。

整個裝配過程的問題抽象模型如圖1所示。

圖1 問題抽象模型

由圖1可知,裝配過程為兩個階段:第一個階段,根據(jù)裝配工藝流程在各裝配工位流轉(zhuǎn)裝配,各子裝配和零件在到達(dá)總裝配工位時間準(zhǔn)確,且最大完工時間最短;第二個階段,工件經(jīng)過總裝后,要求整個完工時間接近交貨期,準(zhǔn)時交貨。

根據(jù)裝配工藝的順序要求,產(chǎn)品在分裝線上裝配之后分批次分階段供應(yīng)總裝,部件齊套后才能進(jìn)行總裝線的生產(chǎn)。產(chǎn)品裝配時,依次按一定速度通過每個裝配工位,每個工位至少有一臺設(shè)備工作。第一階段由m臺設(shè)備對m種零部件進(jìn)行并行作業(yè),第二階段由1臺設(shè)備進(jìn)行產(chǎn)品總裝,每個產(chǎn)品只有經(jīng)過第一階段m臺設(shè)備的裝配,才能進(jìn)入到第二階段,同一工序的設(shè)備功能相同,每個工位最多只能加工一個工件,實(shí)現(xiàn)一種部件的裝配工作。每個工件在相應(yīng)設(shè)備上的每道工序所需的加工時間已知,要解決在調(diào)度目標(biāo)最小的情況下,確定所有工件的順序和各工位的設(shè)備配置的問題[9,10]。

1.2 多目標(biāo)優(yōu)化數(shù)學(xué)模型

混流裝配生產(chǎn)線生產(chǎn)過程分為分裝和總裝兩個階段,分裝的部件到達(dá)最后工作臺的時間或早或晚都會影響裝配的最后環(huán)節(jié),從而影響交貨期。筆者用同時度來衡量第一階段部件全部到達(dá)最后裝配工作臺的程度,用準(zhǔn)時度來衡量整個裝配階段的時長之于產(chǎn)品交貨期的準(zhǔn)確程度;建立同時度和基于產(chǎn)品訂單交貨時的準(zhǔn)時度,作為生產(chǎn)線的調(diào)度目標(biāo)。

以第一階段各零件裝配成子裝配的最早與最晚完工時間差為目標(biāo)[11,12],同時度的優(yōu)化函數(shù)可被定義為:

(1)

式中:MT—同時度優(yōu)化函數(shù),min;P—產(chǎn)品總數(shù),個;J—產(chǎn)品的編號,J=1,…,P;BJ—產(chǎn)品J所需的工件總數(shù),個;jJ—商品J的第j個工件,jJ=1,…,BJ;I—工件的加工工序總數(shù);j—工件的編號,j=1,…,n;i—第i道加工工序,t=1,…,T;CT(j,i)—工件j在第i道工序完成時間,min;C(J)—產(chǎn)品J最后組合裝配結(jié)束的時間,min。

上式的含義為在裝配發(fā)生的第一階段,組成同一產(chǎn)品的不同部件及子裝配之間完工的時間間隔最小。

整個產(chǎn)品準(zhǔn)時交貨的能力為截至到該生產(chǎn)周期期末,若總生產(chǎn)時間大于交貨期則產(chǎn)生延期違約,產(chǎn)品拖期懲罰,若總生產(chǎn)時間小于交貨期則提前完工,會增加產(chǎn)品庫存成本?？偵a(chǎn)時間要求盡可能地接近交貨期,每一道工序并不是越早提前完工越好,若提前完工,則每道工序需要投入的存儲成本越高,建模時通過給提前完工這一項(xiàng)的時間加權(quán)重,來降低提前完工的庫存壓力,權(quán)重取值范圍(0,1),具體數(shù)值根據(jù)提前完工在實(shí)際生產(chǎn)中發(fā)生的概率來定。

設(shè)提前拖期懲罰函數(shù)為ET,準(zhǔn)時度的優(yōu)化函數(shù)為:

(2)

式中:ET—提前拖期懲罰函數(shù),min;λ0—權(quán)重;E(J)—產(chǎn)品J提前完成時間,min;T(J)—產(chǎn)品J拖期完工時間,min。

上式的含義為產(chǎn)品的實(shí)際完工時間與客戶要求的交貨時間之間的差值最小。

該模型的約束條件如下:

(1)同一工序上只能有一臺設(shè)備加工一個工件:

(3)

式中:Mi—加工第i階段,并行設(shè)備的數(shù)量,臺;m—第i道工序并行設(shè)備的數(shù)量，m=1,…,Mi;Yjim—1為在第i階段,第m臺設(shè)備上加工工件j;0為其他情況。

(2)工件的加工順序是固定的,上道工序結(jié)束后才可進(jìn)行下道工序:

C(j,i)≥C(j,i-1)+P(j,i)

(4)

式中:C(j,i)—工件j在第i道工序完成的時刻,min;P(j,i)—工件j在第i道工序的加工時間,min。

(3)一臺設(shè)備一次只能處理一個工件:

(2-Yjim-Yrim+Xjri)+CT(j,i)-
CT(r,i)≥P(j,i)j>r

(5)

(3-Yjim-Yrim-Xjri)+CT(r,i)-
CT(j,i)≥P(r,i)j>r

(6)

式中:r—工件的編號,r=1,…,n;Xjri—1為在第i道工序上,工件j的優(yōu)先級高于工件r,0為其他情況。

(4)產(chǎn)品的完工時間,也就是最后一道工序的完成時間:

C(J)≥max(0,dJ-C(J))jJ=1,…,BJ

(7)

式中:dJ—產(chǎn)品J最后合裝對應(yīng)的時間,min。

(5)產(chǎn)品的平均提前與延后的交貨工期:

E(J)=max(0,dJ-C(J))J=1,…,P

(8)

T(J)=max(0,C(J)-dJ)J=1,…,P

(9)

2 基于二維編碼的社會粒子群算法

2.1 社會粒子及吸引點(diǎn)

根據(jù)建立的混流裝配線的數(shù)學(xué)模型,采用粒子群算法求解時其收斂速度快、魯棒性好,但是其尋優(yōu)策略在后期的搜索過程群中,各向同性的粒子容易聚集在最優(yōu)解附近,易陷入局部的極值。因此,本文設(shè)計一種基于社會粒子群的改進(jìn)算法,將“社會原子”引入到粒子群算法中。社會原子具備向社會整體主流趨近的特征,但每個原子具有不同的“趨向閾值”,閾值越高的個體獨(dú)立性越高,閾值越低的個體更容易去跟從其他個體,即:

(10)

(11)

將社會原子中趨向閾值為零的粒子定義為自由粒子,能隨機(jī)生成速度和位置,其他粒子對其更新迭代不產(chǎn)生影響。趨向閾值不為零的粒子定義為跟隨粒子。吸引點(diǎn)在跟隨粒子的迭代更新過程中會影響其狀態(tài)。吸引點(diǎn)附近跟隨粒子的數(shù)量是跟隨粒子狀態(tài)改變的判斷依據(jù),是維持現(xiàn)狀還是跟隨該吸引點(diǎn)。優(yōu)化結(jié)果的快速尋找,只需要通過動態(tài)調(diào)整社會原子的趨向閾值來提高優(yōu)化算法的搜索能力。

自由粒子在社會原子中的比例隨著迭代的進(jìn)行減小,其自適應(yīng)調(diào)整策略如下:

(12)

式中:Tx—第x個粒子的初始閾值;K—常數(shù);k—變量,與種群的最優(yōu)解的適應(yīng)度值的變化相關(guān),當(dāng)k=K時,粒子的趨向閾值減為0。

2.2 粒子編碼與解碼設(shè)計

2.2.1 二維編碼

混流裝配線上,不同的產(chǎn)品其裝配工藝也有所不同,自然數(shù)1,2,…,n表示工件的序號,n個工件分別有i1,i2…,in道裝配工序,則Sni表示第n個工件的第i(i<=in)道工序。裝配線上有若干個產(chǎn)品需要裝配,每個產(chǎn)品又包含若干個零件,這些零件的裝配工序排序?yàn)橐粋€粒子。

為了描述該粒子,可定義為一個二維向量。該粒子的第一維向量由n個工件按其序號將各自工序依次羅列組成,則第一維向量由N=∑n·in個數(shù)據(jù)組成。第二維向量由一組隨機(jī)數(shù)產(chǎn)生,該組隨機(jī)數(shù)由N個(0,1)之間的數(shù)組成,將其按降序排列得到粒子的位置矢量。隨著粒子位置矢量的排列變動,粒子對應(yīng)的第一維向量也隨之變動。粒子相應(yīng)位置上的隨機(jī)數(shù)為生產(chǎn)權(quán)重,其值的大小決定了被安排生產(chǎn)任務(wù)的優(yōu)先權(quán),值越大,其優(yōu)先級越高。

設(shè)某生產(chǎn)線上有產(chǎn)品1和產(chǎn)品2兩個工件需要裝配,其測試數(shù)據(jù)如表1所示。

表1 測試數(shù)據(jù)

由表2可得產(chǎn)品1由工件1和2組成,產(chǎn)品2由工件3和4組成,每個工件有i1=i2=i3=i4=3道工序組成。

根據(jù)測試數(shù)據(jù)對粒子進(jìn)行二維編碼,粒子的二維編碼如圖2所示。

圖2 粒子的二維編碼

粒子首先生成初始編碼,圖2中的第1個的表所示,第一維向量的初值為圖中第1個表的第1行數(shù)據(jù),其第i個1表示第1個工件的第i道工序,其后的第i個2表示第2個工件的第i道工序,以此類推。粒子的第二維向量的初值為圖中第一個表的第2行數(shù)據(jù),是一組隨機(jī)數(shù),將這組隨機(jī)數(shù)按遞減順序排列,此為一個粒子的二維編碼位置矢量,第一維向量即為工件工序序列。排列完成后得到一個粒子的編碼,圖2中的第2個表中的數(shù)據(jù)排列。

2.2.2 解碼

粒子的解碼就是按粒子的慣量權(quán)值大小的優(yōu)先級進(jìn)行排列,其相應(yīng)的工序與工件號也依此順序排序。

設(shè)工件號為Rs,其含義表示第s個產(chǎn)品的第R個工件。解碼完成后,在序列第一次出現(xiàn)的工件號即為該零件的第一道工序,當(dāng)這個工件號再次出現(xiàn)時,就是該零件的第二道工序,以此類推。降序排列后隨機(jī)粒子的可行解的序列為S21,S22,S41,S42,S43,S11,S31,S12,S23,S32,S33,S13。

工件加工調(diào)度方案如表2所示。

表2 調(diào)度方案

2.3 慣量權(quán)值

為了避免后續(xù)遍歷過程中局部優(yōu)化能力的降低,必須降緩其收斂速度,才能不遺漏粒子群的最優(yōu)位置。因此,式(10)中的慣量權(quán)值λ1就要重新賦值,使得粒子種群迭代序列逼近其局部最優(yōu)值的速度自適應(yīng)調(diào)整。

構(gòu)造線性遞減的λ1表達(dá)式,兼顧搜索效率和搜索精度,即:

(13)

式中:λmax—慣量權(quán)值的極大值;λmin—慣量權(quán)值的極小值;Q—最大迭代次數(shù);q—當(dāng)前迭代次數(shù)。

2.4 適應(yīng)度函數(shù)設(shè)計

在粒子群算法中,用適應(yīng)度值用來判斷算法的優(yōu)劣,適應(yīng)度函數(shù)的構(gòu)造尤為重要。本文設(shè)計的適應(yīng)度函數(shù)以車間調(diào)度的問題為基礎(chǔ),將涉及到的求解問題轉(zhuǎn)化為函數(shù)關(guān)系式,將不同的目標(biāo)函數(shù)加上合適的權(quán)重,最后求和得到最終的適應(yīng)度函數(shù),通過適應(yīng)度函數(shù)的計算得到最優(yōu)解。

適應(yīng)度函數(shù)如下所示:

f(x)=ω0×f1(x)+(1-ω0)f2(x)

(14)

式中:ω0—權(quán)重。

該適應(yīng)度值為同時度與準(zhǔn)時度兩個目標(biāo)函數(shù)的求和,在適應(yīng)度函數(shù)中,用權(quán)重來設(shè)置其所占的比重,其取值范圍為(0,1)。

2.5 自然選擇

自然選擇就是將達(dá)爾文進(jìn)化論中的思想應(yīng)用到粒子群算法[9]中,在每次尋優(yōu)迭代算法過程中,根據(jù)上述適應(yīng)度值的大小,將粒子進(jìn)行升序或者降序的排序,用種群中適應(yīng)度值最優(yōu)的1/2粒子取代剩余適應(yīng)度值最劣的粒子,并保存每個粒子遍歷后的歷史最優(yōu)值。

2.6 算法流程

社會粒子群算法求解分段混流裝配的車間調(diào)度改進(jìn)粒子群算法的流程,如圖3所示。

圖3 改進(jìn)粒子群算法的流程圖

改進(jìn)粒子群算法計算機(jī)實(shí)現(xiàn)的主要步驟如下:

步驟1:粒子二維編碼設(shè)計;

步驟2:初始化粒子群。設(shè)置群體的規(guī)模N,粒子的初始位置xi和速度vi。將跟隨閾值賦給每個粒子,從而產(chǎn)生初始吸引點(diǎn);

步驟3:適應(yīng)度值f(xi)計算。根據(jù)適應(yīng)度函數(shù),在迭代中計算粒子的適應(yīng)度值,依此對粒子群進(jìn)行排序;

步驟4:自然選擇。根據(jù)步驟3經(jīng)過排序的粒子群,用種群中適應(yīng)度值最優(yōu)的1/2粒子替換種群中適應(yīng)度值最劣的粒子,并且保留個體最優(yōu);

步驟6:更新參數(shù)。將新的位置xi和速度vi及權(quán)值代入式(10,11);

步驟7:判斷若到達(dá)終止條件(結(jié)果得到較優(yōu)或循環(huán)次數(shù)已經(jīng)到達(dá)設(shè)置的最大循環(huán)次數(shù))則退出,否則返回步驟3,繼續(xù)進(jìn)行計算。

3 實(shí)驗(yàn)與分析

以某企業(yè)裝配線為例驗(yàn)證算法的有效性。設(shè)有不同型號的4種部件,每種部件有不同個數(shù)的零件組成,已知每個部件的裝配順序,每個工件有4道工序,每道工序上的分裝時間及交貨期根據(jù)企業(yè)實(shí)際數(shù)據(jù)給出。

產(chǎn)品工件的分裝時間和交貨期如表3所示。

表3 產(chǎn)品工件的分裝時間和交貨期

各產(chǎn)品的總裝時間分別為9 min、11 min,17 min和6 min。將上述數(shù)據(jù)的信息進(jìn)行編碼寫入算法程序中,用Matlab2017b版編程,程序運(yùn)行環(huán)境為i5處理器、8 G內(nèi)存、2.5 GHz主頻。程序算法主要參數(shù)設(shè)定為種群個數(shù)20,迭代次數(shù)Q=500,慣量權(quán)值最大λmax=0.625,慣量權(quán)值最小λmin=0.450,加速度常數(shù)c1=2,c2=2.1,提前完工權(quán)重λ0=0.3,適應(yīng)度函數(shù)中的f1(x)的權(quán)重值ω0=0.65。

該調(diào)度計劃生產(chǎn)的4種部件共11個工件,用改進(jìn)社會粒子群算法求解與標(biāo)準(zhǔn)粒子群算法,文獻(xiàn)[14]中的混合粒子群算進(jìn)行10次對比。

仿真結(jié)果對比如表4所示。

表4 仿真結(jié)果對比

由表4的仿真數(shù)據(jù)可得:在標(biāo)準(zhǔn)粒子群算法的仿真實(shí)驗(yàn)中,第1次實(shí)驗(yàn)的適應(yīng)度值最小為75.925,結(jié)果最優(yōu),達(dá)到最優(yōu)解的迭代次數(shù)為72次;改進(jìn)社會粒子群算法的10次仿真實(shí)驗(yàn)中,第5次實(shí)驗(yàn)的適應(yīng)度值最小為66.145,結(jié)果最優(yōu),達(dá)到最優(yōu)解的迭代次數(shù)為25次;混合粒子群算法的10次仿真實(shí)驗(yàn)中,第7次實(shí)驗(yàn)的適應(yīng)度值最小為66.64,結(jié)果最優(yōu),達(dá)到最優(yōu)解的迭代次數(shù)為29次。

3種算法仿真得到的算法迭代圖如圖4所示。

圖4 算法迭代圖

由圖4可知:改進(jìn)社會粒子群算法[15]的收斂速度較快,求解較為穩(wěn)定且求解精度高,保證了所有得到的解盡可能接近最優(yōu)的解;改進(jìn)社會粒子群算法迭代到第25次得到最優(yōu)解,其結(jié)果優(yōu)于標(biāo)準(zhǔn)粒子群算法和混合粒子群算法。

最優(yōu)結(jié)果為:總的調(diào)度目標(biāo)函數(shù)為f=66.145,同時度f1(x)=89,提前拖期函數(shù)f2(x)=23.7。

最優(yōu)解的甘特圖如圖5所示。

圖5 最優(yōu)解的甘特圖

從圖5可知：每個工件每個工序開始加工的時刻、加工時間、加工完成的時刻:工件在設(shè)備1上的加工順序?yàn)?3→10→11→9→2→5→8→7→1→4→6;在設(shè)備2上的加工順序?yàn)?3→10→11→9→2→7→5→4→8→6→1;在設(shè)備3上的加工順序?yàn)?10→11→9→7→2→4→3→8→6→5→1;在設(shè)備4上的加工順序?yàn)?7→10→2→11→6→5→9→4→3→8→1。

設(shè)備1開始加工的時刻為0,結(jié)束時刻為159 min,機(jī)器設(shè)備率為100%;設(shè)備2開始加工的時刻為17 min,結(jié)束時刻為215 min,機(jī)器設(shè)備率為74.75%;設(shè)備3開始加工的時刻為55 min,結(jié)束時刻為244 min,機(jī)器設(shè)備率為72.49%;設(shè)備4開始加工的時刻為135 min,結(jié)束時刻為303 min,機(jī)器設(shè)備率為82.74%;4個產(chǎn)品分裝完工時間為[178,223,285,194],加上總裝時間[9,11,17,6],則,每個產(chǎn)品最終完工時間為[187,234,302,200]。

4 結(jié)束語

本文針對面向訂單的混流裝配線調(diào)度的問題進(jìn)行了研究,建立了多目標(biāo)的數(shù)學(xué)模型;設(shè)計了一種二維編碼方式,將生產(chǎn)信息用特定的方法進(jìn)行了編程;在社會粒子群算法中引入了吸引子,使得自由粒子和跟隨粒子的比例實(shí)現(xiàn)了自適應(yīng)調(diào)節(jié),在此基礎(chǔ)上慣性權(quán)重采用線形遞減的方式;采用自然選擇的方式將粒子進(jìn)行選擇替換,提高迭代的效率,更有可能得到較優(yōu)的結(jié)果。

通過與標(biāo)準(zhǔn)粒子群算法及混合粒子群算法的對比,驗(yàn)證了本文模型及算法的可行性與優(yōu)越性。