[發(fā)明專利]基于關(guān)系鏈的作業(yè)車間調(diào)度關(guān)鍵外協(xié)工序辨識(shí)方法

有效

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

1.一種基于關(guān)系鏈的作業(yè)車間調(diào)度關(guān)鍵外協(xié)工序辨識(shí)方法，其特征在于：包括以下步驟：

步驟1：對(duì)待辨識(shí)的作業(yè)車間調(diào)度問題進(jìn)行求解，得到作業(yè)車間的初始調(diào)度方案C：初始調(diào)度方案C中包含機(jī)器總數(shù)m、工件總數(shù)n、在第k個(gè)機(jī)器的第s個(gè)次序上加工的工序信息：工序號(hào)、工件號(hào)、工序開始時(shí)間、工序結(jié)束時(shí)間；每個(gè)工件的加工過程由m道工序組成；

步驟2：關(guān)系鏈處理：包括如下步驟：

步驟2.1：建立關(guān)系鏈：

步驟2.1.1：根據(jù)步驟1中的初始調(diào)度方案C，得到每個(gè)工序的工件號(hào)i、工序號(hào)j、機(jī)器號(hào)k、在機(jī)器上的加工次序s、工序開始時(shí)間b_i,j和工序結(jié)束時(shí)間e_i,j；建立n個(gè)虛擬工序n個(gè)虛擬工序與n個(gè)工件一一對(duì)應(yīng)，虛擬工序的機(jī)器號(hào)在1~m中隨機(jī)選取，虛擬工序的工序開始時(shí)間和工序結(jié)束時(shí)間為0；

步驟2.1.2：按照下列方法確定每個(gè)工序的前等待關(guān)系A(chǔ)：

若b_i，j＞b_i，j-1+p_i,j-1且b_i,j＝b_i1,j1+p_i1,j1，取前等待關(guān)系A(chǔ)＝2；

若b_i,j＝b_i，j-1+p_i,j-1且b_i，j＞b_i1,j1+p_i1,j1，取前等待關(guān)系A(chǔ)＝3；

若b_i，j＝b_i，j-1+p_i,j-1且b_i，j＝b_i1,j1+p_i1,j1，取前等待關(guān)系A(chǔ)＝4；

其中，b_i,j-1為工序的工序開始時(shí)間，p_i，j-1為工序的加工時(shí)間，k1,s1根據(jù)i,j-1和初始調(diào)度方案C得到，b_i1,j1為工序的工序開始時(shí)間，p_i1,j1為工序的加工時(shí)間，i1，j1根據(jù)k,s-1和初始調(diào)度方案C得到；

步驟2.1.3：將所有工序和虛擬工序按照機(jī)器號(hào)分為m個(gè)關(guān)系鏈，每個(gè)關(guān)系鏈為具有相同機(jī)器號(hào)的工序集合；

步驟2.2：關(guān)系鏈的處理步驟：

步驟2.2.1：尋找出所有關(guān)系鏈中完成時(shí)間最晚的工序；

步驟2.2.2：判斷步驟2.2.1中的工序是否為虛擬工序，若是，則執(zhí)行步驟3，若不是，則以步驟2.2.1中的工序執(zhí)行步驟2.2.3；

步驟2.2.3：根據(jù)執(zhí)行該步驟的工序的前等待關(guān)系，進(jìn)行如下選擇：若執(zhí)行該步驟的工序的前等待關(guān)系A(chǔ)＝2，則執(zhí)行步驟2.2.4，若執(zhí)行該步驟的工序的前等待關(guān)系A(chǔ)＝3，則執(zhí)行步驟2.2.5，執(zhí)行該步驟的工序的前等待關(guān)系A(chǔ)＝4，則執(zhí)行步驟2.2.6；

步驟2.2.4：執(zhí)行本步驟的工序表示為將工序和加入外協(xié)工序集合Out中，其中a1,d1根據(jù)f,g-1和關(guān)系鏈得到；判斷工序是否為虛擬工序，若是，則執(zhí)行步驟2.3，若不是，則以工序執(zhí)行步驟2.2.3；

步驟2.2.5：執(zhí)行本步驟的工序表示為判斷工序是否為虛擬工序，若是，則執(zhí)行步驟2.3，若不是，則以工序執(zhí)行步驟2.2.3；其中h1,o1根據(jù)l,p-1和關(guān)系鏈得到；

步驟2.2.6：執(zhí)行本步驟的工序表示為判斷工序和工序是否均為虛擬工序，若是，則執(zhí)行步驟2.3，若不是，則以工序和工序中不為虛擬工序的工序執(zhí)行步驟2.2.3，并將此后加入外協(xié)工序集合Out中的工序同時(shí)加入試驗(yàn)集合Out1中；

步驟2.3：判斷試驗(yàn)集合Out1中的工序是否外協(xié)有效：首先判斷試驗(yàn)集合Out1是否為空集，若是，則執(zhí)行步驟3，若不是，則對(duì)試驗(yàn)集合Out1中的所有工序分別進(jìn)行外協(xié)，得到試驗(yàn)集合Out1中各個(gè)工序?qū)?yīng)的外協(xié)后重調(diào)度方案，若得到的外協(xié)后重調(diào)度方案的完工時(shí)間大于或等于初始調(diào)度方案的完工時(shí)間，則將該外協(xié)后重調(diào)度方案對(duì)應(yīng)的工序從外協(xié)工序集合Out中去除；

步驟3：對(duì)步驟2得到的外協(xié)工序集合Out中的所有工序分別進(jìn)行外協(xié)，得到的外協(xié)重調(diào)度方案組成外協(xié)重調(diào)度方案集；

其中對(duì)某一工序進(jìn)行外協(xié)，得到外協(xié)后重調(diào)度方案的過程包括以下步驟a~步驟d：

步驟a：計(jì)算外協(xié)工序的開始時(shí)間和結(jié)束時(shí)間：

其中，表示工件i的第j-1道工序的結(jié)束時(shí)間，加工時(shí)間表示外協(xié)工序的加工時(shí)間；

步驟b：以外協(xié)工序在初始調(diào)度方案C中的工序開始時(shí)間為界，將初始調(diào)度方案C中在該時(shí)間之后開始加工的工序組成需要重調(diào)度的工序集合R；

步驟c：計(jì)算集合R中每個(gè)工序在外協(xié)后重調(diào)度方案中的時(shí)間，其中集合R中的工序的開始時(shí)間和結(jié)束時(shí)間分別為：

其中表示在外協(xié)后重調(diào)度方案中工件w的第z-1道工序的結(jié)束時(shí)間，表示在外協(xié)后重調(diào)度方案中機(jī)器x的第v-1個(gè)加工次序的工序結(jié)束時(shí)間；加工時(shí)間表示工序的加工時(shí)間；

步驟d：根據(jù)步驟c得到的集合R中每個(gè)工序在外協(xié)后重調(diào)度方案中的時(shí)間更新初始調(diào)度方案，得到對(duì)某一工序進(jìn)行外協(xié)所對(duì)應(yīng)的外協(xié)后重調(diào)度方案；

步驟4：選擇1/完成時(shí)間、外協(xié)時(shí)間窗大小、平均機(jī)器利用率以及平均活躍時(shí)間的平均值作為評(píng)價(jià)屬性，采用TOPSIS方法對(duì)步驟3中外協(xié)重調(diào)度方案集進(jìn)行多屬性評(píng)價(jià)決策，得到最優(yōu)的外協(xié)重調(diào)度方案和最優(yōu)的外協(xié)重調(diào)度方案對(duì)應(yīng)的外協(xié)工序。