買專利賣專利找龍圖騰，真高效！ 查專利查商標用IPTOP,全免費！專利年費監控用IP管家,真方便！

龍圖騰網恭喜大連理工大學申請的專利一種用于工業4.0環境下車間作業調度問題的分布式Max-sum算法獲國家發明授權專利權，本發明授權專利權由國家知識產權局授予，授權公告號為：CN113469548B 。

龍圖騰網通過國家知識產權局官網在2025-04-15發布的發明授權授權公告中獲悉：該發明授權的專利申請號/專利號為：202110789792.5，技術領域涉及：G06Q10/0631；該發明授權一種用于工業4.0環境下車間作業調度問題的分布式Max-sum算法是由余祺;王宇涵;孫景昊設計研發完成，并于2021-07-13向國家知識產權局提交的專利申請。

本一種用于工業4.0環境下車間作業調度問題的分布式Max-sum算法在說明書摘要公布了：本發明公開了一種用于工業4.0中車間作業調度問題的分布式Max?sum算法，屬于車間作業調度技術領域。將分布式Max?sum算法應用至工業4.0環境下車間作業調度問題中，將車間作業調度問題中各操作的開始時間定義為變量節點，將目標函數和約束條件轉化為變量節點之間的約束函數并定義為函數節點。根據Max?sum算法的消息傳遞規則，在變量節點和函數節點之間進行消息傳遞，并不斷迭代。在達到收斂狀態或者迭代一定次數之后，確定各操作的開始時間，進而確定各操作的調度順序，在分布式環境中得到較優的調度結果。

本發明授權一種用于工業4.0環境下車間作業調度問題的分布式Max-sum算法在權利要求書中公布了：1.一種用于工業4.0環境下車間作業調度問題的方法，其特征在于，每臺機器依據局部信息進行分布式調度，確定每個操作作業的開始時間，最小化最大完成時間；該方法采用分布式Max-sum算法，包括以下步驟：步驟一，建立作業車間調度問題模型，作為模型的目標函數，最小化最大完成時間；數學模型如下：mint1式中，t表示最后一個作業最晚完成的時刻，即最大完成時間，min表示取最小值；步驟二，確定作業車間調度問題的約束條件；作業約束是指每個作業都包含一系列需要按順序執行的操作，操作時間固定且無法搶占；機器約束是指每臺機器在任一時刻最多只能處理一個操作，且每個操作只能在一臺機器上執行；數學模型如下：tij-tij-1≥pij-12t-tij≥pij3tij-thk≥phk∨thk-tij≥pij4式中，tij表示作業Ji的操作oij的開始時刻，tij-1表示作業Ji的操作oij-1的開始時刻，thk表示作業Jh的操作ohk的開始時刻，pij表示操作oij所用時間，pij-1表示操作oij-1所用時間，phk表示操作ohk所用時間；其中式2表示作業的一系列需要按順序執行，作業Ji的操作oij必須在前一個操作oij-1傳輸完成之后才能進行；式3表示最晚傳輸完成的時刻一定在所有操作都完成之后；式4表示每臺機器在任一時刻最多只能處理一個操作；如果操作oij和ohk在同一臺機器上處理，這兩個操作不沖突的約束條件為，操作oij在ohk開始之前完成傳輸或者操作ohk在oij開始之前完成傳輸；步驟三，將作業車間調度問題的約束條件轉化為Max-sum算法的函數節點Fj，將每個操作的開始時間作為變量節點xi；根據式1-式4所表示的優化目標和約束函數，將Max-sum算法應用到作業車間調度問題上；使用Max-sum算法進行調度就是確定每個操作的開始時間，從而使最大完工時間最小；把每個操作oij的開始時間tij作為變量節點xi，把開始時間之間的約束函數，即式2至式4，作為函數節點Fj，在變量節點和函數節點之間進行消息傳遞；數學模型表示如下： 式中，ftij,tij-1,t表示同一個作業的操作開始時間之間的先后次序約束；ftij,t表示最大完工時間和各操作開始時間之間的先后次序約束；atij,thk,t表示某一時刻同時占用同一機器的幾個操作開始時間之間的約束；步驟四，根據變量節點和函數節點構建因子圖；步驟五，根據因子圖運用Max-sum算法求解，不斷進行迭代，確定每個操作的開始時間，從而最小化最大完成時間；變量節點向函數節點傳遞q值，函數節點向變量節點傳遞r值；每次迭代消息計算規則如下：1從變量節點xi到函數節點Fj的消息傳遞規則： 式中，Mi表示與變量節點xi所關聯的所有函數節點下標的集合，Mi\j表示在集合中去掉j，αi,j表示使的調整值；rk→ixi表示與變量節點xi關聯的函數節點Fk向xi傳遞的消息；表示除掉函數節點Fj之外，所有關聯變量節點xi的函數節點向xi傳遞的消息之和；加上一個防止消息在循環因子圖中無限增加的調整值αi,j得到qi→jxi；2從函數節點Fj到變量節點xi的消息傳遞規則: 式中，Nj表示與函數節點Fj所關聯的所有變量節點下標的集合；Xj＝{xk：k∈Nj}，Xj\i＝{xk：k∈Nj\i}；FjXj表示函數節點Fj的約束表達式；表示除掉變量節點xi之外，函數節點Fj關聯的變量節點向Fj發送的消息之和；加上FjXj，并取最大值得到rj→ixi；rj→ixi表示與變量節點xi關聯的函數節點Fj向xi傳遞的消息；變量節點和函數節點進行消息傳遞后，計算傳遞到每個變量節點的r值之和，即變量節點的邊際值z值： 每個變量節點xi通過的計算，得到數值，并據此更新變量節點的值；根據迭代消息計算規則，不斷迭代計算節點之間傳遞的消息；按照下面的步驟進行迭代計算：1初始化所有節點之間的r值和q值為0；2當終止條件未滿足時，循環執行步驟3至步驟10；3對于Mi中下標指向的每個函數節點Fj；4計算rj→ixi；5函數節點Fj把r值傳遞到變量節點xi；6對于Nj中下標指向的每個變量節點xi；7計算qi→jxi；8變量節點xi把q值傳遞到函數節點Fj；9計算每個變量節點的zixi；10通過計算得到最優值，并更新xi的值；11直至結果收斂或迭代了一定的次數；12選擇使zixi最大的xi。

如需購買、轉讓、實施、許可或投資類似專利技術，可聯系本專利的申請人或專利權人大連理工大學，其通訊地址為：116024 遼寧省大連市甘井子區凌工路2號；或者聯系龍圖騰網官方客服，聯系龍圖騰網可撥打電話0551-65771310或微信搜索“龍圖騰網”。