混合裝配線平衡問題的啟發(fā)式過程

混合裝配線平衡問題的啟發(fā)式過程摘要：為了迎合高的定制要求，混合裝配線是迫切需要的。該類生產(chǎn)線以混合序列生產(chǎn)多種模型。設(shè)計(jì)一套裝配線應(yīng)包括其平衡過程研究：工作元素向工作站的分配。即使對(duì)于單一模式裝配線而言，裝配線平衡問題仍是NP難題（非多項(xiàng)式算法問題）因此啟發(fā)式過程常用來避免棘手的多維問題。有效的啟發(fā)式是解決平衡混合生產(chǎn)線的便利方法，因?yàn)樵诂F(xiàn)實(shí)生活中，可行解決方案的檢索一般是可以滿足要求的。本文提出了7種優(yōu)先規(guī)則，它可以與一個(gè)面向解決第二類混裝線平衡問題（工作站數(shù)量已知（type-II））的工作站關(guān)聯(lián)使用。優(yōu)先規(guī)則和面向啟發(fā)式工作站是基于這樣一種理論：即僅僅最小化循環(huán)時(shí)間并不是混裝線的全部目標(biāo)。關(guān)鍵詞：混裝線，第二類平衡問題，啟發(fā)式工作站一、簡(jiǎn)介單一的裝配線已經(jīng)不能適應(yīng)客戶不斷提升的期望和為了滿足大量客制化需求而進(jìn)行的工業(yè)產(chǎn)能平行化。有多變種的模型可以吸引足夠的客戶以達(dá)到裝配系統(tǒng)的盈利使用。變種一般僅僅是特殊定制的模型屬性不同而都是同一模型平臺(tái)的衍生物。兩種模型的準(zhǔn)備時(shí)間很小可以忽略，最終這些模型可以安排在同一生產(chǎn)線混流裝配。設(shè)計(jì)裝配線要考慮平衡過程，也就是工作元素向工作站的分配。裝配線常用的目標(biāo)函數(shù)為利用率的最大化。通過在給定的循環(huán)時(shí)間內(nèi)最小少工作站數(shù)目（type-I）或者在工作站給定的情況下使循環(huán)時(shí)間最小化（type-II）0不能將最小化循環(huán)時(shí)間（或工作站數(shù)量）當(dāng)作混裝條件下的唯一目標(biāo)。阻塞和空閑：因不同模型到達(dá)生產(chǎn)線而造成（在工作站中裝配時(shí)間各不相同）；使得準(zhǔn)確評(píng)估裝配線的吞吐量變得非常困難。工作站耗時(shí)嚴(yán)重依賴于所裝配的不同模型，這會(huì)引起相應(yīng)的短期混流排序問題（MSP）。因?yàn)镸SP問題，人們要找到模型單元的投送順序，以滿足短期計(jì)劃周期的模型流程所給定的要求，并優(yōu)化某些目標(biāo)。這些目標(biāo)主要針對(duì)的是因多種模型的站內(nèi)時(shí)間不同而造成的效率低下問題?；旌涎b配線平衡問題和排序問題（MSP）相互依存。一些學(xué)者建議同事考慮這兩個(gè)問題。但是，這些問題通常源于不同的訂單，有著特定的不同數(shù)據(jù)，因此排序問題會(huì)因每個(gè)訂單、每天、每周的不同而出現(xiàn)。同時(shí)優(yōu)化一般是不可行的，如它們通常會(huì)有完全不同的時(shí)間框架。在更高的平衡水平上使用分層計(jì)劃方法來預(yù)測(cè)排序結(jié)果看起來更加有意義。平衡化階段的可變性目標(biāo)已在文獻(xiàn)【2,3,9,10】中提出，以減少在分層計(jì)劃方法中安排排序所遇到的困難。值得注意的另一個(gè)問題是，在JIT條件下，混裝線要滿足不斷變化的動(dòng)態(tài)要求。所以，JIT條件下裝配線的設(shè)計(jì)過程不強(qiáng)調(diào)排序問題，其主要研究對(duì)象是平衡問題。目前一些企業(yè)中的現(xiàn)有裝配線需要解決方法，而這些方法不應(yīng)是減少現(xiàn)有工作站，甚至當(dāng)設(shè)備造價(jià)昂貴時(shí)還不得不增加工作站。方法本文致力于開發(fā)簡(jiǎn)單的啟發(fā)式而非構(gòu)造數(shù)學(xué)模型并以優(yōu)化技術(shù)來解決問題。由于裝配線平衡問題是NP難題，啟發(fā)式過程通常用以避免維數(shù)問題，通過構(gòu)建單一可行解。所以，是單一平衡?？焖俑咝У膯l(fā)式對(duì)于裝配線平衡是有效的工具，因?yàn)橐粋€(gè)可行解關(guān)注于所給工作站的數(shù)量和循環(huán)時(shí)間，在現(xiàn)實(shí)中，它的獲取一般較容易。Gumussoy和Kabak研究了最優(yōu)解的應(yīng)用問題，這些最優(yōu)解可以通過啟發(fā)式方法來解決實(shí)際ALB問題，如RankedPositionalWeight（RPW）。參考工業(yè)實(shí)例，他們?cè)谡撐闹兄赋?，一些最?yōu)解的尋找方法根本不能解決問題，如二進(jìn)制公式和最短路徑公式。一種解決MALBP的方法是:繪制一個(gè)應(yīng)用于所有模型及其平均任務(wù)次數(shù)的公用優(yōu)先級(jí)圖,以獲得等效的單模型問題。這種從混合模型數(shù)據(jù)到單一平均模型數(shù)據(jù)的簡(jiǎn)單轉(zhuǎn)化，確保了循環(huán)時(shí)間對(duì)于完成所有模型是足夠的。但是，即使使用了平均模型的最優(yōu)解，在實(shí)際的裝配線操作過程中無疑會(huì)產(chǎn)生效率低下的問題。本文中，盡管公用的優(yōu)先級(jí)圖用于定義所有優(yōu)先級(jí)關(guān)系，但是當(dāng)且僅當(dāng)個(gè)體模型的任務(wù)次數(shù)少于或等于工作站中對(duì)應(yīng)模型的可用時(shí)間時(shí)，才向工作站中分配任務(wù)。這種與簡(jiǎn)單地平均任務(wù)時(shí)間在方法上的差異，用于量化整條裝配線在平衡階段自身的效率低下問題，從而啟發(fā)式過程可以試著消除，至少是減少這樣的效率低下問題。起初，工作站對(duì)于每個(gè)模型的可用時(shí)間被當(dāng)做循環(huán)時(shí)間。工作站可用時(shí)間用一個(gè)行向量表示，其各列的數(shù)值與模型數(shù)相同。任務(wù)分配之后，用于進(jìn)一步分配的可用時(shí)間（工作站中，對(duì)于每個(gè)模型的），將通過從工作站可用時(shí)間中減去模型任務(wù)時(shí)間計(jì)算得出。A.面向啟發(fā)式的工作站第一步：輸入工作站數(shù)（Nw）,模型數(shù)（Nm）,所有模型的所有任務(wù)時(shí)間，以及任務(wù)優(yōu)先關(guān)系。第二步:設(shè)定循環(huán)時(shí)間，作為所有模型理論最小循環(huán)時(shí)間的最大值。第三步:分配循環(huán)時(shí)間值，作為所有工作站的可用時(shí)間。第四步:打開1號(hào)工作站，分配任務(wù)。第五步:找到可分配的任務(wù)?？煞峙涞娜蝿?wù)都應(yīng)有前續(xù)工作站，并且其所有任務(wù)時(shí)間應(yīng)小于工作站相應(yīng)模型的可用時(shí)間。第六步：令可分配的任務(wù)編號(hào)為Na。如Na=0,貝I」：如果現(xiàn)有工作站數(shù)位Nw,或現(xiàn)有工作站的單個(gè)模型的累積空閑時(shí)間多于相應(yīng)模型的允許空閑時(shí)間，貝舍棄所有任務(wù)分配，循環(huán)時(shí)間增量1，返回第三步。否貝，開啟下一工作站并分配，到第五步。如Na=1，向現(xiàn)有工作站中分配任務(wù)。如Na〉l，將可分配的任務(wù)根據(jù)所用的優(yōu)先級(jí)規(guī)則按照升序/降序排列，并將列表中的第一個(gè)任務(wù)分配給當(dāng)前工作站。第七步：從上一步的可用時(shí)間中減去已分配了的任務(wù)中所有模型的任務(wù)時(shí)間，得到新的可用時(shí)間。重復(fù)5-7步，直到所有任務(wù)分配到給出的工作站中。B.優(yōu)先級(jí)上述的啟發(fā)式過程使用優(yōu)先級(jí)來構(gòu)建操作順序，根據(jù)該順序向工作站中分配操作。僅僅最小化循環(huán)時(shí)間不能作為MALBP-II的有效目標(biāo)，因?yàn)楣ぷ髡镜钠交ぷ鞣峙涓又匾Ｒ虼?，本文中的?yōu)先級(jí)利用循環(huán)時(shí)間、模型多樣性、工作站多樣性，或者是三種操作對(duì)象的結(jié)合來指導(dǎo)啟發(fā)式過程。處理裝配時(shí)間多樣的Bottleneck法也可以考慮來構(gòu)建優(yōu)先級(jí)規(guī)則。第一優(yōu)先級(jí)規(guī)則，即MeanPositionalWeight(MPW)規(guī)則是一種改進(jìn)RankedPositionalWeight(RPW)規(guī)貝I」。RPW用于解決混流ALB問題，但須通過平均模型任務(wù)時(shí)間，將他們轉(zhuǎn)化為等效的單一模型問題。第二優(yōu)先級(jí)規(guī)則是BaseModelVariability(BMV),旨在最小化模型多樣性。BMV基于邏輯學(xué)，如果混裝線上的個(gè)體問題可以近似地平衡為他們各自的最優(yōu)循環(huán)時(shí)間，那么MALBP的解可作為一條裝配線的解。第三條規(guī)則基于工作站的工位多樣性來優(yōu)先化任務(wù)，根據(jù)該工作站的分配任務(wù)，叫做TaskPrioritizationusingStationVariability(TPSV)0第四條規(guī)則綜合了MPW和BMV，第五條規(guī)則綜合了MPW和TPSV，而第六條規(guī)則融合了這三類方法。第七條優(yōu)先級(jí)規(guī)則是改進(jìn)型Bottleneck方法。Bottleneck方法由Bukchin提出，他同時(shí)指出該方法在混流條件下等效仿真裝配線方面要優(yōu)于其他方法。值得注意的是，他并沒有使用Bottleneck法來獲取平衡解方案，而是等效仿真混裝線的流程。Bukchin也在三段式平衡啟發(fā)式中應(yīng)用該方法，但僅針對(duì)基于臨近搜索的方案改進(jìn)過程。本文中，我們嘗試改進(jìn)Bottleneck方法，以適應(yīng)任務(wù)的優(yōu)先級(jí)，并將其命名為BottleneckPriorityRule(BPR)。本方法的新穎之處是利用模型可變性，工位可變性和瓶頸方法當(dāng)做優(yōu)先級(jí)規(guī)則。據(jù)我們所知，這是第一次在啟發(fā)式中利用它們作為優(yōu)先級(jí)規(guī)則來獲取平衡方案。但是，應(yīng)該注意到，該優(yōu)先級(jí)規(guī)則是從早期的方法中派生出來的。下面是優(yōu)先級(jí)的描述：Nw工作站數(shù)量Nm模型數(shù)量Ntk任務(wù)總數(shù)ntk任務(wù)時(shí)間非零的模型數(shù)t,，m模型m的'tk'任務(wù)時(shí)間tkStk任務(wù)'tk'的所有后續(xù)任務(wù)集tkTwm在工作站'w'中的模型'm'的站內(nèi)時(shí)間T,(平均)工作站'w'的平均站內(nèi)時(shí)間。wm'

Tm模型'm'的理論最小循環(huán)時(shí)間。Tmcw已分配任務(wù)的當(dāng)前工作站XN'X'的規(guī)范化值B1.MeanpositionalWeight（MPW）在有相關(guān)任務(wù)分配的模型中，對(duì)于每個(gè)模型來說，一項(xiàng)任務(wù)的位置權(quán)重會(huì)單獨(dú)計(jì)算出來，然后除以模型數(shù)量得到平均值，有關(guān)的任務(wù)會(huì)呈現(xiàn)在這里。對(duì)于沒有相關(guān)任務(wù)的某個(gè)模型'm'任務(wù)的位置權(quán)重置零。對(duì)于沒有任務(wù)的模型'm'，位置權(quán)重看作0.然后將任務(wù)的MPW規(guī)范值取為：然后將任務(wù)的MPW規(guī)范值取為：將任務(wù)按照其規(guī)范化的MPW值降序排列。B2.BaseModelVariability（BMV）任務(wù)的BMV作為所有單個(gè)模型可變性數(shù)值的最大值。單個(gè)模型可變性數(shù)值這樣算出:'M'模型的所有站內(nèi)時(shí)間與理論最小循環(huán)時(shí)間的平方差。T包括任務(wù)’tk'的任務(wù)時(shí)間。任務(wù)wm根據(jù)規(guī)范化BMV數(shù)值升序排列。BMVtkmax（cw / 、BMVtkmax（cw / 、心 / 「ISMVj二B3.TaskPrioritizationusingStationVariability（TPSV）站的變化值被當(dāng)做當(dāng)前工作站站內(nèi)時(shí)間的標(biāo)準(zhǔn)偏差，而任務(wù)tk'正考慮分配入該工作站。而且，Twm包括任務(wù)'tk'的任務(wù)次數(shù)。TPSVtkITPSVtkITPSV值同樣被規(guī)范化并以升序排列來確定任務(wù)優(yōu)先級(jí)。B4.MPW結(jié)合BMV(PWMV)PWMVt?= MPW.?-BMVtkxB5.MPW結(jié)合TPSV(PWSV)卩wsv/ = M卩w/-TPSVtkNB6.MPW結(jié)合BMV和TPSV(PWMSV)卩WMSVtky=NIPWj-BMVt/-TPSVtkx按照B4—B6的優(yōu)先級(jí)規(guī)則，以降序?qū)θ蝿?wù)進(jìn)行排列。B7.基于Bukchin的公式，可以定義TBD(timebetweendepartures)的預(yù)期時(shí)間:E(TBD)=工工円(幾麗i血巒曲曲時(shí)忖咖任務(wù)按照他們的規(guī)范化E(TBD)值以升序排列，這些數(shù)值可認(rèn)為是所以模型的平均循環(huán)時(shí)間。三、實(shí)例為了評(píng)估面向啟發(fā)式和優(yōu)先級(jí)規(guī)則的工作站的應(yīng)用情況，引入一個(gè)包括十個(gè)問題的數(shù)據(jù)集。圖1-4的聯(lián)合優(yōu)先圖表示了使用從文獻(xiàn)【16】【1】【15】【17】【11】中得到任務(wù)次數(shù)和優(yōu)先關(guān)系數(shù)據(jù)的這些問題。盡管【16】和【1】的聯(lián)合優(yōu)先圖的數(shù)據(jù)相同，但是模型的數(shù)量不同，這使得它們是不同的兩個(gè)問題。工作站數(shù)量的兩個(gè)不同數(shù)值引入到上述五個(gè)問題實(shí)例中。Table1列舉了十個(gè)問題:

Tabl-e1MALBPINSTANCESProblemInstanceProblemNomenckitiireJointPrecedemc-eDiagramNumberofStations1M3W3SMFig.132M3W5SMFig.153M4W3JDFig13斗M4W5JDFig.155M3W3BUKFig.236M3W5BUKFig.257M2WSVSFig.3$SM2W10VSFig.3109M2W7GKF墀4710M2W9GK.Fig.49四、結(jié)果和結(jié)論圖一：實(shí)例1-4的聯(lián)合優(yōu)先圖圖二：For實(shí)例5和6圖三：For實(shí)例7和8圖四：For實(shí)例9和10I)1$圖四：For實(shí)例9和10I)1$1?:B?l1012圖5-8表示4個(gè)目標(biāo)，即循環(huán)時(shí)間，模型多樣化，工作站多樣化和最大完工時(shí)間。每一個(gè)最大完工時(shí)間的獲得是通過選擇啟動(dòng)模型的最佳序列。循環(huán)時(shí)間的顯示結(jié)果表明，基于位置權(quán)重或位置權(quán)重與模型可變、工作站可變結(jié)合的優(yōu)先級(jí)規(guī)則，比單獨(dú)基于模型或工作站可變、瓶頸方法表現(xiàn)的更好°BPR在循環(huán)時(shí)間和模型可變方面表現(xiàn)更差，但是與其他優(yōu)先規(guī)則相比，它在最大完工時(shí)間方面是可作為參考的，在某些實(shí)例中甚至更好。?MPW■BMV■TPSV■PWMV■PWSV-PWMSVBPR圖5循環(huán)時(shí)間

UdQASIAIMd■ASAAdVAlAIMdBASdLBAIA19■ 旳?^d8ASIAIMd■ASAfld■AlAIMdBASdLBAIA19■AAdt/M■

6040M3W35MMSW55MM4W3JDM4W5IDM3W3BUKMJW5SUKMZWSVSMJWlflVSW2W6KM2W9GKB6040M3W35MMSW55MM4W3JDM4W5IDM3W3BUKMJW5SUKMZWSVSMJWlflVSW2W6KM2W9GKBMPWIBMV1TPSVaPWJVIV■PWSV■PWMSV圖8最大完工時(shí)間優(yōu)先規(guī)則表現(xiàn)的良好的模型可變性是振奮人心的。