[發明專利]一種基于遺傳算法的曲面分段場地布局調度方法

有效

• 申請號: 201210552878.7
• 申請日: 2012-12-18
• 公開（公告）號: CN102968702B
• 公開（公告）日: 2017-02-22
• 發明（設計）人: 王愛民;盧治兵;唐承統;李京生
• 申請（專利權）人: 北京理工大學
• 主分類號: G06Q10/06
• 分類號: G06Q10/06;G06Q50/04
• 代理公司: 北京銀龍知識產權代理有限公司11243
• 代理人: 黃燦,安利霞

技術領域

本發明涉及制造技術領域，特別涉及一種基于遺傳算法的曲面分段場地布局調度方法。

背景技術

在大型制造行業（如船舶建造與飛機制造）的制造過程，需要將整體分為一個個大小不一、形狀復雜的分段來進行建造，且很多分段往往十分的沉重并且占用很大的場地面積。因此為了建造體積和質量都很大的分段，其建造場地需投入很多昂貴且重要的設備和材料（如大型吊車，物料托盤，胎架等）。由于場地建造的成本很高，分段占用場地的時間周期長、面積大，所以場地往往是制約船舶建造效率的瓶頸。在船舶曲面分段調度的過程中，調度的核心資源就是場地，而不同于傳統的機加生產調度主要考慮人員和設備。

船舶的建造是大量分段的焊接裝配過程，其中分段按照幾何形狀進行分類包括：平直分段和曲面分段。其中曲面分段主要是由船舶艏部和艉部的組件，具有復雜的幾何形狀。復雜的幾何圖形在場地內的組合也是多種多樣的，單純的依靠調度人員的個人經驗進行分段場地的空間布局是很難達到比較優化的場地布局。但是船舶曲面分段的空間布局又不同于一般套料算法的空間調度。一方面由于船舶曲面分段的建造過程場地利用是一個隨著時間軸動態變化的一個過程，套料算法只能實現一個固定空間占用布局。另一方面，船舶曲面分段場地布局中場地是最重要的調度資源但比不是唯一要考慮的調度資源，如人力資源，設備資源，重要物資等，都是分段場地布局是不得不考慮的影響因素。同時僅對于空間布局來說，套料算法往往面對的問題是空間資源相對進入空間的幾何圖形是無限的，而分段場地布局的空間調度問題主要集中在分段相對于場地是無限的。

綜上所述，船舶曲面分段空間布局調度是一個動態，復雜的過程，其調度的核心是實現有限的場地在時間軸上進行無限的利用，最重要的優化指標就是場地的利用率。對于船舶空間布局調度問題，雖然已有大量的研究，但往往存在以下不足：

（1）布局算法與船舶生產實際結合較少，船舶曲面的制造過程具有其自身的特點，單純的套料算法難于適用于船舶曲面分段場地布局分配過程。例如：分段的排布順序需要按照實際生產進程進行不斷調整；場地具有的動態性特點使得其可用面積會隨時變化；分段在完成生產后必須調離場地，剩余面積仍然需要進行合理利用，無法進行一次性的布局分配必須進行多次調度；

（2）傳統的曲面分段布局算法對生產實際約束進行了簡化，從而造成布局結果無法實現效率的提升，例如多邊形分段被抽象成矩形，使得曲面分段的布局變為矩形堆疊；將場地面積劃分為不同的區域，使得分段的排布只能在固定的區域內進行，從而降低不規則圖形的拼接難度或者直接忽略不規則圖形的拼接；

（3）傳統的空間布局算法通過簡單的優化準（如最大矩形，長邊規則等）判定分段放置位置是否最佳低估空間布局的復雜性。空間組合的多樣性決定了簡單的優化準則約束是無法全面的綜合的考慮所有分段放置場地時哪種布局方式是最佳的。例如滿足優化準則并不一定有利于后續分段的放置反而降低了場地利用率。

由于空間組合的復雜性，用簡單的針對單一分段的約束優化準則是無法求得空間布局的最優解。

發明內容

本發明要解決的技術問題是提供一種基于遺傳算法的曲面分段場地布局調度方法，而為調度人員進行分段布局調度提供輔助。

為解決上述技術問題，本發明的實施例提供一種基于遺傳算法的曲面分段場地布局調度方法，包括：

步驟1、應用基于有限建造資源的日程計劃平衡制定算法，根據預設的調度順序對分段進行分段空間布局調度和虛擬流水式人力資源調度，并制定針對分段建造的資源場地和人員安排的日程計劃；

步驟2、應用基于優化矩陣的多目標遺傳算法完成分段調度順序的排列編碼和解碼，并從根據日程計劃建立優化的矩陣中選取最優的調度結果。

作為上述技術方案的優選，其中所述步驟1中所述的進行分段空間布局調度具體為：

步驟11、對整個場地的曲面分段的調度進行初步規劃，并制定曲面分段的布置順序；

步驟12、獲取曲面分段的幾何圖形和場地邊界的幾何圖形，通過確定曲面分段是否在場地內與其他曲面分段及場地邊界發生碰撞，以獲取曲面分段在該場地內的可能的布置方案；

步驟13、對所述可能的布置方案進行篩選以最終確定曲面分段在場地內的布置位置，生成曲面分段空間布局分配方案。

作為上述技術方案的優選，其中所述步驟1中所述的虛擬流水式人力資源調度具體為：

步驟14、獲取每一分段內的加工工序；