一種基於MCTS的「雲邊」協同預測反應式調度方法

2024-04-16 00:06:05

一種基於mcts的「雲邊」協同預測反應式調度方法
技術領域
1.本發明涉及技術領域，具體而言，尤其涉及一種基於mcts的「雲邊」協同預測反應式調度方法。


背景技術：

2.生產質量和效率是製造業的重中之重，一個企業必須要保證生產過程的平穩優化，才能在激烈的市場競爭中立足。大部分關於調度的文獻都忽略生產過程中出現的擾動，較少考慮動態不確定因素。然而，在實際生產過程中，加工時間的不確定性可能導致原有基礎生產調度方案失效。而且加工時間擾動時會對生產過程產生許多不良影響，使得動態調度問題比靜態調度問題更加複雜。
3.儘管目前存在動態調度的相關研究，但現在的研究很少考慮調度方案切換時所帶來的切換成本。在實際生產過程中，切換調度方案帶來切換成本難以忽略，企業需要儘可能減少切換調度方案所帶來的切換成本。而且原有基礎生產調度方案和切換調度之間也存在聯繫。在產生擾動時進行的切換，需要使切換成本儘可能小，所以在選擇基礎調度方案時要綜合考慮基礎調度成本和切換調度時的切換成本。因此，需要通過對生產製造過程的分析，在綜合考慮工藝約束和不確定加工時間的基礎上，對生產訂單進行調度優化後形成預測的基礎調度方案，當生產過程中發生不確定加工時間擾動時，反應式切換生產調度方案，從而形成預測-反應式調度方法，以保證生產過程的平穩優化。


技術實現要素：

4.根據上述背景技術提到的技術問題，而提供一種基於mcts的「雲邊」協同預測反應式調度方法。
5.本發明採用的技術手段如下：
6.一種基於mcts的「雲邊」協同預測反應式調度方法，其中，「雲」側系統包括：具有歷史數據分析模塊、生產任務處理模塊以及調度方案池生成模塊的預測調度方案模塊和調度方案池；
[0007]「邊」側系統包括：基礎調度獲取模塊、衝突判斷和反饋模塊、備選方案切換模塊以及可行方案快速生成模塊；
[0008]
包括以下步驟：
[0009]
步驟1：構建生產製造過程中，針對不確定加工時間問題的調度方案池，調度方案池生成模塊根據歷史數據分析模塊和生產任務處理模塊的結果數據生成調度方案池；
[0010]
步驟2：基礎調度獲取模塊在調度方案池中選擇最優調度方案，同時，定義所述最優調度方案為基礎調度方案；同時，在生產調度過程中，通過衝突判斷與反饋模塊進行對設備運行的實時監測；
[0011]
當基礎調度方案可行時，即採用基礎調度方案；如果產生衝突，則向「雲」側發送請求，在所述調度方案池中分析是否存在可行備選切換調度方案；如果存在則執行步驟3，不
存在則執行步驟4；
[0012]
步驟3：在調度方案池中提取可行最優備選調度方案，將該方案下達給設備進行執行；
[0013]
步驟4：通過可行方案快速生成模塊，根據當前執行情況和待加工信息重新快速生成可行調度方案並將該調度方案和衝突信息傳送給「雲」側的調度方案池生成模塊，根據該信息更新調度方案池。
[0014]
較現有技術相比，本發明具有以下優點：
[0015]
1、本發明利用預測-反應式調度所包含的預測調度和反應式調度兩個部分，在預測調度部分實現考慮在不確定因素前提下生成並拓展蒙特卡洛樹的方法，據此制定多種生產調度方案，最終形成調度方案池。解決了生產調度遇到了不確定加工時間的遭遇衝突時所造成的切換調度方案時間長、切換成本難控制的問題，保證了生產過程的平穩優化。
[0016]
2、本發明將「雲邊」協同與預測-反應式調度有機結合，基於「雲邊」協同框架，充分發揮「雲」側高性能的計算資源，以及「邊」側快速響應、密切連接的決策管理的綜合作用，實現了「雲邊」協同的跨層調度與綜合優化。
[0017]
3、本發明利用蒙特卡洛樹搜索結合了廣度優先搜索和深度優先搜索和運用模擬方法快速得到方案評估值的特性，將該方法從求解棋類博弈問題推廣到了求解不確定加工時間預測反應式調度問題，提供了改進的蒙特卡洛樹搜索方法。在綜合考慮工藝約束和不確定加工時間的基礎上，對生產訂單進行調度優化後形成預測基礎調度方案、多種備選調度方案和切換策略，滿足了不確定加工時間的動態車間對生產平穩性的要求。
[0018]
綜上，本發明的技術方案解決了現有技術中的遭遇衝突時切換調度方案時間長、切換總成本難控制的問題，針對計算資源分布式部署需求和加工時間不確定等實際問題特點，提出了基於改進的蒙特卡洛樹搜索的「雲邊」協同的預測-反應式調度方法。
附圖說明
[0019]
為了更清楚地說明本發明實施例或現有技術中的技術方案，下面將對實施例或現有技術描述中所需要使用的附圖做以簡單地介紹，顯而易見地，下面描述中的附圖是本發明的一些實施例，對於本領域普通技術人員來講，在不付出創造性勞動性的前提下，還可以根據這些附圖獲得其他的附圖。
[0020]
圖1為本發明構建的一種基於mcts的工業過程「雲邊」協同預測反應式調度方法的基本架構圖；
[0021]
圖2為本發明生產任務信息示意圖；
[0022]
圖3為本發明生成蒙特卡洛樹算法流程圖；
[0023]
圖4為本發明蒙特卡洛樹樹狀算法結構圖；
[0024]
圖5為本發明調度方案池形式及狀態表示圖；
[0025]
圖6為本發明切換算法流程圖；
[0026]
圖7為本發明備選方案切換模塊結果示意圖。
[0027]
圖8為本發明整體系統示意圖。
具體實施方式
[0028]
為了使本技術領域的人員更好地理解本發明方案，下面將結合本發明實施例中的附圖，對本發明實施例中的技術方案進行清楚、完整地描述，顯然，所描述的實施例僅僅是本發明一部分的實施例，而不是全部的實施例。基於本發明中的實施例，本領域普通技術人員在沒有做出創造性勞動前提下所獲得的所有其他實施例，都應當屬於本發明保護的範圍。
[0029]
需要說明的是，本發明的說明書和權利要求書及上述附圖中的術語「第一」、「第二」等是用於區別類似的對象，而不必用於描述特定的順序或先後次序。應該理解這樣使用的數據在適當情況下可以互換，以便這裡描述的本發明的實施例能夠以除了在這裡圖示或描述的那些以外的順序實施。此外，術語「包括」和「具有」以及他們的任何變形，意圖在於覆蓋不排他的包含，例如，包含了一系列步驟或單元的過程、方法、系統、產品或設備不必限於清楚地列出的那些步驟或單元，而是可包括沒有清楚地列出的或對於這些過程、方法、產品或設備固有的其它步驟或單元。
[0030]
如圖1-8所示，本發明提供了一種基於mcts的「雲邊」協同預測反應式調度方法其中，「雲」側系統包括：具有歷史數據分析模塊、生產任務處理模塊以及調度方案池生成模塊的預測調度方案模塊和調度方案池；
[0031]「邊」側系統包括：基礎調度獲取模塊、衝突判斷和反饋模塊、備選方案切換模塊以及可行方案快速生成模塊；
[0032]
步驟1：構建生產製造過程中，針對不確定加工時間問題的調度方案池，調度方案池生成模塊根據歷史數據分析模塊和生產任務處理模塊的結果數據生成調度方案池。
[0033]
步驟1-1：在歷史數據分析模塊中，加載生產各個工序的歷史生產數據，並對歷史加工時間數據進行預處理，即利用均值替換法來填補缺失值、利用滑動平均法來光滑噪聲數據、利用半徑濾波法來識別或刪除離群點，達到異常數據和重複數據的清除的目的；
[0034]
步驟1-2：利用最小二乘法對各個工序的歷史數據進行擬合，得到該數據的分布和統計特性，如二項分布、幾何分布、超幾何分布、多項分布、負二項分布、泊松分布等離散概率概率分布，並得到該數據對應分布的概率分布函數；；
[0035]
步驟1-3：將不確定加工時間的離散概率分布傳遞給生產任務處理模塊和調度方案池生成模塊；通過生產任務處理模塊加載新的生產任務數據；其中，所述生產任務處理模塊包括：生產任務信息和製造資源信息；
[0036]
步驟1-4：結合歷史數據分析模塊的結果，獲取生產工藝約束、工序加工時間區間和工序可用設備集信息；
[0037]
步驟1-5：根據調度方案池生成模塊的需求實現對結果數據信息的存儲和備份，並將所述結果數據傳輸到調度方案池生成模塊；
[0038]
步驟1-6：在調度方案池生成模塊中，基於蒙特卡洛樹搜索生成完整調度方案；
[0039]
步驟1-7：以蒙特卡洛樹形式存儲所述調度方案池；所述調度方案從根節點向下移動，即可形成一個完整調度方案s0-》s12-》s22-》s33；所述蒙特卡洛樹的節點狀態包括：工序編號、工序開始時間區間及工序的機器分配。
[0040]
作為一種優選的實施方式，在本技術中，步驟1-6還包含以下步驟：
[0041]
步驟1-6-1：起點：蒙特卡洛樹從根節點(如圖4中s0節點所示)開始搜索。
[0042]
步驟1-6-2：選擇：如圖4選擇步驟所示，從根節點(s0)開始，向下遞歸使用upper confidence bounds(ucb)函數選擇最具有潛力的子節點(s12)，將該子節點狀態添加到調度方案中，直至選擇到非終端葉子節點(s22)。
[0043][0044]
其中是節點估計的值，ni是節點被訪問的次數，而n則是其父節點已經被訪問的總次數，c是可調整參數。
[0045]
步驟1-6-3：擴展：如圖4擴展步驟所示，如果當前葉子節點不是終端葉子節點，則在該葉子節點(s22)上選擇所有未擴展的可開始的工單工序，並根據其所有祖先節點的開始和結束時間區間，確定該工序可開始的時間範圍。將該工序編號、開始時間和分配的機器定為新狀態(s31、s32、s33、s34)，並將其指向的節點添加到搜索樹中。
[0046]
步驟1-6-4：模擬：對新拓展的節點(s31/s32/s33/s34)向下，對所有未選擇過的工單工序向當前調度方案中添加未選擇過的工序並利用啟發式方法進行排序，從而形成完整調度方案(s31～sn1/s32～sn2/
[0047]
s33～sn3/s34～sn4)，並根據該調度順序得出該方案的調度成本。調度成本由生產加工成本、切換方案成本和無切換調度方案成本組成。此外在模擬過程中還會利用歷史狀態表的結果減少模擬次數以達到同樣的模擬效果。
[0048]
步驟1-6-5：狀態優化：如圖4狀態優化步驟所示，當節點(s31、s32、s33、s34)都被擴展後，進行狀態開始時間區間的縮減。比較同一機器中每個工單工序的狀態區間，對可縮小狀態進行縮小狀態開始時間成本的處理，使其達到覆蓋範圍和成本的總體目標最優，狀態更改為(s31』、s32、s33、s34』)。
[0049]
步驟1-6-6：子樹修剪：如圖4子樹修剪步驟所示，蒙特卡洛樹搜索的過程中，同一父節點的子樹中只保留結果最好的n個子樹，並將其他子節點(如s33)剪掉，以使計算量集中在最優可能子樹中；蒙特卡洛樹搜索的過程中，同一父節點的子樹中只保留結果最好的n個子樹，並將其他子節點剪掉，以使計算量集中在最優可能子樹中；
[0050]
步驟1-6-7：記錄歷史狀態：為了充分利用蒙特卡洛樹先前模擬的結果信息，將這些歷史狀態信息記錄在歷史狀態表中。歷史狀態表記錄了到目前為止所執行過的狀態及其評估值和訪問次數等信息，用於減少模擬次數。
[0051]
步驟1-6-8：反向傳播：如圖4反向傳播步驟所示，新擴展節點(s31』、s32、s34』)模擬得出的調度成本反向傳播到從新節點到根節點的每一個經由節點上(s12、s0)，反向傳播的調度成本將會影響選擇策略，並且反向傳播經過的節點會根據反向傳播的調度成本更新該節點的評估值和訪問次數。
[0052]
步驟1-6-9：重複步驟1-6-2到步驟1-6-8的，直到達到迭代次數且生成一千個完整調度方案。該蒙特卡洛樹記為調度方案池，為整體預測-反應式調度提供基礎調度方案和備選切換調度方案。
[0053]
優選地，步驟2：基礎調度獲取模塊在調度方案池中選擇最優調度方案，同時，定義所述最優調度方案為基礎調度方案；同時，在生產調度過程中，通過衝突判斷與反饋模塊進行對設備運行的實時監測；所述調度方案池包括：蒙特卡洛樹形式存儲的調度方案、下發調
度方案方法以及選擇調度方案方法。
[0054]
當基礎調度方案可行時，即採用基礎調度方案；如果產生衝突，則向「雲」側發送請求，在所述調度方案池中分析是否存在可行備選切換調度方案；如果存在則執行步驟3，不存在則執行步驟4。
[0055]
所述步驟2還包括以下步驟：
[0056]
步驟2-1：所述基礎調度獲取模塊向「雲」側發送請求；在調度方案池中遍歷以蒙特卡洛樹為形式的調度方案池的所有最終層葉子節點，找到全局最優完整調度；並從該葉子節點向上回溯，形成完整調度方案，將其定為基礎調度，並下發給「邊」側系統交給設備執行；
[0057]
步驟2-2：在生產調度中，衝突判斷和反饋模塊用於實時監測生產過程，並判斷此刻當前調度方案能否繼續進行；如果不存在衝突，即當前調度方案可行，則繼續執行調度方案；否則執行步驟2-3；
[0058]
步驟2-3：判斷是否存在可行備選調度方案，如果存在可行備選調度，則調用備選方案切換模塊，在遭遇衝突時有可行備選方案的情況下，調用備選方案切換模塊；接收衝突判斷和反饋模塊的衝突信息，將生產實績反饋給「雲」側系統，並向「雲」側發送請求；否則執行步驟2-4；
[0059]
步驟2-4：調用可行方案快速生成模塊，並將衝突信息傳送給對應模塊；首先接收衝突判斷和反饋模塊的反饋的衝突信息，之後根據已完成的工單工序開始時間、加工時間、機器分配以及待開始的工單工序信息，通過啟發式算法快速生成調度方案，下發給設備端執行；同時將生產實績反饋給「雲」側系統的調度方案池生成模塊，更新調度方案池，此後生產調度按更新後的調度方案池執行。
[0060]
步驟3：在調度方案池中提取可行最優備選調度方案，將該方案下達給設備進行執行；
[0061]
步驟4：通過可行方案快速生成模塊，根據當前執行情況和待加工信息重新快速生成可行調度方案並將該調度方案和衝突信息傳送給「雲」側的調度方案池生成模塊，根據該信息更新調度方案池。
[0062]
上述本發明實施例序號僅僅為了描述，不代表實施例的優劣。
[0063]
在本發明的上述實施例中，對各個實施例的描述都各有側重，某個實施例中沒有詳述的部分，可以參見其他實施例的相關描述。
[0064]
在本技術所提供的幾個實施例中，應該理解到，所揭露的技術內容，可通過其它的方式實現。其中，以上所描述的裝置實施例僅僅是示意性的，例如所述單元的劃分，可以為一種邏輯功能劃分，實際實現時可以有另外的劃分方式，例如多個單元或組件可以結合或者可以集成到另一個系統，或一些特徵可以忽略，或不執行。另一點，所顯示或討論的相互之間的耦合或直接耦合或通信連接可以是通過一些接口，單元或模塊的間接耦合或通信連接，可以是電性或其它的形式。
[0065]
所述作為分離部件說明的單元可以是或者也可以不是物理上分開的，作為單元顯示的部件可以是或者也可以不是物理單元，即可以位於一個地方，或者也可以分布到多個單元上。可以根據實際的需要選擇其中的部分或者全部單元來實現本實施例方案的目的。
[0066]
另外，在本發明各個實施例中的各功能單元可以集成在一個處理單元中，也可以
是各個單元單獨物理存在，也可以兩個或兩個以上單元集成在一個單元中。上述集成的單元既可以採用硬體的形式實現，也可以採用軟體功能單元的形式實現。
[0067]
所述集成的單元如果以軟體功能單元的形式實現並作為獨立的產品銷售或使用時，可以存儲在一個計算機可讀取存儲介質中。基於這樣的理解，本發明的技術方案本質上或者說對現有技術做出貢獻的部分或者該技術方案的全部或部分可以以軟體產品的形式體現出來，該計算機軟體產品存儲在一個存儲介質中，包括若干指令用以使得一臺計算機設備(可為個人計算機、伺服器或者網絡設備等)執行本發明各個實施例所述方法的全部或部分步驟。而前述的存儲介質包括：u盤、只讀存儲器(rom，read-only memory)、隨機存取存儲器(ram，random access memory)、移動硬碟、磁碟或者光碟等各種可以存儲程序代碼的介質。
[0068]
最後應說明的是：以上各實施例僅用以說明本發明的技術方案，而非對其限制；儘管參照前述各實施例對本發明進行了詳細的說明，本領域的普通技術人員應當理解：其依然可以對前述各實施例所記載的技術方案進行修改，或者對其中部分或者全部技術特徵進行等同替換；而這些修改或者替換，並不使相應技術方案的本質脫離本發明各實施例技術方案的範圍。