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

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

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

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

6040M3W35MMSW55MM4W3JDM4W5IDM3W3BUKMJW5SUKMZWSVSMJWlflVSW2W6KM2W9GKB6040M3W35MMSW55MM4W3JDM4W5IDM3W3BUKMJW5SUKMZWSVSMJWlflVSW2W6KM2W9GKBMPWIBMV1TPSVaPWJVIV■PWSV■PWMSV圖8最大完工時間優先規則表現的良好的模型可變性是振奮人心的。