[發(fā)明專利]一種基于果蠅算法的模糊批調(diào)度方法及系統(tǒng)

在審

• 申請(qǐng)?zhí)枺?/td>: 202011376058.8
• 申請(qǐng)日: 2020-11-30
• 公開（公告）號(hào): CN112364526A
• 公開（公告）日: 2021-02-12
• 發(fā)明（設(shè)計(jì)）人: 賈兆紅;王銳;唐俊
• 申請(qǐng)（專利權(quán)）人: 安徽大學(xué)
• 主分類號(hào): G06F30/20
• 分類號(hào): G06F30/20;G06F111/08;G06F119/12
• 代理公司: 合肥市浩智運(yùn)專利代理事務(wù)所(普通合伙) 34124
• 代理人: 張景云

1.一種基于果蠅算法的模糊批調(diào)度方法，其特征在于，包括以下步驟：

步驟1：根據(jù)模糊批調(diào)度問題的特點(diǎn)，建立模糊批調(diào)度問題的數(shù)學(xué)模型

步驟2：初始化最大迭代數(shù)T_max，果蠅種群數(shù)量NC，精英種群數(shù)量NE，果蠅種群中果蠅個(gè)體數(shù)S,令當(dāng)前迭代數(shù)t＝0；

步驟3：根據(jù)問題設(shè)計(jì)啟發(fā)式信息，通過啟發(fā)式信息構(gòu)建所有果蠅種群初始解；

步驟4：令t＝t+1，果蠅種群通過多種嗅覺搜索方案形成新的解，通過視覺搜索得到新的種群；

步驟5：對(duì)當(dāng)前代所有的果蠅種群進(jìn)行目標(biāo)值比較，重新初始化部分擁有較劣解和陷入局優(yōu)的果蠅種群；

步驟6：通過協(xié)作搜索更新精英種群，保留優(yōu)秀的解空間，精英果蠅執(zhí)行嗅覺和視覺搜索并更新種群解；

步驟7：從所有果蠅種群中獲取全局最優(yōu)調(diào)度方案，如果t＜T_max，則返回步驟4，否則輸出最優(yōu)調(diào)度方案。

2.根據(jù)權(quán)利要求1所述的基于果蠅算法的模糊批調(diào)度方法，其特征在于，所述的步驟1的數(shù)學(xué)模型如下：

假設(shè)存在n個(gè)工件需要進(jìn)行加工處理，處理工件的機(jī)器集合為M＝{M₁,M₂...M_i...M_m}，其中M_i的機(jī)器容量為Z_i，由n個(gè)工件組成的待加工批總集合為B，其中B_ki表示在第i個(gè)機(jī)器上處理的第k個(gè)批；工件集具有不同的加工尺寸s和模糊加工時(shí)間批的尺寸是批中所有工件的尺寸之和，批的模糊加工時(shí)間取決于批中所有工件中最大模糊加工時(shí)間以及批在機(jī)器上的加工位置，批的尺寸不超過其加工機(jī)器的容量，機(jī)器的模糊加工時(shí)間為機(jī)器中所有批的加工時(shí)間總和，目標(biāo)是最小化最大完工時(shí)間，即

其中T_i為機(jī)器M_i的完工時(shí)間。

3.根據(jù)權(quán)利要求1所述的基于果蠅算法的模糊批調(diào)度方法，其特征在于，所述的步驟3啟發(fā)式信息生成初始解詳細(xì)步驟如下：

步驟3.1：初始化當(dāng)前果蠅種群數(shù)Foa＝0；

步驟3.2：令Foa＝Foa+1,生成當(dāng)前果蠅種群的待加工工件集合TL；

步驟3.3：為所有機(jī)器創(chuàng)建候選工件集合CL_i，利用公式，

CL_i＝{J_j∈TL|s_j≤Z_i}

其中s_j表示工件J_j的尺寸；

步驟3.4：對(duì)比所有機(jī)器，找到當(dāng)前具有最小模糊完工時(shí)間且候選工件集不為空的機(jī)器M_i，為機(jī)器M_i新建一個(gè)批B_ki，從候選集合隨機(jī)選擇一個(gè)工件加入批中；

步驟3.5：更新批的尺寸和模糊加工時(shí)間，更新候選集合，公式為

CL_ki＝{J_j∈TL|s_j≤(Z_i-S_ki)}

其中CL_ki表示批B_ki的工件候選集合，S_ki表示B_ki的尺寸；

步驟3.6：通過候選工件和當(dāng)前加工批尺寸和加工時(shí)間的差異，計(jì)算候選工件的啟發(fā)式信息利用公式，

其中是工件J_j的模糊加工時(shí)間，表示批B_ki的模糊加工時(shí)間；

步驟3.7：生成一個(gè)隨機(jī)數(shù)R∈(0,1)，判斷R是否大于設(shè)定值；本實(shí)施例中，根據(jù)試驗(yàn)及工作經(jīng)驗(yàn)，設(shè)定值取值0.5；

步驟3.8：若是，選擇在候選集合中具有最大啟發(fā)式信息的工件放入當(dāng)前批中，若否，在候選集合中隨機(jī)選擇一個(gè)工件放入當(dāng)前批中；

步驟3.9：更新當(dāng)前批的剩余容量和模糊加工時(shí)間。

步驟3.10：更新當(dāng)前批的候選集合，判斷是否為空，若是則執(zhí)行步驟3.11，否則執(zhí)行步驟3.6；

步驟3.11：計(jì)算批的實(shí)際模糊加工時(shí)間，利用公式

其中表示批B_ki的原始加工時(shí)間，表示批B_ki的實(shí)際加工時(shí)間，γ表示一個(gè)不可壓縮因子，c₁和c₂分別表示學(xué)習(xí)因子和惡化因子，表示批B_ki的開始加工時(shí)間；

步驟3.12：更新機(jī)器M_i的模糊完工時(shí)間和待處理工件集合TL，判斷是否還有工件未分批，若是，則執(zhí)行步驟3.3；

步驟3.13：若否，則計(jì)算目標(biāo)值為當(dāng)前果蠅種群調(diào)度的初始解；

步驟3.14：判斷FoaNE，若是則執(zhí)行步驟3.2，否則結(jié)束。