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

龍圖騰網(wǎng)恭喜大連理工大學(xué)申請的專利一種用于工業(yè)4.0環(huán)境下車間作業(yè)調(diào)度問題的分布式Max-sum算法獲國家發(fā)明授權(quán)專利權(quán)，本發(fā)明授權(quán)專利權(quán)由國家知識產(chǎn)權(quán)局授予，授權(quán)公告號為：CN113469548B 。

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

本一種用于工業(yè)4.0環(huán)境下車間作業(yè)調(diào)度問題的分布式Max-sum算法在說明書摘要公布了：本發(fā)明公開了一種用于工業(yè)4.0中車間作業(yè)調(diào)度問題的分布式Max?sum算法，屬于車間作業(yè)調(diào)度技術(shù)領(lǐng)域。將分布式Max?sum算法應(yīng)用至工業(yè)4.0環(huán)境下車間作業(yè)調(diào)度問題中，將車間作業(yè)調(diào)度問題中各操作的開始時間定義為變量節(jié)點，將目標(biāo)函數(shù)和約束條件轉(zhuǎn)化為變量節(jié)點之間的約束函數(shù)并定義為函數(shù)節(jié)點。根據(jù)Max?sum算法的消息傳遞規(guī)則，在變量節(jié)點和函數(shù)節(jié)點之間進(jìn)行消息傳遞，并不斷迭代。在達(dá)到收斂狀態(tài)或者迭代一定次數(shù)之后，確定各操作的開始時間，進(jìn)而確定各操作的調(diào)度順序，在分布式環(huán)境中得到較優(yōu)的調(diào)度結(jié)果。

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

如需購買、轉(zhuǎn)讓、實施、許可或投資類似專利技術(shù)，可聯(lián)系本專利的申請人或?qū)＠麢?quán)人大連理工大學(xué)，其通訊地址為：116024 遼寧省大連市甘井子區(qū)凌工路2號；或者聯(lián)系龍圖騰網(wǎng)官方客服，聯(lián)系龍圖騰網(wǎng)可撥打電話0551-65771310或微信搜索“龍圖騰網(wǎng)”。