[發明專利]一種兩階段裝配流水車間調度方法

在審

• 申請號: 201711275686.5
• 申請日: 2017-12-06
• 公開（公告）號: CN108279647A
• 公開（公告）日: 2018-07-13
• 發明（設計）人: 鐘翠萍;陳豐;王樂;邱猛
• 申請（專利權）人: 吉林大學
• 主分類號: G05B19/418
• 分類號: G05B19/418
• 代理公司: 長春吉大專利代理有限責任公司 22201
• 代理人: 崔斌

1.一種兩階段裝配流水車間調度方法，其特征在于，該方法包括以下步驟：

步驟一、建立不同交貨期窗口約束下的兩階段裝配流水車間調度的目標函數；

步驟二、確定調度過程的約束條件；

步驟三、采用基于細胞受體的人工免疫系統算法即RAIS算法求解所述目標函數，經過迭代運算，將滿足停止條件的解解碼后作為最終的調度方案；

步驟一中所述的目標函數如下：

i為工件號，n為工件個數；

α_i為工件i的單位提前懲罰成本，β_i為工件i的單位滯后懲罰成本；

E_i為工件i的提前時間，T_i為工件i的滯后時間；

Z為提前與滯后懲罰成本加權和；

步驟二中所述的約束條件包括：

零件在并行同速機上不同位置約束：

零件拆分處理約束：

M×x_jtk≥q_jtk j,t＝1,2,…,h,k＝1,2,…m (6)

q_jtk-1≥M×(x_jtk-1) j,t＝1,2,…,h,k＝1,2,…m (7)

同一并行同速機不同位置上的零件完工時間約束：

C_0k＝0 k＝1,2,…,m (8)

F_i≥C_tk-M×(1-x_jtk)

工件在裝配機不同位置約束：

裝配機不同位置上的工件完工時間約束：

C_r≥F_i+A_i-M×(1-y_ir) i,r＝1,2,…,n (13)

工件提前成本與滯后成本約束：

E_i≥e_i-C_r-M×(1-y_ir) i,r＝1,2,…,n (15)

T_i≥C_r-d_i-M×(1-y_ir) i,r＝1,2,…,n (16)

E_i≥0 i＝1,2,…,n (17)

T_i≥0 i＝1,2,…,n (18)

上述公式(2)～(18)中，存在以下決策標量：

r為裝配機上工件加工的位置號；

m為并行同速機個數；

k為并行同速機號；

h為總的零件種類數；

j為零部件種類號；

t為并行同速機上零件加工的位置號；

J_i為工件i的零件種類集；

s_1j為加工零件j前的準備時間；

q_1j為零件j的總個數；

p_1j為零件j的單個加工時間；

s_2i為加工工件i前的準備時間；

A_i為工件i的裝配時間；

e_i為工件i交貨期窗口的起始時間；

d_i為工件i交貨期窗口的結束時間；

C_tk為并行同速機k位置t上的零件的完工時間；

C_(t-1)k為并行同速機k位置t-1上的零件的完工時間；

C_0k為并行同速機k位置0上的完工時間即機器未進行加工狀態下的時間點；

F_i為工件i進行裝配操作的最早開始時間；

C_r為裝配機位置r上的工件的完工時間；

C_r-1為裝配機位置r-1上的工件的完工時間；

q_jtk為并行同速機k位置t上的零件j的個數；

M為一個足夠大的正整數；

在上述公式(2)～(18)中，存在以下決策變量：

所述的步驟三的具體方法如下：

用RAIS求解不同交貨期窗口約束下的TSAFSP包括編碼、解碼和適應度值計算的操作；

31)編碼時，每個受體采用基于工件序列的編碼，記作(π₁,π₂,…,π_n)，即加工位置i處的工件為π_i；

32)解碼時，每個受體的解碼步驟如下：

步驟3.2.1：依據公式(2)～(10)，采用拆分法確定每臺并行同速機上零件種類、數量和完工時間；

a.設定i＝1,轉b；

b.計算其中CT_0k＝0，如果i≤n，則計算并對TP_j按從大到小排序得轉c；如果i＝n+1，則停止；

c.設定t＝1，MCT_k＝0(k＝1,2,…,m)轉d；

d.令w為min(MCT₁,MCT₂,…,MCT_m)的機器號，如果q_1t′＝0，則令t＝t+1轉d；如果同時滿足q_1t′>0，則q_tw′＝q_1t′，q_1t′＝0，CT_iw＝MCT_w+s_1t′+p_1t′×q_tw′，MCT_w＝CT_iw，令t＝t+1轉d；如果同時滿足q_1t′>0，則q_1t′＝q_1t′-q_tw′，CT_iw＝MCT_w+s_1t′+p_1t′×q_tw′，MCT_w＝CT_iw，轉d；如果同時滿足q_1t′>0，則q_tw′＝q_1t′，q_1t′＝0，CT_iw＝MCT_w+s_1t′+p_1t′×q_tw′，MCT_w＝CT_iw令t＝t+1轉d；如果且q_1t′＝0，則i＝i+1轉b；

步驟3.2.1中存在以下決策標量：

i為工件加工位置號，j為零件號，k為并行同速機器號；

為加工位置號為i的工件的零件在制造階段的完工時間下界；

CT_ik為加工位置號為i的工件的零件在并行同速機k上的最大完工時間；

CT_iw為加工位置號為i的工件的零件在并行同速機w上的最大完工時間；

CT_(i-1)k為加工位置號為i-1的工件的零件在并行同速機k上的最大完工時間；

為裝配工件π_i所需的零件種類數；

為工件π_i的零件j的不拆分總處理時間；

為裝配工件π_i所需的種零件中，第t大的不拆分總處理時間；

MCT_k為并行同速機k的完工時間；

MCT_w為并行同速機w的完工時間；

為裝配工件π_i所需的種零件中，不拆分總處理時間第t大的零件的總個數；

為裝配工件π_i所需的種零件中，不拆分總處理時間第t大的零件在并行同速機w上的個數；

為裝配工件π_i所需的種零件中，不拆分總處理時間第t大的零件的準備時間；

為裝配工件π_i所需的種零件中，不拆分總處理時間第t大的零件的單個加工時間；

為對數a向上取整；

步驟3.2.2：依據公式(11)～(14)，采用空閑時間插入法確定裝配機上工件的完工時間：

a.設定i＝1，ACT＝0，轉b；

b.判斷i≤n，如果不滿足，設定i＝n，ξ_r＝0(r＝1,2,…,n)，l＝1，FJ_l＝LJ_l＝i轉c；否則判斷滿足則ACT＝C_i，不滿足則ACT＝C_i；令i＝i+1轉b；

c.判斷i≥1，如果不滿足，則停止；否則判斷i＝n，如果滿足，則ξ_i＝1，否則判斷如果滿足，則ξ_i＝ξ_i+1，FJ_l＝i，否則ξ_i＝ξ_i+1+1，l＝l+1，FJ_l＝LJ_l＝i轉d；

d.令σ_l＝{r|ξ_r＝ξ_i,r＝1,2,…,n}，若則若則若則η_r＝0；計算判斷如果滿足，則i＝i-1轉c，否則轉e；

e.若則若則△_1r＝M；若則判斷ξ_i＝1，如果滿足，則△_2l＝M，如果不滿足，轉f；

f.若則C_r＝C_r+△_2l，ξ_r＝ξ_r-1，FJ_l-1＝FJ_l，l＝l-1轉c；若則轉c；

步驟3.2.2中存在以下決策標量：

CT_i1為加工位置號為i的工件的零件在并行同速機1上的最大完工時間；

CT_i2為加工位置號為i的工件的零件在并行同速機2上的最大完工時間；

CT_im為加工位置號為i的工件的零件在并行同速機m上的最大完工時間；

C_i為裝配機位置i上的工件的完工時間；

C_i+1為裝配機位置i+1上的工件的完工時間；

為加工工件π_i前的準備時間；

為加工工件π_i+1前的準備時間；

為加工工件前的準備時間；

為工件π_i的裝配時間；

為工件π_i+1的裝配時間；

為工件的裝配時間；

ACT為裝配機的完工時間；

ξ_i為裝配機上加工位置號為i的工件的標記號；

ξ_i+1為裝配機上加工位置號為i+1的工件的標記號；

ξ_r為裝配機上加工位置號為r的工件的標記號；

l為集合σ_l的標記號；

FJ_l為標記號為l的工件集中最早進行裝配的工件的加工位置號；

FJ_l-1為標記號為l-1的工件集中最早進行裝配的工件的加工位置號；

LJ_l為標記號為l的工件集中最晚進行裝配的工件的加工位置號；

為裝配機位置LJ_l上的工件的完工時間；

為裝配機位置LJ_l-1上的工件的完工時間；

為工件π_r的單位提前懲罰成本；

為工件π_r的單位滯后懲罰成本；

η_i為裝配機上加工位置號為i的工件的完工時間增加一個單位造成的成本減少值；

η_r為裝配機上加工位置號為r的工件的完工時間增加一個單位造成的成本減少值；

為工件π_r交貨期窗口的起始時間；

為工件π_r交貨期窗口的結束時間；

σ_l為標記號為l的工件集；

△_1r為工件在不改變其完工狀態(提前、滯后或如期完工)時，完工時間允許的最大增加值；

△_2l為集合σ_l中的工件在不影響其他工件集中的工作時，完工時間允許的最大增加值；

步驟3.2.3：依據公式(1)和(15)～(18)計算目標函數；

33)由于優化目標為提前和滯后懲罰成本加權和最小，采用目標函數的倒數作為適應度函數對每個受體進行評價；

34)RAIS算法求解不同交貨期窗口約束下的TSAFSP的步驟如下：

步驟3.4.1：隨機初始化NB個B細胞受體和NT個T細胞受體種群，轉步驟3.4.2；

步驟3.4.2：采用選擇和插入的方式對B細胞受體和T細胞受體種群進行基因再排列：首先將當前適應度值最高的受體作為標準受體，然后從其他受體的工件序列中隨機選擇R個加工位置號，將這R個加工位置號上對應的工件分別插入到其在標準受體中的加工位置上，若這個新的工件序列解碼的適應度值大于被選擇的受體適應度值，則更新被選擇的受體，否則被選擇的受體保持不變，轉步驟3.4.3；

步驟3.4.3：比對B細胞受體與當前適應度值最高的T細胞受體在相同加工位置處的工件，如果存在工件相同，則B細胞與T細胞發生同源相互作用，轉步驟4.4.4，否則B細胞與T細胞不發生同源相互作用，轉步驟3.4.6；

步驟3.4.4：采用部分隨機排序的方式對B細胞受體進行細胞突變：對比B細胞受體與當前適應度值最高的T細胞受體在相同加工位置處的工件，工件相同情況下組成的加工位置號集合為工件不相同情況下組成的加工位置號集合為δ，集合中加工位置號上工件保持不變，對集合δ中加工位置號上的工作重新隨機排序生成新的集合δ′，若解碼的適應度值大于被選擇的B細胞受體適應度值，則更新被選擇的B細胞受體，否則被選擇的B細胞受體保持不變，轉步驟3.4.5；

步驟3.4.5：采用交換、插入、和顛倒的領域搜索機制對B細胞受體進行抗體轉換：由于B細胞在T細胞受體的幫助下可以大量分化為分泌IgG、IgA、和IgE形態抗體的漿細胞進而消滅抗原，所以對被選擇的B細胞受體，分別以1/3的概率進行交換、插入、或顛倒搜索進而達到局部最優，每個被選擇的B細胞受體共進行I次抗體轉換，若抗體轉換后B細胞受體的適應度值提升，則更新被選擇的B細胞受體，否則不變，轉步驟3.4.7；

步驟3.4.6：采用插入和交換的領域搜索機制對B細胞受體進行IgM抗體轉換：由于B細胞在不與T細胞發生同源相互作用時，只是表達IgM抗體，提供一個快速的早期防御機制，所以被選擇的B細胞受體先進行插入，再做交換，若IgM抗體的表達后B細胞受體的適應度值提升，則更新被選擇的B細胞受體，否則不變，轉步驟3.4.7；

步驟3.4.7：當前適應度值最高的受體保持不變，其他受體重新隨機生成，轉3.4.8；

步驟3.4.8：判斷是否滿足預先設定的最長CPU運行時間T_max，如果滿足，將當前最好的解作為最優解，得到最終的調度方案并停止，如果不滿足轉步驟3.4.2。