外文翻譯--并聯(lián)機(jī)床的操作安排.doc

附錄1并聯(lián)機(jī)床的操作安排我們引進(jìn)獨(dú)特的排序問題，來改進(jìn)多主軸機(jī)床。這些機(jī)器同時對一個以上的部分執(zhí)行操作的能力造成了約束，這在傳統(tǒng)預(yù)定的文學(xué)中是找不到的。為這個問題引進(jìn)了兩種類型的解決程序。第一利用優(yōu)先分配規(guī)則和延遲因素概念，而第二是利用隨機(jī)碼編寫的遺傳運(yùn)算法則。這些方法的有效性是在測試問題時與下界對比中被證明的。1介紹并聯(lián)機(jī)床在計(jì)算機(jī)輔助工藝設(shè)計(jì)(CAPP)設(shè)備系統(tǒng)中，驅(qū)動加工硬件有了改進(jìn)。在硬件改善方面為了獲得最大的利益，CAPP軟件能夠最大限度地發(fā)揮這些改進(jìn)加以開發(fā)。并聯(lián)機(jī)床和傳統(tǒng)數(shù)控機(jī)床的最關(guān)鍵的區(qū)別是，前者包含了多個主軸以及它可以同時加工多個工件。結(jié)果，PMT的一次加工可以加工多于一個工件或者一次可以執(zhí)行多于一個操作。這違背了最基本的假設(shè)或傳統(tǒng)工藝規(guī)劃調(diào)度。2排序問題的定義排序問題牽涉到對既定的工作，其工件加工時間最小化的操作順序。一個工作有一個或多個工件組成，每個工件在其上都有很多執(zhí)行操作。已經(jīng)給出了每個操作所需的時間、每個操作模式（如下所述）和各個操作之間的優(yōu)先關(guān)系。我們的目的是決定一個操作順序，這個操作順序?qū)烟幚磉@一系列操作所需的總時間最少化。一個并行車床上使得操作順序復(fù)雜化的四個問題描述有：（i）操作之間的優(yōu)先約束關(guān)系；（ii）約束形式；（iii）對零件加工位置的操作選擇和（iv）對加工單元的刀具選擇?，F(xiàn)在，這些描述已經(jīng)更詳細(xì)了！優(yōu)先約束的提出有三個原因。首先，涉及到幾何考量。因?yàn)榧庸げ僮鞲淖儾牧系捏w積，有些操作必須先于其它操作。第二個原因是公差。公差可能是一個工件與另一個工件尺寸配合特點(diǎn)所需要的。第三種優(yōu)先形式由需要保證精度的制造實(shí)踐產(chǎn)生的。在并行車床上所進(jìn)行的操作根據(jù)工件在零件加工位置的運(yùn)動和加工單元的運(yùn)動可以分為三種模式，加工單元執(zhí)行加工工件的操作。在LevinandDutta中，這三種模型被定義為：轉(zhuǎn)削工件旋轉(zhuǎn)而加工單元固定；磨削工件固定而加工單元運(yùn)動，比如鉆削或者銑削；輪廓銑工件和刀具都運(yùn)動，比如輪廓銑?，F(xiàn)在，由于技術(shù)的局限，不同模式的操作不能在同一零件加工位置進(jìn)行。約束模式的增加添加了復(fù)雜性。由于一個并行車床有多樣的零件加工位置，所以我們必須決定要在每個零件加工位置完成的一系列操作。這些決定將對完成加工零件所需的時間起很大作用。例如，為了使得物流順暢，一個工件代表性地訪問沒個零件加工位置一次。我們假設(shè)零件不能反向訪問一個給定的零件加工位置。因此，一個零件加工位置所安排的操作不能先于工件已訪問過的其它零件加工位置所安排的操作。加工單元所使用的刀具也對加工周期起作用。只有在不同的加工單元使用不用的刀具才可能并行進(jìn)行。這個問題復(fù)雜的是，不是每個加工單元都可以達(dá)到每個零件加工位置。刀具是一個困難的問題，將在未來的研究中被解決掉。在一個指令中可能存在不同零件之間的相互作用。假設(shè)一個零件訪問兩個零件加工位置。假如在指令中只有一個零件，那么，目的就是要使得零件盡可能快的通過這兩個零件加工位置。但是，假如有很多工件在一次命令中，當(dāng)一個工件轉(zhuǎn)到第二個零件加工位置時，新的工件就會被放置在第一個加工位置?，F(xiàn)在的目標(biāo)是盡可能快的完成兩個零件的操作在平衡方式下。謹(jǐn)慎執(zhí)行這些先后順序，使得并聯(lián)機(jī)床可以在一次進(jìn)程中同時執(zhí)行一些操作，從而縮短了總的時間。因此，這個先后順序問題的目標(biāo)是最小化加工次序的總的時間，考慮了一系列相關(guān)問題：工具分配，操作任務(wù)以及操作的先后順序。理想的說，所有的三個問題都必需同時解決。我們首先要解決的是，由已知刀具和運(yùn)行任務(wù)產(chǎn)生的排序問題。在今后的工作中,我們將建立模塊來處理分配問題.關(guān)于這個問題的數(shù)據(jù)見表1。最佳操作順序有一個45的制造時間的跨度見圖1。我們提供一個關(guān)于并聯(lián)機(jī)床上出現(xiàn)的排序問題的詳細(xì)描述。參數(shù)設(shè)置n=流程圖上運(yùn)行任務(wù)的數(shù)量，1，2，；i=任務(wù)標(biāo)號，1，2，n；mi=運(yùn)作模式i，1，2，3；pi；j=第i個運(yùn)行任務(wù)的第j個當(dāng)前步驟，1，2，n；Pi=第i個運(yùn)行任務(wù)的所有當(dāng)前步驟的設(shè)置，1，2，n；ti=第i個任務(wù)的運(yùn)行時間，；MUmax=MU（機(jī)組）在一個問題中的數(shù)目，1，2，；PMLmax=PML在一個工序中的數(shù)目，1，2，；M=大正數(shù)；MUi=第i個操作的MU，1，2，MUmax；PMLi=第i個操作的PML，1，2，PMLmax；決定問題的變量Ci=第i個操作完成的時間，；Cmax=完成全部n個操作的最大時間，；附加符號ij表示在第j個操作開始時，必須完成第i個操作；ij在最后的時間表上，第i個操作完成在第j個操作之前；xij=如果ij的話，那么一個指示變量就是1。我們進(jìn)行六個假設(shè)；（i）機(jī)組連續(xù)不斷；（ii）沒有操作優(yōu)先權(quán)；（iii）事先知道操作時間；（iv）操作已分配給PML；（v）刀具已分配給MU，沒有副加工；（vi）我們的目標(biāo)是最小化制造時間跨度（即盡可能快完成這項(xiàng)工作）。假設(shè)MUs是持續(xù)用來做為消除MU崩潰的需要。在第3部分給出的解決方案，可以用來改進(jìn)解決這些崩潰問題。然而，數(shù)據(jù)設(shè)置測試沒有包括MU的崩潰信息。不允許優(yōu)先響應(yīng)金屬切割作業(yè)的技術(shù)約束。假設(shè)已知每步操作的加工時間，這個時間必須扣除掉共用加工參數(shù)而同時進(jìn)行的預(yù)定操作的重疊部分。假定刀具已經(jīng)分配給刀架，并且沒有副刀具，也就意味著每步操作都必須由一個特定的MU來完成。在今后的工作中我們將忽略掉假設(shè)(iii),(iv)和(v)。假設(shè)(iv)和(v)定義了分等級設(shè)計(jì)問題的部分。今后的工作將利用在本文中提到的算法，為全部問題建立一個決策支持系統(tǒng)。對PMT排定問題來說，制造時間跨度（假設(shè)（vi）目標(biāo)是合理的，就像完全發(fā)生在單個機(jī)床中一樣。我們假設(shè)當(dāng)決定解除定單時，應(yīng)在更高的決策層次上考慮庫存和交貨期。在PMT上定義加工計(jì)劃的目標(biāo)是，盡快完成定單上的工件生產(chǎn)。制造時間跨度是這個目標(biāo)的合理措施。如果沒有模式?jīng)_突，我們將得到由P1表示的一個簡單問題，這是加工車間排序的普遍問題，也就是我們所說的NP-hard6。它與資源約束項(xiàng)目排序問題(RCPSP)有相同的結(jié)構(gòu)。P1中的每個步驟與RCPSP中的行為相適應(yīng)，要求一個包含所有可用性的資源回收單元。在P1中的MU符合在RCPSP問題中的資源。優(yōu)先約束對兩個問題來說是一致的。在過去的30年中RCPSP已被廣泛的研究過7-10。我們將建立這些方法中的一部分，來發(fā)展處理更復(fù)雜多變問題的算法。雖然P1相當(dāng)于在先前文獻(xiàn)中所研究過的問題，但它對在PMT中更復(fù)雜問題的多變性來說是不正確的。把模式制約引進(jìn)到這個問題中來，產(chǎn)生了這么個說法，據(jù)我們所知，這個說法以前的Levin、Yip-Hoi、Dutta等人已經(jīng)提及了。這個問題可以用以下的數(shù)學(xué)式來表示。數(shù)學(xué)公式P2約束（2）保證了每步操作不會在先前一步操作完成之前開始。分離性的約束（3）和（4），保證了每個MU在任何時候最多只執(zhí)行一個任務(wù)。這些分離性的約束和在加工車間所陳述的排定問題是類似的。分離性的約束（6）和（7），確保了一個操作可以同時預(yù)定一樣的機(jī)器模式。這些約束把P1和P2區(qū)分開了。我們現(xiàn)在對P2建立了啟發(fā)式的解決方法。3.啟發(fā)式程序解決方法論我們限制為這個問題所建議的啟發(fā)式方法解決方案有兩個原因。首先，約束（6）和（7）的附加條件，相對于P1增加了P2中（0，1）變量的數(shù)目。我們測試的問題有成百上千個0-1變量和約束。大量的0-1變量使得直接數(shù)學(xué)公式解決方法失效。實(shí)驗(yàn)結(jié)果表明，包括25項(xiàng)任務(wù)的實(shí)例問題需要大約40小時的時間來解決CPLEX在SunSparc20中應(yīng)用。包含50個任務(wù)的實(shí)例問題不可能在200個小時內(nèi)解決。其次，為問題P2發(fā)展的啟發(fā)式規(guī)則可以被擴(kuò)展，在往后的工作中，包含由放寬假設(shè)(iii),(iv)和(v)而產(chǎn)生的附加復(fù)雜性。我們研究兩種類型的啟發(fā)式程序。第一運(yùn)用改良的優(yōu)先調(diào)度規(guī)則，解決了P2中的結(jié)構(gòu)問題。第二是利用隨機(jī)碼編碼的遺傳算法。3.1啟發(fā)式的優(yōu)先規(guī)則優(yōu)先分配規(guī)則已被運(yùn)用到許多不同的排定問題上，包括P1。因?yàn)镻2類似于P1，來自O(shè)laguibelandGoerlich13的16個優(yōu)先規(guī)則已作用于P1，在P2中被挑選來用做測試。檢驗(yàn)規(guī)則包括最短的加工時間、最長的加工時間、最直接的后續(xù)事物、最不直接的后續(xù)事物、最大的總的后續(xù)事物、最少的總的后續(xù)事物、最長的跟隨路線、最大的位置重力、最少的位置重力、最大的平衡位置重力、最早的完成時間、最早的開始時間、最遲的完成時間、最小的減落時間、每個后續(xù)事物的最小浮動。關(guān)于細(xì)節(jié)和定義看OlaguibelandGoerlich.對于一個給定的問題實(shí)例，每個優(yōu)先規(guī)則都被用來建立一個時間表以及據(jù)說最好的16個進(jìn)度表。16個優(yōu)先規(guī)則在P2型問題中被檢驗(yàn)，并且討論它的結(jié)果在第5部分。一般來說，不能很好的執(zhí)行分配規(guī)則，這點(diǎn)并不令人驚訝，因?yàn)樗麄儾豢紤]概念模式。為了改善性能，這些規(guī)則被改良來解決P2中的結(jié)構(gòu)問題。在P2中只有一個操作可以平行的預(yù)定一樣的模式。這是用一種利用延遲類似記數(shù)來完成的，在Norman14中用于車間加工排定。在優(yōu)先運(yùn)算法則的清單上的關(guān)鍵因素是切實(shí)可行的，操作位置給出了三個不同的機(jī)床模式。舉例來說，假設(shè)有一個零件在時間10至26一直在運(yùn)轉(zhuǎn)。另一個旋轉(zhuǎn)操作要求一個刀具，刀具可利用的時間直到20才需要10個時間單位。這個操作的排定將會擴(kuò)大旋轉(zhuǎn)的時間。無論我們是否應(yīng)該確定新任務(wù)的時間確定，是關(guān)于它的危險(xiǎn)系數(shù)相對于其他沒有預(yù)定的功能。延遲因素是這個危險(xiǎn)系數(shù)的度量標(biāo)準(zhǔn)。五個延遲因素，如果延誤了5個單位或更少的模式轉(zhuǎn)變，也就意味著我們將要確定鉆孔操作的時間。因此，更高的延遲因素，使得操作變得更加緊急。每個操作中設(shè)立的合理的延遲因素，是通過研究一系列可能產(chǎn)生的因素而來的。下列運(yùn)算法則是描述如何改良規(guī)則1至16來合并延遲數(shù)目的概念。讓j代表一系列的排定操作（沒排定的操作關(guān)于沒有排定原有事物），一系列的k操作是包含了不定期和未排定兩個，在操作i中，pi代表優(yōu)先規(guī)則的價值。步驟1.初始化。選擇優(yōu)先規(guī)則和估算pi的價值（每個優(yōu)先規(guī)則只能做一次）。初始化J和K。步驟2.確定第一步操作的時間。重新考慮的實(shí)例數(shù)據(jù)問題已在表一中給出。如果最短加工時間規(guī)則是實(shí)用的，那么部分操作將在兩個操作之后，此操作包含1和4?，F(xiàn)在，在接下來的排定操作2中直接運(yùn)用SPT結(jié)果，和在PML1的總時間要求將會是41。然而，若延遲時間足夠的話，操作