1、船舶制造論文：基于虛擬流水線的船舶分段建造調度問題研究    摘要：針對傳統船舶分段制造中出現的生產等待、時間冗余等問題，應用虛擬流水線生產模式的方法進行生產系統改造。在滿足約束的前提下，建立以作業班組在生產系統中的流通時間最短為目標的班組調度模型。針對分段車間調度問題應用一種基于混合蟻群遺傳算法（Mixed Ant Colony and Genetic Algorithm，MACGA）實現了作業班組的優化調度。最后，以某造船廠分段加工車間為例，驗證了虛擬流水線模式及其調度方法可以有效的提高船舶分段的生產效率。 Abstract: Traditional

2、 shipbuilding appears waiting, time redundancy and other issues, in order to solve these problems, this paper presents a virtual assembly line production model. Under the premise of meeting the constraints, the paper establishes a scheduling model which used the shortest working hours of work-teams

3、as the goal, on this basis, using MACGA to achieve optimal scheduling. At last, an example on a shipyard is given which can verify the virtual line model and its scheduling method can effectively improve the production efficiency of ship building. 關鍵詞：船舶制造；虛擬流水線；混合蟻群遺傳算法 Key words: shipbuilding；virt

4、ual flow line；MACGA 0引言 船舶制造企業是一個大型、單件、小批量生產系統，具有新產品多、更新換代快、約束條件多、生產組織復雜等諸多特點。傳統生產模式下，由于產品體積和重量都很大，搬遷運輸很困難，在生產過程中不適宜到處搬運，因此，一般采用固定工位的生產模式，即將工件的基體放置到一個固定的平臺上，操作者和設備都圍繞著基體在固定的工位上將各種零部件裝配或者焊接到基體上，最后形成所需要的產品。這種固定工位的生產方式生產效率低，生產周期長，生產效益低1。由于現代的造船模式向著敏捷造船模式的方向發展，傳統造船模式已經跟不上生產的需求，且船舶企業在實際生產中存在生產計劃管理模式落后、管理

5、方法粗放、計劃指導性差，從而導致造船周期長、誤工誤期嚴重、庫存占用高、資金利用率低等突出問題。 針對船舶分段生產過程的研究，國內外文獻都比較少。張志英、李川2-4等人提出了虛擬流水線的生產組織過程，并分析了實現虛擬流水線的關鍵技術。虛擬流水線的方式改變了傳統造船模式中分段生產的所有工作都在一個胎位上完成的生產模式，它利相似性原理對產品加工任務分解成門類繁多的中間產品，按作業的相似性特征，遵循一定準則進行分類，以便用相同的加工處理方法擴大中間產品的成組批量，以建立批量性的流水定位，或流水定員的生產作業體系5。在虛擬流水線方式下，若干個被加工的工件或裝配主體件固定在工作平臺（工位）上不動，而人員、

6、設備（可移動的）和工具按作業任務不同并根據成組技術原理歸類為各種作業任務組。組成的不同工作組按照一定的順序在不同的工位之間流動，完成指派的加工任務。這種人員、設備和工具的流動構成了“人員流”與“設備工具流”。對于同一個要加工的工件，它的整個加工任務是由不同的作業組依次操作完成的；對于同一個作業組，它在不同的工位之間重復完成相同或類似的加工任務。從物理空間，加工的工件固定不動，而在邏輯上，工件依次在不同的人員和設備工具之間相對流動而被加工4。與傳統的流水線相比，虛擬流水線既達到了流水線所具備的高效率，又具備了流水線所沒有的高柔性的要求。 虛擬流水線模式下作業的班組調度問題是類似于有關多機調度問題

7、的組合優化問題。文獻6系統的總結了這類問題的研究進展，其中采用遍歷搜索的方法受制于時間和資源的限制很難得到使人滿意的結果，而通過鄰域搜索7、混合遺傳8-10、禁忌搜索11等優化求解方法是目前調度問題研究的熱點。針對虛擬流水線模式的作業班組調度問題張志英等人應用遺傳算法實現虛擬流水線的船舶曲面分段的制造的作業車間調度，遺傳算法雖然具有大范圍的全局搜索能力，但對系統中的反饋信息利用不夠，當求解到一定范圍時往往做大量無用的冗余迭代求精確解效率低。本文基于虛擬流水線生產組織模式，提出一種改進后的遺傳算法用于解決車間調度問題，并以作業班組在生產系統中的流通時間最短為目標函數建立作業班組調度模型，利用應用

8、混合蟻群遺傳算法實現分段車間的班組作業調度，并結合實際生產數據驗證研究方法的有效性。 1虛擬流水線生產模式下的作業班組調度問題模型 本文假定某一個加工系統有n個作業班組和k個待加工分段，n個作業班組可根據加工技能的不同分為g種不同類的作業班組，每個分段包含一道或多道工序，每個分段的工序順序是預先確定的，不同的工序由具有相對應加工技能的作業班組中的任一空閑的作業班組來加工，工序的加工時間是已知的。生產排序的目標是為每道工序選擇最合適的作業班組，以及確定每個作業班組進入各個加工工位的最佳加工順序及開工時間，使所有作業班組在生產系統中的流通時間最短。數學模型:目標函數（使作業班組在生產系統中的流通時

9、間最短）。 Min（SM）=Max（t+t），（t+t），（t+t） 其中：k表示分段序號，j表示分段k的工序號， SM是所有作業班組的最后完工時間，t表示第k個分段第j道工序的加工時間，t表示第k個分段第j道工序的等待時間。 另外，X=0，1：若作業班組i在第k工位對第j道工序進行加工，則X=1；否則X=0。R=0，1：第k工位的第j道工序和第e工位的第g道工序都有作業班組i加工，若工序j先于工序g，則R=1；否則R=0。 該目標函數代表了系統最長完工時間最短，因為作業班組對工序的加工是并行的，所以最長的生產加工時間也就代表整個加工任務完成所需的時間。整個加工任務完成所需的時間是指加工完成時

10、間和加工任務所需的等待時間之和。其約束條件為： （1）E-Rt+t其中1該式表示只有當作業班組加工完上道工序后，下一作業班組才能進入工位對下道工序進行加工。 （2）E-Et+t其中X=X=1，R=1 該式表示任一確定時刻，作業班組或是設備i不能同時加工任意兩個不同的工位上的兩個不同工序。 （3）X=1表示每項任務都有一個作業班組承擔，并在同一時間只有一個作業班組對任務進行加工。 2基于混合蟻群遺傳算法的作業班組調度系統 遺傳算法類似于自然進化，通過作用于染色體上的基因尋找好的染色體來求解問題。與自然界相似，遺傳算法對求解問題的本身一無所知，它所需要的僅是對算法所產生的每個染色體進行評價，并基于

11、適應值來選擇染色體，使適應性好的染色體有更多的繁殖機會。在遺傳算法中，通過隨機方式產生若干個所求解問題的數字編碼，即染色體，形成初始群體：通過適應度函數給每個個體一個數值評價，淘汰低適應度的個體，選擇高適應度的個體參加遺傳操作，經過遺傳操作后的個體集合形成下一代新的種群，對這個新種群進行下一輪進化，這就是遺傳算法的基本原理。 蟻群算法是模擬真實蟻群覓食過程尋求最短路徑的原理，基本思路是：自然界中的螞蟻是以外激素（pheromone）為媒介進行信息傳遞的，從而螞蟻個體能相互協作，完成復雜的任務。螞蟻在行動中，會在它們經過的地方留下外激素。同一蟻群中后到的螞蟻能夠感知到這些外激素的存在及其強度，并

12、以此來指引自己的行動方向，具體表現在選擇外激素強度大的路徑的概率要高些。這樣，后到的螞蟻同樣留下外激素，對原有的外激素進行加強，如此循環下去。蟻群的行為便表現出一種信息正反饋現象：某一路徑上經過的螞蟻越多，則后到者選擇該路徑的概率就越大。蟻群算法很容易與多種啟發式算法結合，以改善算法的性能。眾多研究已經證明蟻群算法具有很強的發現較優解的能力，這是因為該算法不僅利用了正反饋原理在一定程度上可以加快進化過程，而且是一種本質并行的算法，不同個體之間不斷進行信息交流和傳遞，從而能夠相互協作，有利于發現較好解。 混合算法的思路是首先由遺傳算法產生較優解，較優的路徑留下信息素，其他不改變；然后按照蟻群算法

13、，讓螞蟻完成一次遍歷后，再讓螞蟻作遺傳算法的交叉操作和變異操作，有可能經過交叉操作和變異操作的解不一定得到改善，只有改變螞蟻的路徑，代替原來的路徑，才能使解得到改善。將遺傳算法與蟻群算法的混合來解決作業車間調度問題，不僅僅采用遺傳算法生成初始信息素分布，在螞蟻算法尋優中，采用交叉和變異的策略，改善解的質量12。 2.1 遺傳編碼分段作業車間中有K個待加工分段，每個分段均需要2類作業工序即裝配和焊接，對于每個工序可供選擇的作業班組很多，因此對于一組給定的分段，作業班組的調度計劃有很多。假設待加工分段數k=3，裝配和焊接班組各2個，按照分段工藝順序（拼裝自動焊吊裝自動焊中組裝中組焊縱向裝縱向焊外板

14、裝）隨機產生一個分段作業順序如下： （分段1拼裝，分段2拼裝，分段1自動焊，分段2自動焊，分段1外板裝，分段2外板裝，分段3拼裝，分段3自動焊，分段3外板裝） 各作業班組完成隨機產生的分段作業順序一一對應，構成一個作業班組的可行序列即染色體編碼。 2.2 適應度函數適應度函數是用來評價染色體優劣的標準，本文使用數學模型中的目標函數即使作業班組在生產系統中的流通時間最短作為遺傳過程中染色體的適應度函數，滿足了制造周期最小化的目標。即適應度函數為： fitness=Min（SM） =Max（t+t），（t+t），（t+t） 2.3 遺傳策略變異策略：在K個分段中隨機選取第Ki分段，在路徑C0中交換

15、Ki和Ki+1分段，其余不變，此時的路徑為C1。比如C0=231465，K2=3，則C1=213465。 交叉策略：兩染色體交叉時，父本old2的交叉區域加到old1對應的位置，刪除old1中已在old2交叉區域中出現過的分段。如old1=1 2 3 4 5 6，old2=1 5 3 2 6，若交叉區域為：5 3 2，則交叉后產生的新染色體為：1 5 3 2 4 6。 混合蟻群遺傳算法具體步驟如下： 步驟1 利用遺傳編碼隨機產生初始種群，并利用遺傳算法產生一個較優解，在這個路徑上留下信息素； 步驟2 nc=0，（nc為搜索次數），將m個螞蟻置于K個頂點上； 步驟3 將各螞蟻的初始出發點置于當前

16、解集中，對每個螞蟻M（M=1，2，m）按概率P移至下一頂點j，將頂點j置于當前解集，完成一次遍歷； 若j=Ji（M），P（t）=，否則為0 步驟4 根據交叉概率，選擇若干組解，然后進行交叉的解，若新的目標函數變好，接受新值，否則拒絕； 步驟5 根據變異概率，判斷是否變異，變異后的目標函數好接受新值，否則拒絕； 步驟6 計算各螞蟻的路徑長度LM（M=1，2，3，m），記錄當前的最好解； 步驟7 對于路徑長度LM小于給定值的路徑，按更新方程修改軌跡強度； 更新方程：=+。 E為此次分配全部目標的失敗概率，表示強度的持久性系數，一般取0.5-0.9左右，Q為一正常數。 步驟8 nc=nc+1； 步驟

17、9 若nc小于預定的迭代次數且無退化行為則轉步驟2； 步驟10 輸出目前最好解。 3實例驗證 為驗證研究方法的有效性，本文以南通某船廠的分段生產車間為例進行實驗。選取7500T散貨輪待加工分段中的六個分段的作業任務作為數據來源，如表1、2。 根據要求加工時間是20天，由公式：T=（h）（其中，T表示要求完成時間、n表示分段數、m表示某工序在各分段上的加工次數）以焊接作業班組為例可算出焊接班組的平均移動節拍T0=5。在分段加工作業中，部件制作、構件裝配和分段合攏都是以焊接為主的作業。因此，必須根據焊縫長度和生產節拍的需要安排足夠數量的焊工來完成作業。焊接的生產節拍確定以后，裝配、打磨等其它作業的

18、生產節拍和勞動力安排必須與焊接作業相一致，這樣才能保持連續不斷的均衡作業。由此可以推出裝配班組的生產節拍也是5。經計算可得各類作業的總任務量和單工序的平均工作量，根據作業類型中掌握各類技能的工人數量及相應的工作能力按照公式g=可算出焊接班組和裝配班組的組數為3。分組情況如表3。 將分段制造中不同類型作業班組分配進行整體考慮，并且考慮了所需要的關鍵資源，基于前述數學模型，利用前文2節所述的基于混合蟻群遺傳算法來生成作業班組的生產計劃。得到作業班組加工時間表如表4。 并進而可以得到作業班組的調度結果的甘特圖，如圖1所示其中包括各作業班組的加工信息和總的完工時間。 在實際生產中，該造船廠通過對分段車

19、間進行虛擬流水線系統改造，大大提高了車間的生產效率。從2003年至今每年的人均噸位和人均產值分別保持了19% 和28% 的年增長率。可見通過虛擬流水線系統可以大幅度提高船舶分段制造的生產效率, 取得良好的生產效益。 4結論 本文的理論研究對于提高我國船舶制造業的競爭力具有一定的積極意義。通過改造生產組織的模式有利于提高車間的生產效率，降低生產成本，便于生產控制；有利于縮短船舶生產周期，采用科學的計劃控制體系，消除傳統造船生產模式的等待、冗余時間，來達到縮短制造周期的目的。現代造船模式是對我國船舶企業的生產組織管理體制的一次重大變革，即按區域來組織設計和生產的殼、舾、涂一體化的管理模式。本文提出

20、的車間組織生產模式及相關生產調度方法可在現代造船模式各個環節的制造車間進行應用推廣。 參考文獻： 1陳強中心制造船模式的研究與應用D哈爾濱：哈爾濱工程大學，2001 2張志英,江志斌,陳強等.曲面分段加工的虛擬流水線生產模式及關鍵技術探討J.中國造船,2005,46(3):112-116. 3張志英,江志斌.虛擬流水線生產系統及Petri網建模技術研究J.華東船舶工業學院學報,2004,18(4):32-36. 4張志英,李川,李珍.面向船體曲面分段建造的虛擬流水線生產調度J. 工業工程，2010，13(1):58-63. 5張美玉等譯.相似性理論的原理與實踐J.成組技術與生產現代化，1996No.1, 25-28. 6Jain A S, Meeran S Deterministic job shop scheduling: Past, present and futureJ.European Joumal of Operational Research, 1999, 113(2):390-434. 7王磊,黃文奇.求解工件車間調度問題的一種新的鄰域搜索算法J.計算機學報,2005,28(5):809-816. 8Jo séF G, Jorge JM M, Maoríc io GC