葛茂根 劉明周 錢(qián) 芳 扈 靜 蔣增強(qiáng) 張銘鑫
合肥工業(yè)大學(xué),合肥,230009
基于JIT的多目標(biāo)總裝準(zhǔn)時(shí)物料配送方法研究
葛茂根 劉明周 錢(qián) 芳 扈 靜 蔣增強(qiáng) 張銘鑫
合肥工業(yè)大學(xué),合肥,230009
針對(duì)機(jī)械產(chǎn)品總裝過(guò)程中的準(zhǔn)時(shí)物料配送問(wèn)題,從優(yōu)化目標(biāo)、約束條件及影響因素三方面考慮,提出以物料運(yùn)輸成本、物料運(yùn)輸時(shí)間、線旁庫(kù)存三者綜合為優(yōu)化目標(biāo)的多目標(biāo)準(zhǔn)時(shí)物料配送模型。給出優(yōu)化目標(biāo)的計(jì)算方法,并設(shè)計(jì)了混合粒子群算法,給出了使用此算法求解模型的具體實(shí)現(xiàn)過(guò)程。最終求解得到物料配送單用于指導(dǎo)配送,使決策者能夠根據(jù)實(shí)際情況選擇優(yōu)化的偏好值。通過(guò)一個(gè)總裝車間準(zhǔn)時(shí)物料配送問(wèn)題的實(shí)例驗(yàn)證了此模型和算法的有效性。
準(zhǔn)時(shí)物料配送;多目標(biāo);JIT(準(zhǔn)時(shí));混合PSO
在機(jī)械產(chǎn)品總裝過(guò)程中,當(dāng)物料供應(yīng)商與裝配車間之間距離較遠(yuǎn)時(shí),采用中轉(zhuǎn)庫(kù)、工位庫(kù)存兩級(jí)庫(kù)存的模式儲(chǔ)存物料并安排配送。目前,國(guó)內(nèi)外學(xué)者對(duì)兩級(jí)庫(kù)存模式下的物料配送問(wèn)題進(jìn)行了相關(guān)研究,其中:文獻(xiàn)[1-2]提出用看板系統(tǒng)實(shí)現(xiàn)物料拉動(dòng)配送;文獻(xiàn)[3]提出運(yùn)用按燈系統(tǒng)來(lái)提高生產(chǎn)線的吞吐量;文獻(xiàn)[4]在文獻(xiàn)[3]基礎(chǔ)上提出一套專門(mén)為汽車生產(chǎn)、裝配線設(shè)計(jì)的信息管理和控制的多媒體自動(dòng)化控制Andon系統(tǒng);文獻(xiàn)[5-6]在研究中設(shè)定了最大庫(kù)存與安全庫(kù)存,當(dāng)線旁庫(kù)存低于安全庫(kù)存數(shù)量時(shí),按最大庫(kù)存進(jìn)行配送;文獻(xiàn)[7]提出注塑企業(yè)的準(zhǔn)時(shí)物料配送方法,即根據(jù)時(shí)間、交貨期和相同時(shí)間內(nèi)物料消耗數(shù)量等因素排序得到總的配送計(jì)劃。
以上關(guān)于物料配送的研究文獻(xiàn)大多集中在拉動(dòng)式物料配送和周期性物料配送,研究重點(diǎn)是倉(cāng)儲(chǔ)部門(mén)如何及時(shí)響應(yīng)生產(chǎn)現(xiàn)場(chǎng)物料需求并降低車輛運(yùn)輸成本。本文針對(duì)機(jī)械產(chǎn)品總裝過(guò)程物料配送批量小、批次多、線旁庫(kù)存空間有限等特點(diǎn),提出包含配送成本、配送時(shí)間和線旁庫(kù)存的多目標(biāo)準(zhǔn)時(shí)物料配送模型,以指導(dǎo)倉(cāng)儲(chǔ)部門(mén)進(jìn)行多頻次、小批量的主動(dòng)送料,并根據(jù)實(shí)際情況選擇優(yōu)化的偏好值。
在準(zhǔn)時(shí)制(just-in-time,JIT)生產(chǎn)模式下,機(jī)械產(chǎn)品總裝過(guò)程中的物料配送問(wèn)題可以描述為:先由生產(chǎn)計(jì)劃獲知需要生產(chǎn)的產(chǎn)品型號(hào)與數(shù)量,然后根據(jù)產(chǎn)品的制造物料清單(bill of materials,BOM)計(jì)算生產(chǎn)該批產(chǎn)品所需要的零部件種類與數(shù)量[8]。例如:若要生產(chǎn)一個(gè)70B3型號(hào)的變速箱,則在工位OP3030需要4個(gè)同步彈簧。若70B3變速箱2010年8月1日的日生產(chǎn)計(jì)劃是100臺(tái),則2010年8月1日在工位OP3030需要400個(gè)同步彈簧供生產(chǎn)該產(chǎn)品使用。得到每個(gè)工位需要配送的各種零部件及數(shù)量之后,就可利用多目標(biāo)準(zhǔn)時(shí)物料配送模型計(jì)算物料配送指導(dǎo)單,安排運(yùn)輸設(shè)備在指定的時(shí)間將指定數(shù)量的零部件運(yùn)送到指定工位供生產(chǎn)使用。準(zhǔn)時(shí)物料配送的目標(biāo)是在保證生產(chǎn)現(xiàn)場(chǎng)物料不缺料、不堆積的前提下,考慮配送過(guò)程的經(jīng)濟(jì)性以及配送時(shí)間的實(shí)效性,使其達(dá)到整體最優(yōu)。其生產(chǎn)過(guò)程需要滿足以下假設(shè)與約束條件:
(1)本文中的物料配送是指將物料從車間緩存區(qū),即物料中轉(zhuǎn)庫(kù)配送到生產(chǎn)現(xiàn)場(chǎng)工位,不包括物料的采購(gòu)過(guò)程。
(2)僅考慮因受工位庫(kù)存面積限制需要多次配送的主動(dòng)配送件,不考慮體積小、通用性強(qiáng)的標(biāo)準(zhǔn)件等非配送件。
(3)產(chǎn)品的裝配工藝即制造物料清單事先已經(jīng)確定。
(4)產(chǎn)品的生產(chǎn)計(jì)劃已知,按規(guī)定的節(jié)拍持續(xù)生產(chǎn)。
(5)用于配送的運(yùn)輸設(shè)備已知,設(shè)備的運(yùn)輸能力僅考慮運(yùn)輸設(shè)備的載重量及容積約束,不考慮運(yùn)輸設(shè)備的最大運(yùn)輸時(shí)間約束。
優(yōu)化目標(biāo)主要考慮物料配送過(guò)程中發(fā)生的運(yùn)輸成本、運(yùn)輸時(shí)間和線旁庫(kù)存。其中,運(yùn)輸成本包括啟用運(yùn)輸工具的固定成本和與載重量及行駛距離相關(guān)的可變成本。由于車間生產(chǎn)面積的限制以及裝配過(guò)程工位布局相對(duì)簡(jiǎn)單,本文僅考慮與載重量相關(guān)的可變成本,而忽略與行駛距離相關(guān)的可變成本。運(yùn)輸時(shí)間包括車輛行駛時(shí)間與服務(wù)時(shí)間,即從配送第一批物料開(kāi)始至完成配送任務(wù)時(shí)整個(gè)物料配送過(guò)程所需總時(shí)間。線旁庫(kù)存指的是裝配線工位旁料箱料架的物料庫(kù)存量。
本文將物料配送過(guò)程中的影響因素分為靜態(tài)影響因素與動(dòng)態(tài)影響因素兩種。其中靜態(tài)因素包括:工位-物料最大存儲(chǔ)數(shù)量、車輛-物料運(yùn)輸能力以及裝配線生產(chǎn)節(jié)拍等相對(duì)固定不變的影響因素;動(dòng)態(tài)因素包括:工位-物料需求數(shù)量、工位-物料需求時(shí)間窗以及工位-物料線旁庫(kù)存數(shù)量等隨生產(chǎn)進(jìn)行而不斷發(fā)生改變的影響因素。
物料配送過(guò)程的約束條件包括運(yùn)力約束、生產(chǎn)約束以及庫(kù)存約束等。其中,運(yùn)力約束是指每一次配送的各種零部件之和不能超過(guò)運(yùn)輸設(shè)備的總運(yùn)輸能力,即要分別考慮車輛載重量的約束以及車輛容積的約束。生產(chǎn)約束是指每一次物料配送的時(shí)間與零部件數(shù)量滿足裝配線按節(jié)拍生產(chǎn)的約束,即需保證現(xiàn)場(chǎng)生產(chǎn)的不缺料。庫(kù)存約束是指每一次物料配送后,線旁工位零件數(shù)量不能超過(guò)其最大存儲(chǔ)數(shù)量,即不能造成現(xiàn)場(chǎng)物料的堆積。
在綜合考慮優(yōu)化目標(biāo)、影響因素與約束條件的基礎(chǔ)上,建立的準(zhǔn)時(shí)物料配送數(shù)學(xué)模型為
式(1)為配送模型的優(yōu)化目標(biāo)函數(shù),x表示一個(gè)可行解;式(2)表示運(yùn)輸成本之和;式(3)表示每次配送前各個(gè)工位零件線旁庫(kù)存之和;式(4)表示配送時(shí)間總和;式(5)表示各運(yùn)輸設(shè)備運(yùn)力之和至少大于一個(gè)節(jié)拍內(nèi)每個(gè)工位所需的零件數(shù)量總和;式(6)表示每種零件的總配送量滿足生產(chǎn)需求;式(7)表示每一批各個(gè)運(yùn)輸設(shè)備運(yùn)送的零件總數(shù)不超過(guò)該運(yùn)輸設(shè)備的運(yùn)力;式(8)、式(9)分別表示第1批或者第k批物料的配送時(shí)間小于或者等于零件消耗最快、最先不能滿足生產(chǎn)的工位的要料時(shí)間;式(10)表示到達(dá)的前k批物料需要滿足第k+1批物料到達(dá)之前的生產(chǎn)需求,同時(shí),當(dāng)?shù)趉批物料到達(dá)時(shí),總物料數(shù)量應(yīng)小于最大庫(kù)存。
準(zhǔn)時(shí)物料配送問(wèn)題屬于多目標(biāo)多約束優(yōu)化問(wèn)題,目前許多啟發(fā)式算法在解決多目標(biāo)多約束優(yōu)化問(wèn)題時(shí)都有一定的局限性,如模擬退火算法和遺傳算法進(jìn)行求解時(shí)收斂速度慢,粒子群算法收斂能力差,易早熟[9-11]。因此,采用將三者相結(jié)合的混合PSO算法對(duì)該問(wèn)題進(jìn)行求解,即基于PSO算法的進(jìn)化方式,借鑒遺傳算法的編碼方式,同時(shí)將Metropolis準(zhǔn)則融入到PSO算法中,以計(jì)算全局最優(yōu)位置,其算法流程如圖1所示。
圖1 混合PSO算法流程圖
為了使決策者可以對(duì)運(yùn)輸成本、運(yùn)輸時(shí)間和線旁庫(kù)存的權(quán)重有不同的側(cè)重,本文利用綜合判斷先行加權(quán)平均模型進(jìn)行評(píng)價(jià),由于優(yōu)化目標(biāo)中的運(yùn)輸成本Γ、運(yùn)輸時(shí)間T和線旁庫(kù)存M要求最小化,因此,根據(jù)準(zhǔn)時(shí)物料配送模型的優(yōu)化目標(biāo)函數(shù)確定的優(yōu)化算法的適應(yīng)度函數(shù)為
個(gè)體x代表一個(gè)可行解(即被選方案),Γmin、Mmin、Tmin分別為遺傳算法中每一代的運(yùn)輸成本Γ的最小適應(yīng)度值、線旁庫(kù)存M的最小適應(yīng)度值和運(yùn)輸時(shí)間T的最小適應(yīng)度值。
由于最終得到的配送結(jié)果集是關(guān)于配送零件、數(shù)量、所至工位、配送時(shí)間以及配送車輛的集合,所以優(yōu)化算法配送的粒子可采用關(guān)聯(lián)矩陣的方式表示為
式(12)、式(13)、式(14)分別表示第1次、第2次和第s次配送的粒子,其中,式(12)中的T(1)為第1次物料配送到達(dá)的時(shí)間,N11為運(yùn)送至第一個(gè)工位的第一種零件數(shù)量,E11為將第一種零件運(yùn)送至第一個(gè)工位的車輛數(shù),以此類推。
考慮到對(duì)于不可行解的處理需要一定的開(kāi)銷,所以這里設(shè)計(jì)的交叉策略采用較多的約束條件以盡量避免產(chǎn)生不可行解,提高算法效率。采取兩點(diǎn)交叉策略,即隨機(jī)確定個(gè)體最優(yōu)解Pi或者全局最優(yōu)解Pg中的某一段,將此段復(fù)制到要交叉的粒子中。以單次配送矩陣為單位,隨機(jī)選擇從第x次到第y次的z個(gè)配送矩陣,即z=y(tǒng)-x+1(y≥x,且x≥1,y≤s),其中s為待交叉粒子的總配送次數(shù)。選取z個(gè)配送矩陣后,為保證交叉后的粒子為可行解,首先將待交叉粒子中的第x次到第y次配送的矩陣替換為復(fù)制段,然后參考初始種群的產(chǎn)生方法,調(diào)整待交叉粒子的其余配送矩陣,使其滿足各約束條件后成為可行解。
變異算子采取變異全局最優(yōu)解Pg的方法,即以一定概率將Pg中所有數(shù)字交換位置,進(jìn)行重新排序。這個(gè)概率即為混合粒子群算法的變異率,即每次變異操作前生成一個(gè)隨機(jī)數(shù),當(dāng)該數(shù)小于變異率時(shí),對(duì)Pg采取變異操作,而當(dāng)該數(shù)大于變異率時(shí),不采取變異操作。經(jīng)過(guò)變異的粒子必須為可行解,因此,采取隨機(jī)生成一個(gè)新的初始粒子來(lái)代替Pg的方式。實(shí)驗(yàn)證明,該方法簡(jiǎn)便可行。
以某總裝線中的某4個(gè)工位為例驗(yàn)證本文所述的準(zhǔn)時(shí)物料配送方法,該裝配線用于生產(chǎn)型號(hào)為MF70B3的變速箱。產(chǎn)品-零件結(jié)構(gòu)BOM、工位-物料最大庫(kù)存以及工位-物料原始庫(kù)存如表1所示。某日生產(chǎn)計(jì)劃為150臺(tái),生產(chǎn)節(jié)拍為100s。用參考物流當(dāng)量[12]的計(jì)算方法轉(zhuǎn)換的標(biāo)準(zhǔn)零件的系數(shù)矩陣為U=[0.1 0.1 0.2 0.3 0.25 0.8 1 0.02 0.14 0.28 0.4 0.25 0.4 0.125 0.125 0.1 0.38 0.25 0.24 0.28 0.31]。車間有3臺(tái)運(yùn)輸設(shè)備用于該裝配線的物料配送,標(biāo)準(zhǔn)運(yùn)力分別為35、25和20。每臺(tái)運(yùn)輸設(shè)備每次的啟動(dòng)成本分別為5元、4元和3元,運(yùn)輸單位標(biāo)準(zhǔn)零件的可變成本分別為每件0.1元、0.15元和0元。
根據(jù)以上數(shù)據(jù),使用MATLAB 7.0編寫(xiě)仿真實(shí)驗(yàn)程序,優(yōu)化參數(shù)分別為:初始粒子群數(shù)量20,循環(huán)迭代次數(shù)100,變異率0.35。計(jì)算Γ、M、T權(quán)重分別為0.2、0.7、0.1時(shí)的解集,并與遺傳算法進(jìn)行對(duì)比。遺傳算法的參數(shù)取為:初始染色體數(shù)20,迭代次數(shù)100,變異率0.02。在內(nèi)存為512MB,CPU為2.4GHz、磁盤(pán)空間為80GB的同一臺(tái)計(jì)算機(jī)上用混合PSO算法計(jì)算的平均時(shí)間為104s,而用遺傳算法計(jì)算的平均時(shí)間為409s?;旌螾SO算法計(jì)算的配送成本Γ=300,配送時(shí)間T=116(以生產(chǎn)節(jié)拍為單位),線旁庫(kù)存M=309;而遺傳算法計(jì)算的結(jié)果為:配送成本Γ=321、配送時(shí)間T=145、線旁庫(kù)存M=394。結(jié)果表明,混合PSO算法的解優(yōu)于遺傳算法的解,且計(jì)算時(shí)間較短。
表1 工位-零件的BOM/最大庫(kù)存/原始庫(kù)存
圖2所示為混合PSO算法和遺傳算法計(jì)算結(jié)果對(duì)比。限于篇幅,僅列出了混合PSO算法結(jié)果的前4次物料配送矩陣,如表2所示。
圖2 混合PSO算法與遺傳算法的收斂對(duì)比
表3所示為Γ、T、M 權(quán)重分別為1時(shí)的解集,從表中可以看出,當(dāng)Γ、T、M 權(quán)重分別為1時(shí),雖然配送成本、配送時(shí)間、線旁庫(kù)存分別達(dá)到最優(yōu),但另外兩個(gè)目標(biāo)卻未達(dá)到最優(yōu)化。因此實(shí)際應(yīng)用中,決策者可以根據(jù)不同的權(quán)重選擇來(lái)獲得不同的解集,從中選擇一個(gè)合適的解作為物料配送指導(dǎo)單的最終結(jié)果。
表2 物料配送矩陣
表3 Γ、T、M 權(quán)重分別為1時(shí)的解集
(1)本文提出的多目標(biāo)準(zhǔn)時(shí)物料配送方法,變被動(dòng)配送為主動(dòng)配送,同時(shí)兼顧整個(gè)配送過(guò)程的時(shí)間效應(yīng)與經(jīng)濟(jì)效益,適合機(jī)械產(chǎn)品總裝車間的物料配送。
(2)采用綜合評(píng)判線性加權(quán)模型解決多目標(biāo)優(yōu)化問(wèn)題中的權(quán)重選擇問(wèn)題,使決策者能根據(jù)實(shí)際情況選擇配送過(guò)程優(yōu)化目標(biāo)的偏好值,滿足JIT生產(chǎn)模式下機(jī)械產(chǎn)品裝配過(guò)程對(duì)準(zhǔn)時(shí)物料配送的要求。
[1] Lai C L,Lee W B,Ip W H.A Study of System Dynamics in Just-in-time Logistics[J].Journal of Materials Processing Technology,2003,138:265-269.
[2] Al-Tahat D M,Mukattash A M.Design and Analysis of Production Control Scheme for Kanbanbased JIT Environment[J].Journal of the Franklin Institute,2006,343:521-531.
[3] Li Jingshan,Blumenfeld D E.Analysis of Andon Type Transfer Production Lines:a Quantitative Approach.Proceedings[C]//IEEE International Conference on Robotics and Automation.Barcelona,Spain,2005:278-283.
[4] Cao Zhenxin,Zhu Yunlong.Research on Material Feeding and Its Implementation in General Assembly Line of Mixed Model Automobile[J].Computer Inte-grated Manufacturing Systems,2006,12:285-291.
[5] Choi W,Le Y.A Dynamic Part-feeding System for an Automotive Assembly Line[J].Computers &Industrial Engineering,2002,43:123-134.
[6] 呂利勇,王田苗,肖修劍.基于配送BOM的拉動(dòng)式生產(chǎn)方法研究[J].組合機(jī)床與自動(dòng)化加工技術(shù),2002(11):29-31.
[7] 李喆.基于MES的注塑生產(chǎn)過(guò)程實(shí)時(shí)物料配送系統(tǒng)的研究與實(shí)現(xiàn)[D].廣州:廣東工業(yè)大學(xué),2007.
[8] 徐建萍,郭鋼.基于工藝流程的物料配送BOM模型[J].重慶大學(xué)學(xué)報(bào),2005,28(6):19-21.
[9] 劉明周,張明偉,蔣增強(qiáng),等.基于混合粒子群算法的多目標(biāo)柔性Job-Shop調(diào)度方法[J].農(nóng)業(yè)機(jī)械學(xué)報(bào),2008,39(5):122-127.
[10] Wei Zhong,Xu Xiaofei,Deng Shengchun.Evolutionary Algorithm for Solving Multi-objective Hybrid Flow-shops Scheduling Problem[J].Computer Integrated Manufacturing Systems,2006,12(8):1227-1233.
[11] Wu Xiuli,Sun Shudong,Yu Jianjun.Research on Multi-objective Optimization for Flexible Job Shop Scheduling[J].Computer Integrated Manufacturing Systems,2006,12(5):731-736.
[12] 李云.混合裝配流水線物流系統(tǒng)的優(yōu)化與仿真[D].上海:上海大學(xué),2004.
Research on Multi-objective Method on Main Assembly Material Delivery Based on JIT
Ge Maogen Liu Mingzhou Qian Fang Hu Jing Jiang Zengqiang Zhang Mingxin
Hefei University of Technology,Hefei,230009
To solving the real-time material delivery problems during the assembly process of mechanical products,a multi-objective real-time materials distribution model was proposed considering from optimization objectives,constraints and impact factors,which integrated materials transportation costs,materials transportation time and materials storage on-line as optimization target.The calculation method of optimization objectives was given,a hybrid particle swarm algorithm was designed and the detail realization process with this algorithm was presented.Then distribution bills were gained,which used to guide materials distribution,and the overall objective optimization will be achieved,the decision-makers choose the preferred solution of optimization objectives according to the facts.Finally,the validity of this model and algorithm was verified by a case of assembly plant materials distribution problem.
real-time material delivery;multi-objective;just-in-time(JIT);hybrid particle swarm optimization
TH18;TP391
1004—132X(2011)23—2834—05
2011—01—07
國(guó)家自然科學(xué)基金資助項(xiàng)目(71071046)
(編輯 何成根)
葛茂根,男,1979年生。合肥工業(yè)大學(xué)機(jī)械與汽車工程學(xué)院講師、博士研究生。主要研究方向?yàn)橄到y(tǒng)建模與仿真、CIMS。劉明周,男,1968年生。合肥工業(yè)大學(xué)機(jī)械與汽車工程學(xué)院教授、博士研究生導(dǎo)師。錢(qián) 芳,女,1987年生。合肥工業(yè)大學(xué)機(jī)械與汽車工程學(xué)院碩士研究生。扈 靜,女,1976年。合肥工業(yè)大學(xué)機(jī)械與汽車工程學(xué)院博士研究生。蔣增強(qiáng),男,1979年生。合肥工業(yè)大學(xué)機(jī)械與汽車工程學(xué)院副教授、博士。張銘鑫,男,1980年生。合肥工業(yè)大學(xué)機(jī)械與汽車工程學(xué)院講師、博士研究生。