[發明專利]同順序流水線車間調度問題的樹搜索方法及裝置

有效

• 申請號: 201810064713.2
• 申請日: 2018-01-23
• 公開（公告）號: CN108446814B
• 公開（公告）日: 2020-12-01
• 發明（設計）人: 商秀芹;劉勝;王飛躍;袁勇;沈震;朱鳳華;荊思鳳;趙紅霞
• 申請（專利權）人: 中國科學院自動化研究所
• 主分類號: G06Q10/06
• 分類號: G06Q10/06;G06N20/00
• 代理公司: 北京市恒有知識產權代理事務所(普通合伙) 11576
• 代理人: 郭文浩

本發明屬于流水線車間調度領域，具體涉及一種同順序流水線車間調度的樹搜索方法及裝置。旨在解決同順序流水線車間的優化調度問題。首先采用NEH算法求得初始解，然后結合樹搜索方法將正向搜索和逆向搜索作為一個父結點的兩個分支，分別尋優，并與父節點比較，得到正向最優解和逆向最優解，即為生成的兩個子結點。通過上述方式構建樹形結構，實現同順序流水車間的優化調度。與現有技術相比，本發明縮短了最大完工時間，且該算法為確定性算法，求解結果為確定穩定解。

技術領域

本發明屬于流水線車間調度領域，具體涉及一種同順序流水線車間調度問題的樹搜索方法及裝置。

背景技術

流水線車間調度問題是一個交叉性研究領域，涉及運籌學，管理學，自動化，計算機等領域。流水線車間調度問題的研究可以幫助企業提高生產效率，增強生產的柔性和可靠性，對先進制造和智能制造有重要研究意義。

流水線車間調度問題一般屬于為NP完全問題，目標解的搜索涉及解空間的組合爆炸。目前的求解方法主要有禁忌搜索算法、模擬退火算法、蟻群算法、粒子群算法等。上述算法主要采用元啟發式算法，算法本身帶有隨機性，有時結果不可復現，具有不穩定性，且在計算機上運算時間較長。

發明內容

為了解決現有技術中的上述問題，即為了解決同順序流水線車間優化調度問題，本發明的一方面，提出了一種同順序流水線車間調度問題的樹搜索方法，包括以下步驟：

步驟S1：采用啟發式算法求解同順序流水線車間調度的初始解，作為第一次搜索的當前結點；

步驟S2：基于正向搜索方法得到當前結點的正向子結點，基于逆向搜索方法得到當前結點的逆向子結點，構建二叉搜索樹；

步驟S3：判斷當前子結點有無祖結點，若當前子結點有祖結點，則執行步驟S4，否則分別以新生成的正向子結點、逆向子結點作為當前結點執行步驟S2；

步驟S4：若當前結點的正向子結點、逆向子結點、祖結點不相等，則返回步驟S2，否則以三者的值為最優解，樹搜索結束；

所述祖結點為當前子結點的上兩級結點。

優選地，所述步驟S1，具體為：依據同順序流水線車間調度中工件數n、加工工件所需的機器數m和所有工件在每一個機器上所需加工的時間p_i,j,i＝1,2,...,m,j＝1,2,...,n,采用啟發式算法求解同順序流水線車間調度工件的初始解，作為第一次搜索的當前結點。

優選地，所述啟發式算法為NEH算法。

優選地，所述初始解為同順序流水線車間調度的最小的最大完工時間。

優選地，所述正向搜索方法，具體為：對當前結點中每一個工件依次從前向后移動到所有可能的位置，得到(n^-1)！個排列組合，計算所有排列組合中的最大完工時間，選出最小值作為正向較優解；

將所述正向較優解與其父結點比較，若所述正向較優解小于或等于其父結點的值，則以所述正向較優解為本次搜索的正向子結點，否則以所述正向較優解的父結點為本次搜索的正向子結點。

優選地，所述逆向搜索方法，具體為：對當前結點中每一個工件依次從后向前移動到所有可能的位置，得到(n^-1)！個排列組合，計算所有排列組合中的最大完工時間，選出最小值作為逆向較優解；

將所述逆向較優解與其父結點比較，若所述逆向較優解小于或等于其父結點的值，則以所述逆向較優解為本次搜索的逆向子結點，否則以所述逆向較優解的父結點為本次搜索的逆向子結點。

本發明的另一方面，還提出了一種同順序流水線車間調度問題的樹搜索裝置，

啟發式算法求解模塊：用于利用啟發式算法求解同順序流水線車間調度的初始解，作為第一次搜索的當前結點；