[發明專利]一種用于多技能資源受限項目調度的進化策略算法

在審

• 申請號: 202011001300.3
• 申請日: 2020-09-22
• 公開（公告）號: CN112148446A
• 公開（公告）日: 2020-12-29
• 發明（設計）人: 熊體凡;田源;劉振元;高鑫浩;吳航
• 申請（專利權）人: 華中科技大學
• 主分類號: G06F9/48
• 分類號: G06F9/48;G06F9/50;G06N3/00
• 代理公司: 北京金智普華知識產權代理有限公司 11401
• 代理人: 楊采良

本發明公開了一種用于多技能資源受限項目調度的進化策略算法，包括設置算法參數及初始化變量、初始化種群、對種群中的個體執行變異操作、評估種群適應度、更新帕累托種群、選擇下一代的父代種群、判斷是否滿足迭代的終止條件，若滿足條件，則終止程序并輸出帕累托種群等步驟；本發明進一步考慮了資源在使用不同技能時的切換情況，更切合實際的應用場景。新的個體編碼結構僅表示任務的資源指派，減少搜索空間。新的計劃生成方案，采用貪婪策略，將任務分為兩個集合依次安排其開始時間，并盡量減少不必要的技能切換，使得生成的調度方案的工期和成本大大減少。在解集的延展性、多樣性和收斂性上好于目前已有的同類算法。

技術領域

本發明涉及智能優化算法技術領域，尤其涉及一種用于考慮技能切換背景下多技能資源受限項目調度的進化策略算法。

背景技術

資源受限項目調度(Resource Constrained Project Scheduling Problem，RCPSP)是運籌學和項目管理中最經典的組合優化問題。最基本的RCPSP問題研究在資源有限的情況下，安排各任務的開始時間，并且滿足資源用量上限及任務間的緊前約束。問題的目標函數常為項目的工期類指標或成本類指標最短。資源受限項目調度問題并不能完全適用于各類實際場景中。

多技能資源受限項目調度問題(Multi-skill Resource Constrained ProjectScheduling Problem，MS-RCPSP)是RCPSP的一類擴展問題。相較于RCPSP中假設的同質化資源，該問題假設資源具有一種(或多種)技能，不同的任務需要由具有特定技能的資源完成。這類問題常用于人力資源調度或柔性制造車間中。考慮技能的人力資源調度常見于復雜產品的眾包研發或軟件開發行業中，任務的技能需求差異較大，需要由具有該技能的人員完成。在柔性制造車間中，工件的某道工序可由具備加工條件的某個機器完成。

求解調度類問題的方法大體可分為精確式算法(Exact Algorithm)、啟發式算法(Heuristics)和智能優化算法(Intelligent Optimization Algorithm)三大類。精確式算法以分支定界算法為主，可以求得問題的最優解，但可求解的問題規模小，面對實際應用中的大規模問題顯得無能為力。啟發式算法基于優先規則(Priority Rule,PR)和計劃生成方案(Schedule Generator Scheme，SGS)。其生成的解的質量極大地依賴于優先規則的設計和選取。針對不同的實際問題，往往所適用的最佳規則也有所不同。智能優化算法以隨機搜索為基礎，利用計算機強大運算能力嘗試在有限的時間內尋找較優的解。這類算法的設計思路簡單，且能夠求解的問題廣泛。常見的智能優化算法有遺傳算法(GeneticAlgorithm)、模擬退火(Simulated Annealing)、粒子群算法(Particle SwarmOptimization)等。科研人員也常在這些經典的算法上，對某些執行步驟進行細微的改進，設計出新的算法。一般而而言，智能優化算法包含以下要素：(1)編碼，按照某種對應規則與調度生成計劃相對應的一組代碼；(2)解碼，采用一定規則將編碼轉換為可行的調度方案；(3)初始解，采用其他方法得到的一組編碼，對應初始的可行調度方案；(4)鄰域解，一組編碼經過鄰域搜索算子(local search operator)得到的所有新的編碼的集合。

目前已有的多技能資源受限項目調度問題及算法存在以下不足：

1)在多技能受限項目調度中，大部分的調度問題假設資源在不同技能間切換是不需要花費時間的，但在實際應用中，技能的切換所花費的時間往往也較為可觀。如員工在執行不同技能類型的任務時，需要做些準備工作，如前往不同配置的工作臺，獲取適合的工具等。在制造車間中，加工不同要求的工件可能意為著更換不同類型的刀具、原料或者夾緊裝置。上述的這些操作都會花費額外的時間，且頻繁的切換會延長項目的完成時間。因此，合理地安排資源上任務的執行順序也顯得尤為重要。