面向訂單的混流裝配線多目標調度研究*

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

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

0 引 言

隨著個性化市場的發展,越來越多的企業采用訂單式生產模式來滿足客戶需求[1]。

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

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

本文將混流生產裝配分為子裝配和總裝配兩個階段,并用兩個目標函數來描述上述問題,通過改進社會粒子群算法對此進行求解驗證。

1 面向訂單的混流生產線建模

1.1 問題特點及描述

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

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

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

圖1 問題抽象模型

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

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

1.2 多目標優化數學模型

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

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

(1)

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

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

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

設提前拖期懲罰函數為ET,準時度的優化函數為:

(2)

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

上式的含義為產品的實際完工時間與客戶要求的交貨時間之間的差值最小。

該模型的約束條件如下:

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

(3)

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

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

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

(4)

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

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

(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的優先級高于工件r,0為其他情況。

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

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

(7)

式中:dJ—產品J最后合裝對應的時間,min。

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

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 社會粒子及吸引點

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

(10)

(11)

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

自由粒子在社會原子中的比例隨著迭代的進行減小,其自適應調整策略如下:

(12)

式中:Tx—第x個粒子的初始閾值;K—常數;k—變量,與種群的最優解的適應度值的變化相關,當k=K時,粒子的趨向閾值減為0。

2.2 粒子編碼與解碼設計

2.2.1 二維編碼

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

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

設某生產線上有產品1和產品2兩個工件需要裝配,其測試數據如表1所示。

表1 測試數據

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

根據測試數據對粒子進行二維編碼,粒子的二維編碼如圖2所示。

圖2 粒子的二維編碼

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

2.2.2 解碼

粒子的解碼就是按粒子的慣量權值大小的優先級進行排列,其相應的工序與工件號也依此順序排序。

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

工件加工調度方案如表2所示。

表2 調度方案

2.3 慣量權值

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

構造線性遞減的λ1表達式,兼顧搜索效率和搜索精度,即:

(13)

式中:λmax—慣量權值的極大值;λmin—慣量權值的極小值;Q—最大迭代次數;q—當前迭代次數。

2.4 適應度函數設計

在粒子群算法中,用適應度值用來判斷算法的優劣,適應度函數的構造尤為重要。本文設計的適應度函數以車間調度的問題為基礎,將涉及到的求解問題轉化為函數關系式,將不同的目標函數加上合適的權重,最后求和得到最終的適應度函數,通過適應度函數的計算得到最優解。

適應度函數如下所示:

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

(14)

式中:ω0—權重。

該適應度值為同時度與準時度兩個目標函數的求和,在適應度函數中,用權重來設置其所占的比重,其取值范圍為(0,1)。

2.5 自然選擇

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

2.6 算法流程

社會粒子群算法求解分段混流裝配的車間調度改進粒子群算法的流程,如圖3所示。

圖3 改進粒子群算法的流程圖

改進粒子群算法計算機實現的主要步驟如下:

步驟1:粒子二維編碼設計;

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

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

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

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

步驟7:判斷若到達終止條件(結果得到較優或循環次數已經到達設置的最大循環次數)則退出,否則返回步驟3,繼續進行計算。

3 實驗與分析

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

產品工件的分裝時間和交貨期如表3所示。

表3 產品工件的分裝時間和交貨期

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

該調度計劃生產的4種部件共11個工件,用改進社會粒子群算法求解與標準粒子群算法,文獻[14]中的混合粒子群算進行10次對比。

仿真結果對比如表4所示。

表4 仿真結果對比

由表4的仿真數據可得:在標準粒子群算法的仿真實驗中,第1次實驗的適應度值最小為75.925,結果最優,達到最優解的迭代次數為72次;改進社會粒子群算法的10次仿真實驗中,第5次實驗的適應度值最小為66.145,結果最優,達到最優解的迭代次數為25次;混合粒子群算法的10次仿真實驗中,第7次實驗的適應度值最小為66.64,結果最優,達到最優解的迭代次數為29次。

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

圖4 算法迭代圖

由圖4可知:改進社會粒子群算法[15]的收斂速度較快,求解較為穩定且求解精度高,保證了所有得到的解盡可能接近最優的解;改進社會粒子群算法迭代到第25次得到最優解,其結果優于標準粒子群算法和混合粒子群算法。

最優結果為:總的調度目標函數為f=66.145,同時度f1(x)=89,提前拖期函數f2(x)=23.7。

最優解的甘特圖如圖5所示。

圖5 最優解的甘特圖

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

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

4 結束語

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

通過與標準粒子群算法及混合粒子群算法的對比,驗證了本文模型及算法的可行性與優越性。