[發(fā)明專利]一種鄰域結(jié)構(gòu)及其在作業(yè)車間調(diào)度中的應(yīng)用

在審

• 申請?zhí)枺?/td>: 202010179254.X
• 申請日: 2020-03-15
• 公開（公告）號: CN111461504A
• 公開（公告）日: 2020-07-28
• 發(fā)明（設(shè)計）人: 李新宇;桂林;高亮
• 申請（專利權(quán)）人: 華中科技大學(xué)
• 主分類號: G06Q10/06
• 分類號: G06Q10/06
• 代理公司: 華中科技大學(xué)專利中心 42201
• 代理人: 徐美琳;李智

本發(fā)明公開了一種鄰域結(jié)構(gòu)及其在作業(yè)車間調(diào)度中的應(yīng)用，屬于車間調(diào)度領(lǐng)域，其中，一種鄰域結(jié)構(gòu)為：當(dāng)滿足約束條件C(u)≥C(jp[v])或S(v)≤S(js[u])時，關(guān)鍵路徑塊中的工序交換加工順序后不會產(chǎn)生不可行解；另一種鄰域結(jié)構(gòu)為：當(dāng)滿足約束條件C(u)≥S(jp[v])或S(v)≤C(js[u])時，關(guān)鍵路徑塊中的工序交換加工順序后不會產(chǎn)生不可行解。兩種鄰域結(jié)構(gòu)不需要消耗較大的計算資源，不會增加整個算法的編寫難度。兩種鄰域結(jié)構(gòu)應(yīng)用于作業(yè)車間調(diào)度時，在有效的提高算法的求解速度的同時，也提高了算法的求解質(zhì)量。

技術(shù)領(lǐng)域

本發(fā)明屬于車間調(diào)度領(lǐng)域，更具體地，涉及一種鄰域結(jié)構(gòu)及其在作業(yè)車間調(diào)度中的應(yīng)用。

背景技術(shù)

作業(yè)車間調(diào)度問題(job shop scheduling problem，JSP)是一種典型的車間調(diào)度問題，在生產(chǎn)實(shí)際中有具有廣泛的應(yīng)用。JSP是NP-hard問題，因此為了在有限時間里求得滿意解，通常使用智能優(yōu)化算法對該問題進(jìn)行求解。智能優(yōu)化算法主要由全局搜索和局部搜索兩部分組成，而鄰域結(jié)構(gòu)作為局部搜索的核心部分，對整個算法的求解效率和求解質(zhì)量起到關(guān)鍵性作用。

在現(xiàn)有技術(shù)中，對鄰域的設(shè)計主要有兩種類型。第一種類型是從編碼的角度設(shè)計鄰域操作，但由于編碼空間與問題解空間的不對等關(guān)系，以這種方式設(shè)計的鄰域的求解質(zhì)量不高；第二種類型是直接從解空間的角度設(shè)計鄰域結(jié)構(gòu)，通過分析解空間中存在的知識，設(shè)計高效的鄰域結(jié)構(gòu)。在解空間中存在的知識有：1、當(dāng)關(guān)鍵路徑中的工序沒有變化時，解不會變優(yōu)；2、關(guān)鍵路徑中相同機(jī)器加工的相鄰工序稱為關(guān)鍵路徑塊，當(dāng)關(guān)鍵路徑塊中的首工序和尾工序不發(fā)生變化時，解不會變優(yōu)。在以上兩點(diǎn)知識的基礎(chǔ)上，學(xué)者設(shè)計了若干種不同的鄰域結(jié)構(gòu)。但以這種方式設(shè)計的鄰域結(jié)構(gòu)存在鄰域變換后得到的解可能為不可行解的情況。

為解決這個問題，Balas等人在1998年(Balas E，Vazacopoulos A.Guided localsearch with shifting bottleneck for job shop scheduling[J].Managementscience，1998，44(2)：262-275.)提出一種鄰域結(jié)構(gòu)，在滿足約束條件的情況下進(jìn)行鄰域搜索，不會產(chǎn)生不可行解。其具體內(nèi)容為：當(dāng)滿足約束條件L(0，u)+p_u≥L(0，jp[V])+p_jp[v]時，關(guān)鍵路徑塊的非首工序插入首工序之前不會產(chǎn)生不可行解；當(dāng)滿足約束條件L(v，n)≥L(js[u]，n)時，關(guān)鍵路徑塊上的非尾工序插入尾工序之后不會產(chǎn)生不可行解。其中，上述約束條件中符號表示的含義如下：

u、v表示同一關(guān)鍵路徑塊上的兩個工序，且工序u在工序v之前加工；

js[i]：與工序i同工件的下一道工序；

jp[i]：與工序i同工件的上一道工序；

L(0，i)：從0時刻到工序i開始加工的總時長；

L(i，n)：從工序i開始加工到所有工件加工完的總時長；

p_i：工序i的加工時長。