生產(chǎn)線平衡外文翻譯

1、螞蟻算法在時間和空間約束的裝配線平衡問題中的應(yīng)用摘要本文重點研究基于蟻群算法解決裝配線平衡問題的一個程序中的應(yīng)用。在裝配線問題的介紹之后，在研究中提出的問題是：時間和空間約束的裝配線平衡問題（TSALBP）；同時對它的一個變體的基本模型提出了研究。隨后，螞蟻算法對一些簡單的平衡問題提供了良好的結(jié)果。最后，本文提出的算法的有效性是通過參考實例計算測試，印證了本研究的結(jié)論。關(guān)鍵詞人工智能；制造；算法；生產(chǎn)1 簡介裝配線是由個工作站通過串聯(lián)和并聯(lián)排列貫穿整個產(chǎn)品流程。各個工作站被物流系統(tǒng)鏈接起來，物流系統(tǒng)其任務(wù)是供應(yīng)原材料和半成品從一個站到下一個站的流動。生產(chǎn)項目可以是一種類型（單模）或幾種類型（混

2、模）。一個生產(chǎn)項目的生產(chǎn)任務(wù)可以看成是由個任務(wù)組成的集合；工作站被分配的任務(wù)是的一個子集；任務(wù)只能分配給某一個工作站。每個任務(wù)需要一個運行時間,這由制造技術(shù)和人力資源決定。混模裝配線，它通常由單模的運行時間依據(jù)各模權(quán)重進行估算。如果不同模型之間運行時間差別較大，單位必須相當(dāng)。此外，每個工作任務(wù)都有前置任務(wù)，必須在任務(wù)之前完成。這些限制通常是由一個存在優(yōu)先級的非循環(huán)圖表示，其中每個從到的向弧表示任務(wù)必須在開始任務(wù)之前完成；因此，如果和，那么必須滿足。每個工作站任務(wù)的持續(xù)時間的總和用表示。一旦永久制造條件已達(dá)到，生產(chǎn)項目沿裝配線線以恒定的速率流動，工作站存在周期時間以完成分配給它的任務(wù)。在汽車裝配

3、線，項目通常分配給每個工作站一定的空間在一段時間內(nèi)來完成相應(yīng)的任務(wù)可以看做是一個循環(huán)。該項目以極短的時間傳送到下一工作站，從而引發(fā)新循環(huán)。周期時間決定裝配線的生產(chǎn)速率，同時不能小于最大工作站運行時間：，也不應(yīng)大于總生產(chǎn)任務(wù)的持續(xù)時間的總和：。每個站空閑時間。這些空閑時間的總和，這和該裝配線的無效率有關(guān)。在一般情況下，ALBP（裝配線平衡問題）致力于使的的各項任務(wù)有效率且條理分明地完成。總之，我們的目標(biāo)是實現(xiàn)一個分組的任務(wù)，最大限度地減少裝配線停機時間和尊重任務(wù)自身的強制約。ALBP屬于一般類排序問題（Baker，1974），可視為有額外約束的裝箱問題。這些優(yōu)先約束建立箱隱秩序，導(dǎo)出操作序列。第

4、一類問題，被稱為SALBP（簡單裝配線平衡問題）（Baybars，1986），可按下列方式表示：給定一組個任務(wù)的屬性和優(yōu)先級表格，每個任務(wù)必須被分配某個工作站，滿足所有的優(yōu)先約束，并且沒有工作時間大于周期時間的情況。SALBP存在4個變種：SALBP-1：減少工作站的數(shù)量給出了一個固定值的周期時間；SALBP-2：減少周期時間（最大限度地提升生產(chǎn)速率R）給出了一個固定的站數(shù)；SALBP-E：同時減少和考慮總空閑時間；SALBP-F：給定和，確定問題的可行性，如果它是可行的，找到一個解決方案。當(dāng)其他因素被添加到SALBP類問題，在文獻(xiàn)中已知的GALBP（一般的裝配線平衡問題）。這類問題包括這些問

5、題與額外的約束，如平行站的考慮，Daganzo和Blumfield（1994）和Vilarinho 和 Simaria（2002），對任務(wù)強制分組，Deckro（1989）任務(wù)之間的不兼容，Agnetis等人（1995）以及工作站之間的差異Nico等人（2002）。關(guān)于解決問題的程序，這些文獻(xiàn)包括很多。第一組的算法被稱為“貪婪”算法，它是基于優(yōu)先級的規(guī)則或部分枚舉程序；見Talbot等人（1986）以及最近Fleszar和Hindi（2003）。第二組是由枚舉程序組成，基本上在一個分支定界范式，Johnson（1988），Hoffmann（1992），Scholl和Klein（1999），Sp

6、rencher（2003），目前是最有效的。第三組由多樣式啟發(fā)式的方法組成（參見Scholl和Voss（1996）。幾乎所有這些研究集中在SALBP-1和SALBP-2問題的解決；因此，特定的程序必須采用在解決一個問題，包括與尊重差異表示模型。本文的組織如下。第二部分提出在汽車行業(yè)的問題，包括額外的限制，和裝配線周圍可用空間相關(guān)；提出了數(shù)學(xué)公式，建立了SALBP的關(guān)系。在第三部分，一種由Dorigo（1996）等人提出的的蟻群算法，作為啟發(fā)式地解決問題。該算法融合了其他的啟發(fā)式原理，對平衡問題有很好的結(jié)果。第四部分論述了集合參考的情況下，適應(yīng)新的問題的一種計算經(jīng)驗。最后，本研究的主要結(jié)論在第五

7、部分。2 時間和空間約束的裝配線平衡問題2.1 空間約束的裝配線平衡在一個由數(shù)個分枝制造或裝配線組成的生產(chǎn)系統(tǒng)，生產(chǎn)線的平衡是一個常見的問題。在汽車行業(yè)，常使用相同的線的裝配各種零件（如底盤，車體，座位，等）。需要的是在不同的情況下，即使只是暫時性的平衡。如果一個已經(jīng)存在的裝置限制了規(guī)定的材料和制造及裝配工具的空間也必須考慮。一些以空間考慮常見的原因有：工作站的長度是有限的。當(dāng)產(chǎn)品沿著生產(chǎn)線以恒定的速率，如使用傳送帶，工人開始工作盡量靠近工作站的初始點，必須跟隨產(chǎn)品完成任務(wù)。當(dāng)產(chǎn)品在工作站定期轉(zhuǎn)移到下面的工作站，在每個周期時間，工人需要工具和材料組裝產(chǎn)品。在這兩種情況下，工人的最大可移動限制了

8、工作站的長度以及可用空間。所需要組裝的的工具和配件應(yīng)沿生產(chǎn)線兩側(cè)分布。盡量的使他們和工作地保持近距離，以及避免材料雙線。除了這些常見的約束，在汽車行業(yè)，一些操作只能在線路的一側(cè)執(zhí)行，物理空間條件作用限制了工具和材料的分派。最后，幾個貨柜要求是非常大的，以減少投遞次數(shù)或是由于配件的專業(yè)特性，如前座和后座。如果需要供應(yīng)大區(qū)的幾個任務(wù)都放在一起，這樣是難以實施的?；炷Ｑb配線的空間約束更重要。這通常在汽車行業(yè)。在求解平衡有關(guān)的問題，它是通常利用任務(wù)的加權(quán)時間，由于每個工作站都需要相關(guān)的變型產(chǎn)品的組件和工具來組裝產(chǎn)品，故工作站分配的空間需要增加。另一種常見空間限制來自于產(chǎn)品的變化。當(dāng)一個汽車模型更替為新

9、的，通常是保持相同的生產(chǎn)布置。生產(chǎn)布置設(shè)計通常考慮到原有的模型，但是當(dāng)它是由一個較大的模型或更豐富的模型組件取代，在生產(chǎn)布置的額外空間要求將產(chǎn)生空間約束。這一空間的局限性可能是通過與每個任務(wù)所需的面積 (周期時間，產(chǎn)量和材料的供應(yīng)率的相關(guān)函數(shù)）相關(guān)聯(lián)，每個站可用面積（和布局的函數(shù)），簡單來看，我們假設(shè)所有站是相同的為：。每個站需要一個工作面積等于分配給站的任務(wù)所需的面積之和。TSALBP問題：時間和空間約束的裝配線平衡問題，可在定義如下：給定一組n個任務(wù)以及每個任務(wù)的時間和空間屬性和和優(yōu)先級表格，每個任務(wù)必須被分配到某個特定的站：（1）所有優(yōu)先滿足約束條件，（2）不大于，（3）不大于.TSAL

10、BP提出了不同的變種取決于元素, 和。在這里，我們提出八個變種TSALBP（見表1），這取決于元素, 和，作為固定值還是最優(yōu)變量。例如，TSALBP-1（相當(dāng)于SALBP-1）在最小化的站數(shù)的基礎(chǔ)上給出每一站的可用區(qū)域以及固定的周期時間，而TSALBP-F給出固定的, 和值的可行性問題。表1 TSALBP類型名稱類型TSALBP-F已知已知已知FTSALBP-1最小化已知已知OPTSALBP-2已知最小化已知OPTSALBP-3已知已知最小化OPTSALBP-1/2最小化最小化已知MOPTSALBP-1/3最小化已知最小化MOPTSALBP-2/3已知最小化最小化MOPTSALBP-1/2/3

11、最小化最小化最小化MOP后綴1，2和3分別指的是最小化, 和。如果問題是一個可行的，則類型為F；如果它是一個單目標(biāo)優(yōu)化問題，則類型為OP；如果問題是一個多目標(biāo)優(yōu)化問題，則類型為MOP。當(dāng)問題是MOP類型，后綴1，2和3用“/”連接以便命名。2.2 舉例圖1顯示了關(guān)于BOWMAN8簡單裝配線平衡問題的實例的優(yōu)先圖。實例來自http:/www.assembly-line-balancing.de。該實例有8個任務(wù)，各任務(wù)加工時間為3到17單位不等。每個任務(wù)被賦予了時間和空間的需求來顯示TSALBP案例。這兩個值出現(xiàn)在每個頂點上，第一個處理時間，第二處理面積。111/3217/10710/1758/

12、539/1545/883/11612/9給定周期時間為20，最佳的解決SALBP-1實例需要五臺以下分組的任務(wù)： 1 ， 2 ， 3，5 ， 4，6，8 ， 7 。每個工作站的加工時間都不大于周期時間，此外各個工作站的各個任務(wù)之間的優(yōu)先級也可以滿足。如果施加一個額外的空間約束，每站20個單位的空間，五個工作站沒有解決辦法。之前的解決方案工作站四不滿足面積約束，通過任務(wù) 4，6，8 組成，需要28個單位的空間?？梢钥闯觯鍌€工作站不能同時滿足兩種約束，最佳的解決方案的任務(wù)分組 1 ， 2 ， 3，5 ， 4，6 ， 7 ， 8 ，需要六個工作站。2.3 建立時間和空間約束的裝配線平衡問題數(shù)學(xué)模型

13、為了正式地描述TSALBP模型，我們采用以下附加符號：， 任務(wù)可以被指派的最先和最后的工作站UB 工作站數(shù)上限 變量：如果任務(wù)被指派給工作站，則為1；否則為0 在以上條件上，表達(dá)式（1）-（6）建立了TSALBP-1模型。 ， （1）， （2） ， （3） , （4） ， （5） . （6）等式（1）確保每個任務(wù)只被分配到一個站。不等式（2）到（4）分別確保工作量站數(shù)量不超過允許的數(shù)量，在每一站的工作時間不超過周期時間，每個站需要的面積不超過可用面積。不等式（5）保證任務(wù)間的優(yōu)先關(guān)系的實現(xiàn)。最后，約束（6）確定決策變量為二進制變量。在TSALBP-F中，元素, 和作為變量，而在其余情況下，一個

14、或多個以上這些因素作為目標(biāo)函數(shù)。表達(dá)式（7）-（9）對應(yīng)TSALBP-1，TSALBP-2，TSALBP-3各自的目標(biāo)函數(shù)。Minimize ， （7）Minimize ， （8）Minimize ， （9）在表達(dá)式（7）-（9）的基礎(chǔ)，我們很容易建立MOP類問題（TSALBP-1/2，TSALBP-1/3，TSALBP-2/3, TSALBP-1/2/3）的目標(biāo)函數(shù)。3 螞蟻算法解決TSALBP問題許多種類的螞蟻獲取食物的行為，是基于追蹤一種稱為信息素的化學(xué)物質(zhì)。給定一個食物來源，蟻群會自然地找到食物來源與巢穴之間的最短路徑，這通過兩個過程。首先，螞蟻在路徑上釋放信息素；其次，他們通常遵循能

15、找到更多先前沉積的信息素的路徑。如果他們找到了一個較短的路徑，更多的螞蟻沿著這條道路傳播，更多的信息素會沉積在這條路徑上。這種優(yōu)化適應(yīng)思想被稱為蟻群算法，它反復(fù)應(yīng)用以下三個階段：（1）由一個隨機程序解決問題（2）局部改善（3）信息素沉積以反饋信息找到新的解決方案。這一部分主要研究對蟻群算法在有時間和空間的限制的工作站應(yīng)用于裝配線平衡問題。這里提出的算法適用于蟻群系統(tǒng)（AS）范式（Dorigo等人，1996）。接下來我們詳細(xì)描述了算法的總體架構(gòu)，然后展示以上提到的螞蟻算法的三個階段。3.1 一般程序概論雖然解決類似SALBP-1的問題很簡單，但很難定義適用的局部改善的有效方法；參見Bautist

16、a 和 Pereira (2002)，一個特定的情況下，或Scholl和Voss（1996）更一般地討論這些問題。SALBP-1目標(biāo)函數(shù)的難度在于，不斷改善只能得到?jīng)]有任務(wù)的工作站，因而也沒有明顯的措施促成好的改善（見Scholl，1999）。為此，提出了一種解決方案是類似于使用禁忌搜索程序（Scholl和Voss，1996），用于SALBP-1是基于越來越嚴(yán)格的SALBP-2實例的迭代解。程序開始采用3.2節(jié)中提出的啟發(fā)式規(guī)則構(gòu)建初始解；一個有效的解決方案獲得一個工作站的數(shù)目等于。隨后，一個蟻群系統(tǒng)程序用個工作站解決TSALBP-2實例。如果解決方案得到的最大工作時間和最大工作空間等于或小于

17、原始TSALBP-1實例的給定值，找到的解決方案比已知的更好，從而減少所需的站數(shù)。這個方法可以用來再次減少工作站數(shù)，直到達(dá)到最終狀態(tài)。為了避免在空間不起眼的地區(qū)停滯，采用多元化機制接納信息素的信息，解決方案生成解的個數(shù)等于50倍的實例中的任務(wù)數(shù)量，這樣蟻群系統(tǒng)程序以相同的工作站數(shù)重啟。雖然這種迭代模式能確保局部改善算法的應(yīng)用（見3.3節(jié)），這樣的指導(dǎo)比基于TSALBP-1直接求解模式更好，初始解的產(chǎn)生更復(fù)雜。該方法迭代解決TSALBP-1實例見3.2節(jié)，直到站的給定數(shù)量達(dá)。最初，試圖為實例建立一個解決方案，該實例給定的時間和空間分別等于周期時間和可用空間。該程序提供的解決方案需要比預(yù)期的數(shù)目更

18、大的站數(shù)，周期時間和可用空間按1%或一個單位的量遞增，無論是更好的或是一個新的初始解，直到以預(yù)期的工作站數(shù)量能找到解決的辦法了。同樣地，當(dāng)以所需數(shù)量的工作站數(shù)獲得解決方案，周期時間和可用空間是相對于給定值的1%或一個單位之間的價值降低，取更大的。以工作站的所需數(shù)量建立的解決方案進行了局部的改進（見3.3節(jié)）和信息素的沉積建造未來的解決方案（見3.4節(jié)）。算法1即為提出的算法。算法1:TSALBP-1的解決程序m heuristic(c,A) /見3.2節(jié)INIT:iteration = 0 c A m-1RESTART:initialize_trail() /見3.4節(jié)do ants(,) /

19、見3.2節(jié)IF( = ) then(,) localsearch() /見3.3節(jié)IF AND Goto INITENDIFiteration iteration + 1IF iteration = 50 * n GOTO RESTARTUpdate_trail(,) /見3.4節(jié) MIN MINELSE MAX MAXENDIFWHILE(NOT(end_condition)我們討論從SALBP-1問題概要生成解決方案的理論。然后我們展示如何進行局部改進，根據(jù)SALBP-2概要，建設(shè)程序采用跟蹤技術(shù)。3.2 生成解決方案為解決平衡問題構(gòu)建程序大部分是基于優(yōu)先規(guī)則或約束程序。對可用的程序進行深入的研究可以發(fā)現(xiàn)，見Scholl（1999）?；趦?yōu)先規(guī)則的程序是基于SALBP-1實例的可行解。通過一系列的規(guī)則，每個任務(wù)被分配的優(yōu)先值取決于它的加工時間和優(yōu)先關(guān)系（見Hackmam等人，1989）。優(yōu)先權(quán)用于建設(shè)過程中把任務(wù)分配給工作站。該理論包括兩個框架：一是工作站定向，另一個是任務(wù)定向。前者是用在這項研究中，用于SALBP-1多樣的計算實驗（見