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

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