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