[發明專利]基于工序劃分的任務規劃方法及系統

在審

• 申請號: 201410407852.2
• 申請日: 2014-08-18
• 公開（公告）號: CN104166903A
• 公開（公告）日: 2014-11-26
• 發明（設計）人: 徐戰;宋勇;周保琢;陳粵海;唐經天;劉俊;郭繼文;嚴明
• 申請（專利權）人: 四川航天系統工程研究所
• 主分類號: G06Q10/06
• 分類號: G06Q10/06;G06N3/12
• 代理公司: 四川省成都市天策商標專利事務所 51213
• 代理人: 伍孝慈

技術領域

本發明涉及任務規劃領域，特別涉及一種基于工序劃分的任務規劃方法及系統。

背景技術

任務規劃是指在一定時間內把一定量的任務按照一定的方法安排給規定的人員完成。在計算機科學和工業領域中，任務規劃問題有著廣泛的應用背景，例如批量物資轉運、大型實驗工作準備等，對任務規劃問題的研究都是焦點。

從資源排布角度看，任務規劃是將有限資源安排給不同的工作，最終設法達到預定的優化目標。具體地，任務下達方下達工作任務后，同時確定工作資源(包括人員、時間等)并明確工作對象(如物資、工具等)，同時，根據任務類型和相關輸入，確定任務約束和優化目標，并根據上述幾方面的內容，經過優化和決策，輸出規劃結果。

從計算復雜性理論來講，任務規劃問題一般是NP完全問題，是優化問題中最難的一類組合優化問題，其求解難度隨著問題規模的增大和約束的增多而成幾何級增長，絕大多數算法很難求得其精確解。

在任務規劃問題中，通常組成任務的各項工作之間相互影響、相互作用，每項工作又要考慮它的操作步驟、工作難度等因素，因而相當復雜。例如一項物資轉運任務包括物資打包、物資裝車、物資轉運、物資卸車等幾個步驟，零件生產又根據零件類型的不同具有不同的工序和生產時間，因此任務規劃需要考慮的因素很多。同時，任務規劃中又有很多隨機因素，例如實際工作的執行時間。目前主要采用人工方式進行任務規劃，但是人工規劃主要是依靠經驗進行人工推理，由于這種規劃方式沒有合理的理論依據支撐，而且在分配資源中不可避免地會受到主觀意識影響，此外，面對大規模任務的規劃問題，人工規劃的工作量大而且不夠智能。

發明內容

本發明提供一種基于工序劃分的任務規劃方法及系統，用于解決現有技術中任務規劃問題求解難度大、通過人工進行任務規劃工作量大而且不具備智能化特點的問題。

為了解決以上的技術問題，本發明的第一個方面是提供一種基于工序劃分的任務規劃方法，所述方法包括如下步驟：

步驟A：創建任務規劃所需的基礎數據，所述基礎數據至少包括工作人員、工作對象和工作任務，數據管理模塊將基礎數據保存至系統數據庫；

步驟B：將所述工作任務劃分為多個子任務，其中每個子任務包含多個工序，對工序進行工作量估計以獲取工序工作量；

步驟C：選取約束條件和優化目標，并采用啟發式算法確定規劃方案，所述規劃方案至少包括工作人員執行的工序和執行工序的順序。

在第一個方面的第一種可能實現方式中，其特征在于步驟C之后還包括:

步驟D：顯示所述規劃方案；

步驟E：通過對所述規劃方案進行手工拖動以調整規劃方案。

在第一個方面的第二種可能實現方式中，所述步驟C中采用啟發式算法確定規劃方案的步驟為：

步驟C1：為各個子任務和各個工作對象分配初始優先級，將該優先級作為初始種群中的初始染色體，通過采用對所述初始染色體交換子任務優先級和工作對象優先級的方式生成初始種群；

步驟C2：判斷是否已經生成了滿足約束條件和優化目標的染色體，如果生成了則執行步驟C4，如果未生成則執行步驟C3；

步驟C3：選擇種群中的染色體執行交叉運算和/或變異運算，運算完畢后執行步驟C2；

步驟C4：根據滿足約束條件和優化目標的染色體生成規劃方案，并輸出所述規劃方案。

在第一個方面的第三種可能實現方式中，所述步驟C1具體包括：

步驟C11：將所有子任務隨機進行排序，生成一個子任務列表；

步驟C12：對所述子任務列表中的子任務依次賦予優先級，得到與子任務列表相對應的子任務優先級序列；

步驟C13：將所有工作對象隨機進行排序，生成一個工作對象列表；

步驟C14：對所述工作對象列表中的工作對象依次賦予優先級，得到與工作對象列表相對應的工作對象優先級序列；

步驟C15：將所述子任務優先級序列和所述工作對象優先級序列組合成為初始染色體；

步驟C16：隨機選擇所述子任務列表中的兩個子任務，交換這兩個子任務的優先級，得到新的子任務優先級序列；

步驟C17：隨機選擇工作對象列表中的兩個工作對象，交換這兩個工作對象的優先級，得到新的工作對象優先級序列；

步驟C18：將步驟C16得到的新的子任務優先級序列與步驟C17得到的新的工作對象優先級序列組合成為新生成的染色體，將所述新生成的染色體保存至初始種群；