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

龍圖騰網恭喜聊城大學申請的專利混合流水車間必經工序有效位置插入的快速局部搜索方法獲國家發明授權專利權，本發明授權專利權由國家知識產權局授予，授權公告號為：CN118710026B 。

龍圖騰網通過國家知識產權局官網在2025-04-04發布的發明授權授權公告中獲悉：該發明授權的專利申請號/專利號為：202411194605.9，技術領域涉及：G06Q10/0631；該發明授權混合流水車間必經工序有效位置插入的快速局部搜索方法是由韓玉艷;王宇航;王玉亭;李寰;張彪;賈保憲設計研發完成，并于2024-08-29向國家知識產權局提交的專利申請。

本混合流水車間必經工序有效位置插入的快速局部搜索方法在說明書摘要公布了：本發明公開了一種混合流水車間必經工序有效位置插入的快速局部搜索方法，通過調度方案的解空間表示，初始化過程，使用局部搜索方法，整個搜索過程中僅考慮必經工序的插入方法。本發明一方面通過減少移動工序的個數和插入位置的次數，有效避免了工序的無效移動，另一方面通過快速評價方法計算移動工序后的最大完工時間，節約了計算成本，提高了優化調度效率。

本發明授權混合流水車間必經工序有效位置插入的快速局部搜索方法在權利要求書中公布了：1.一種混合流水車間必經工序有效位置插入的快速局部搜索方法，其特征在于，包括以下步驟：步驟1：獲取調度方案在解空間中的表示；步驟2：初始化過程，令局部搜索之后的最大完工時間等于局部搜索之前的最大完工時間，改進的標記參數等于；步驟3：如果等于，則局部搜索方法結束并輸出，否則，執行步驟4；步驟4：將設置為，然后從調度方案中獲取必經工序集；步驟5：依次刪除其中一個必經工序，為該工序尋找有效插入位置，在插入過程中，采用快速評價方法計算從第一個工序到最后一個工序經過該必經工序的最長路徑，記錄使最小的位置；步驟6：如果小于，將該必經工序插入到使最小的位置，更新所有工序的完工時間和逆向完工時間，重新計算，并更新為，再執行步驟3；步驟7：如果大于等于，將該必經工序插入到原位置，執行步驟3；所述步驟1中的解空間的表示為：混合流水車間中個工件的處理過程按照相同的順序依次經過相同的個工序的處理，每個階段都有個并行機器處理工序；混合流水車間其中一個調度方案定義為：對每一個工序，在階段確定唯一的機器（）處理該工序，并確定每個機器上的工序的處理順序，其中，為工件的數量，為階段的數量，為工件的索引,，為階段的索引,，為階段中并行機器的集合,，為階段中的第臺并行機器，=，為工件在階段的工序；在解空間中，每個節點對應一個工序，每個節點的權重等于該節點對應工序的加工時間，每個階段引入兩個虛擬工序和，分別代表每個階段所有機器加工的開始和結束，所有虛擬工序的加工時間為，此外，引入兩個虛擬階段，分別為階段0和階段，所有工件必須先經過階段0的處理，然后經過正常階段的處理，最后經過階段的處理，每個工件在兩個虛擬階段的虛擬工序分別為和，加工時間均為0；對于同一非虛擬階段上的操作和；如果且是的直接后繼，則和之間存在兩條弧線；如果是機器上的第一個操作，則和之間存在兩條弧線；如果是機器上的最后一個操作，則和之間存在兩條弧線；在解空間中完成正向完工時間和逆向完工時間的方法為：對于非虛擬階段所有虛擬工序，令=0，，對于虛擬階段的所有虛擬工序，令，，在解空間中，每一個非虛擬工序有四條入弧、、和，根據和得到工序的正向完工時間，根據和得到工序的逆向完工時間；在完成正向完工時間和逆向完工時間的計算后，確定調度方案的最大完工時間，記為；所述步驟4中的從調度方案中獲取必經工序集的方法為：確定調度方案的解空間子集：基于解空間子集獲得必經工序集；對于非虛擬工序，如果，工序為解空間的關鍵工序，在解空間中，由節點、和解空間的關鍵工序節點，以及和以上節點相關的弧構成的子集為解空間子集，記為，所有工序的連續操作之間沒有間隙；所述基于解空間子集獲得必經工序集，執行為：步驟4.1：令必經工序集合為空，設置時間戳為1；步驟4.2：對解空間子集中的每個操作，設置和為0，對解空間子集中的每條邊，設置訪問標記為0，構造一個棧，存儲當前節點和其父節點的節點對；步驟4.3：從工序進行深度優先搜索，對于工序，設置和為當前的時間戳，將時間戳加1，將節點對進棧，表示沒有父節點；步驟4.4：如果棧不為空，執行步驟5，否則執行步驟9；步驟4.5：從棧頂取出一對節點，為當前節點，為父節點；步驟4.6：尋找一條以當前節點為起點不以父節點為終點的訪問標記為0的邊；步驟4.7：若找到步驟4.6中的邊，記該邊為，設置其訪問標記為1，如果discovery[]等于0，則設置和為當前的時間戳，將時間戳加1，并將節點對進棧，否則設置等于，執行步驟4.4；步驟4.8：若沒有找到步驟4.6中的邊，則出棧，如果棧不為空、和不是同一個節點和小于等于三個條件同時滿足，則為一個必經工序，將其并入必經工序集，設置等于，執行步驟4.4；步驟4.9：基于關鍵子圖獲得必經工序集方法結束，輸出必經工序集輸出必經工序集；所述步驟5中的刪除其中一個必經工序，將其重新插入其他位置后判斷最大完工時間是否變小的快速評價方法，執行為：記為要刪除并重新插入的必經工序，的原加工機器為，刪除必經工序之后的最大完工時間記為，，重新插入工序后的最大完工時間記為，則；該為重新插入工序后，調度方案圖中從到經過的所有路徑中最長路徑的長度；已知，則，進而判斷刪除某個必經工序將其重新插入其他位置后最大完工時間變優；在刪除后，在機器上，原位置之后的工序的正向完工時間和原位置之前的工序的逆向完工時間發生變化并進行更新；在中除之外的機器上，工序的完工時間和逆向完工時間不會發生變化；完成所述更新后在每個位置插入時，記插入位置前后的工序分別為和，則等于；所述步驟5中刪除其中一個必經工序，將其重新插入時有效位置的策略，執行為：記為要刪除并重新插入的必經工序，的原加工機器為，在機器上，更新原位置之后的工序的正向完工時間和原位置之前的工序的逆向完工時間；往調度方案圖中中重新插入時，以插入的機器為，記機器上加工的工序數為，則在機器共有位置插入，每一個位置的編號用表示，；機器上，位置前后工序記為和，位置前后工序對應的工件編號分別記為和，如果，則，表示為虛擬工序，如果，則，表示為虛擬工序，機器上從右往左第一個滿足的位置記為，即，機器上從左往右第一個滿足的位置記為，即。

如需購買、轉讓、實施、許可或投資類似專利技術，可聯系本專利的申請人或專利權人聊城大學，其通訊地址為：252000 山東省聊城市東昌府區湖南路1號；或者聯系龍圖騰網官方客服，聯系龍圖騰網可撥打電話0551-65771310或微信搜索“龍圖騰網”。