[發明專利]一種基于博弈論的云制造多任務調度優化方法

有效

• 申請號: 201910933511.1
• 申請日: 2019-09-29
• 公開（公告）號: CN110751293B
• 公開（公告）日: 2022-04-15
• 發明（設計）人: 張帥;肖久紅;張文宇;朱長泰;何方
• 申請（專利權）人: 浙江財經大學
• 主分類號: G06N20/00
• 分類號: G06N20/00;G06Q10/04;G06Q10/06;G06Q50/04
• 代理公司: 杭州君度專利代理事務所(特殊普通合伙) 33240
• 代理人: 楊天嬌

本發明公開了一種基于博弈論的云制造多任務調度優化方法，包括：結合博弈論建立基于時間、成本和可靠性的CMMS博弈模型；初始化獲得棲息地，采用矩陣表示各棲息地；采用基于納什均衡的適應度函數計算各棲息地的棲息適宜性指數，根據棲息適宜性指數確定初始的最優解；根據遷入率和遷出率選擇棲息地執行遷移操作，更新最優解；根據變異率選取相應的棲息地進行變異操作，更新最優解；采用精英替換策略更新種群；若達到迭代次數，則輸出最優解，即最優的調度方案；否則繼續迭代。本發明基于博弈論提出了一種新的云制造多任務調度博弈模型，能夠獲得更好的調度方案，并且克服了基礎型BBO算法存在過早收斂、種群多樣性差的缺點。

技術領域

本申請屬于云制造任務調度技術領域，具體涉及一種基于博弈論的云制造多任務調度優化方法。

背景技術

云制造多任務調度(CMMS)問題是指隨時間的變化，調度可用的制造服務以完成各種制造任務，是一個組合優化問題。在過去十年中，許多研究都探索了單個制造任務的服務組合問題，但是并不適用于多任務調度問題的處理。此外，在部分文獻中提出的云制造多任務調度模型主要是實現所有任務組合目標的優化，以達到更好的云制造平臺性能。但在這種情況下，可能只有部分的制造任務以合理的成本和時間被可靠的服務所完成。

事實上，在以客戶為中心、以服務為導向的云制造平臺中，客戶期望提交的每一項制造任務都能以可靠的服務、合理的成本和時間來完成。然而，云制造平臺上要完成的制造任務不止一個，不同的制造任務之間可能存在沖突，這無疑給云制造多任務調度增加了難度。

并且制造任務數量的不斷增加使得CMMS問題成為了一個NP-hard問題(非確定性問題)。而元啟發式算法被廣泛應用于求解NP-hard問題，如遺傳算法、人工蜂群算法、粒子群優化算法、基于優先調度規則的啟發式算法等。近年來，Simon(2008)提出的生物地理學優化算法(BBO算法)在許多領域得到了廣泛的應用，且表現良好。但基礎型BBO算法存在著過早收斂的趨勢和種群多樣性差等缺點。因此，我們提出了一種改進型生物地理學優化算法以求解云制造多任務調度問題。

發明內容

本申請的目的在于提供一種基于博弈論的云制造多任務調度優化方法，該方法基于博弈論提出了一種新的云制造多任務調度博弈模型，能夠獲得更好的調度方案，并且克服了基礎型BBO算法存在過早收斂、種群多樣性差的缺點。

為實現上述目的，本申請所采取的技術方案為：

一種基于博弈論的云制造多任務調度優化方法，應用于云制造環境下多個任務和多個服務之間的調度，各任務包括多個子任務，所述基于博弈論的云制造多任務調度優化方法，包括：

步驟1：結合博弈論建立基于時間、成本和可靠性的CMMS博弈模型，包括：

以時間、成本和可靠性作為參與者收益的標準，建立參與者T_i的收益U_i作為CMMS博弈模型，所述收益U_i如下：

式中，參與者T_i即第i個任務，為偏好權重，且TCT_i表示完成第i個任務的總時間，TC_i表示完成第i個任務的總成本，TR_i表示完成第i個任務的總可靠性；

步驟2：采用BBO算法求解所述CMMS博弈模型，包括：

步驟2.1：初始化獲得CMMS博弈模型的解，即棲息地，并采用矩陣表示各棲息地；

步驟2.2：采用基于納什均衡的適應度函數計算各棲息地的棲息適宜性指數，根據所述棲息適宜性指數確定初始的最優解；其中，所述適應度函數為：

式中，表示棲息適宜性指數，I表示任務的總個數，表示第i個任務在第v個棲息地的收益值，表示第i個任務的完美收益值；