[發(fā)明專利]基于不等量二分法的開放車間調(diào)度問題關(guān)鍵操作識(shí)別方法

有效

• 申請(qǐng)?zhí)枺?/td>: 201310013375.7
• 申請(qǐng)日: 2013-01-15
• 公開（公告）號(hào): CN103093311A
• 公開（公告）日: 2013-05-08
• 發(fā)明（設(shè)計(jì)）人: 王軍強(qiáng);郭銀洲;王爍;崔福東;張承武;楊宏安;張映鋒;孫樹棟
• 申請(qǐng)（專利權(quán)）人: 西北工業(yè)大學(xué)
• 主分類號(hào): G06Q10/06
• 分類號(hào): G06Q10/06
• 代理公司: 西北工業(yè)大學(xué)專利中心 61204
• 代理人: 陳星

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

本發(fā)明涉及開放車間中關(guān)鍵操作識(shí)別問題，具體為一種基于不等量二分法的開放車間調(diào)度問題關(guān)鍵操作識(shí)別方法。

背景技術(shù)

開放車間的定義可描述為：給定n個(gè)工件的工件集合J＝{1,2,...,n}，具有m個(gè)機(jī)器的機(jī)器集合M＝{1,2,...,m}，定義工件在一個(gè)機(jī)器上加工稱為一道工序，則工件的工序之間無順序約束。任意時(shí)刻，任意工件i∈J同時(shí)最多只能在一個(gè)機(jī)器進(jìn)行加工，任意機(jī)器j∈M同一時(shí)間只能加工一個(gè)工件，此類問題屬于開放車間調(diào)度問題（Open-shop?Scheduling?Problem,OSP）。

關(guān)鍵操作指的是對(duì)整個(gè)開放車間調(diào)度方案影響最大的操作，關(guān)鍵操作包含關(guān)鍵工件、關(guān)鍵工序和關(guān)鍵機(jī)器，標(biāo)記關(guān)鍵操作集合為O^*，關(guān)鍵工件集合為J^*，關(guān)鍵機(jī)器集合為M^*，關(guān)鍵工序集合為P^*，則有O^*＝{J^*,M^*,P^*}。

OSP的顯著特點(diǎn)是工件、機(jī)器、工序之間無順序約束，即彼此獨(dú)立。這一方面使得問題有較大的優(yōu)化空間，另一方面也使解空間規(guī)模呈幾何指數(shù)增長(zhǎng)，給求解帶來困難。當(dāng)前主流的做法是對(duì)問題進(jìn)行編碼，然后利用優(yōu)化算法迭代尋找最優(yōu)的解決方案。但是，如前所述，由于解空間的規(guī)模巨大，“漫無目的”的“被動(dòng)尋找”，不僅效率低下，而且解的質(zhì)量沒有保障。

發(fā)明內(nèi)容

要解決的技術(shù)問題

為解決傳統(tǒng)方法對(duì)優(yōu)化方案“被動(dòng)尋找”的不足之處，本發(fā)明提出了一種基于不等量二分法的開放車間調(diào)度問題關(guān)鍵操作識(shí)別方法，該方法“主動(dòng)利用”O(jiān)SP無順序約束的特點(diǎn)，深入挖掘優(yōu)化方案的背后信息，能夠快速識(shí)別OSP中的關(guān)鍵操作，加快了問題求解速度，有助于提高求解質(zhì)量。

技術(shù)方案

本發(fā)明的主要步驟包括：?jiǎn)栴}編碼；對(duì)初始編碼方案進(jìn)行解碼；參數(shù)初始化；二分法“中點(diǎn)”位置確定；鄰域搜索；方案解碼；參數(shù)更新；得到關(guān)鍵工件和關(guān)鍵工序；輸出最終結(jié)果。

本發(fā)明的技術(shù)方案為：

所述一種基于不等量二分法的開放車間調(diào)度問題關(guān)鍵操作識(shí)別方法，其特征在于：采用以下步驟：

步驟1：?jiǎn)栴}編碼：對(duì)開放車間調(diào)度問題采用基于操作的整數(shù)編碼，得到編碼序列I₀＝{g₁,g₂,...,g_N}，其中N是I₀中包含的基因個(gè)數(shù)，g_j是I₀的第j個(gè)基因，j為基因在編碼序列I₀中的位置編號(hào)，基因所表示的整數(shù)值對(duì)應(yīng)實(shí)際調(diào)度問題中的一個(gè)工件編號(hào)，某個(gè)整數(shù)值在I₀中按從左向右順序出現(xiàn)的次數(shù)表示該整數(shù)值對(duì)應(yīng)工件的工序數(shù)；

步驟2：對(duì)編碼序列I₀進(jìn)行活動(dòng)解碼運(yùn)算，得到編碼序列I₀對(duì)應(yīng)的總的完工時(shí)間V₀和編碼序列I₀對(duì)應(yīng)的生產(chǎn)方案S₀；

步驟3：參數(shù)初始化：迭代次數(shù)sd初始值為1，鄰域搜索左邊界pos_L初始值為1，鄰域搜索右邊界pos_R初始值為N；

步驟4：采用以下步驟產(chǎn)生區(qū)間[pos_L+1,pos_R-1]內(nèi)的隨機(jī)整數(shù)mid：

步驟4.1：產(chǎn)生區(qū)間[0,1]內(nèi)的隨機(jī)實(shí)數(shù)r；

步驟4.2：產(chǎn)生區(qū)間[pos_L+1,pos_R-1]內(nèi)的隨機(jī)實(shí)數(shù)tmid：

tmid＝r×[(pos_R-1)-(pos_L+1)]+(pos_L+1)；

步驟4.3：對(duì)步驟4.2得到的隨機(jī)實(shí)數(shù)tmid進(jìn)行取整運(yùn)算，得到區(qū)間[pos_L+1,pos_R-1]內(nèi)的隨機(jī)整數(shù)mid；

步驟5：對(duì)編碼序列I₀中位置編號(hào)對(duì)應(yīng)區(qū)間[pos_L，mid]的所有基因利用洗牌算法隨機(jī)重排，得到重排后的編碼序列I_L；對(duì)編碼序列I₀中位置編號(hào)對(duì)應(yīng)區(qū)間[mid，pos_R]的所有基因利用洗牌算法隨機(jī)重排，得到重排后的編碼序列I_R；