蘇章圣,鄧 超+,錢 斌,胡 蓉,陳 波

(1.昆明理工大學(xué) 機(jī)電工程學(xué)院,云南 昆明 650500;2.昆明理工大學(xué) 信息與自動(dòng)化學(xué)院,云南 昆明 650500;3. 云南省煙草公司紅河州公司,云南,紅河 652300)

0 引言

在國(guó)家全面推進(jìn)制造業(yè)生產(chǎn)過(guò)程智能化戰(zhàn)略背景下,混合生產(chǎn)作為眾多制造企業(yè)實(shí)現(xiàn)柔性生產(chǎn)的一種主流方式,常用于工藝具有相似性產(chǎn)品的生產(chǎn)中,在發(fā)動(dòng)機(jī)、汽車、家電等行業(yè)中應(yīng)用極為廣泛。如何從調(diào)度的角度提升其混合系統(tǒng)智能化水平成為近年來(lái)制造領(lǐng)域研究熱點(diǎn)之一,備受工業(yè)界關(guān)注。

對(duì)于現(xiàn)有混合生產(chǎn)系統(tǒng)的調(diào)度研究,隨著調(diào)度理論的豐富與信息技術(shù)手段的增強(qiáng),從只考慮產(chǎn)品混流裝配的單系統(tǒng)調(diào)度問(wèn)題向加工到裝配整個(gè)流程的復(fù)雜系統(tǒng)轉(zhuǎn)移。王炳剛等[1-2]分別研究了加工階段為一條柔性線,裝配階段為帶緩沖區(qū)的多并行機(jī)流水線和一條混合裝配線的加工-混裝兩階段調(diào)度問(wèn)題,以平順化混合裝配線的部件消耗和最小化加工線總切換時(shí)間為優(yōu)化目標(biāo),提出了多目標(biāo)算法用于求解問(wèn)題。隨后,李修琳等[3]在文獻(xiàn)[2]基礎(chǔ)上進(jìn)一步研究了裝配階段考慮部件裝配和產(chǎn)品總裝過(guò)程的加工-混裝兩階段調(diào)度問(wèn)題,以最小化在制品成本為目標(biāo),設(shè)計(jì)集成模擬退火混合遺傳算法求解問(wèn)題。然而,隨著交通運(yùn)輸業(yè)快速發(fā)展,企業(yè)跨區(qū)域建廠成為主流,加工-混裝過(guò)程中的運(yùn)輸環(huán)節(jié)不容忽視。文獻(xiàn)[4-6]雖然將運(yùn)輸階段考慮到加工-裝配兩階段問(wèn)題中,但卻將運(yùn)輸過(guò)程簡(jiǎn)化為常數(shù)。鄧超等[7]考慮了運(yùn)輸階段車輛載重約束和工件分批運(yùn)輸問(wèn)題,將車間調(diào)度與運(yùn)輸調(diào)度集成,把問(wèn)題擴(kuò)展為帶批量運(yùn)輸?shù)募庸?運(yùn)輸-裝配三階段集成調(diào)度問(wèn)題,以最小化最大完工時(shí)間為優(yōu)化目標(biāo),設(shè)計(jì)融合規(guī)則的混合分布估計(jì)算法進(jìn)行優(yōu)化求解,但卻將裝配階段簡(jiǎn)化為單機(jī)調(diào)度問(wèn)題,并未考慮產(chǎn)品在裝配時(shí)多工藝約束和多機(jī)裝配的混裝問(wèn)題。KOMAKI等[8]對(duì)混裝問(wèn)題進(jìn)行詳細(xì)的分類和綜述,認(rèn)為大多數(shù)研究將產(chǎn)品結(jié)構(gòu)設(shè)置過(guò)于簡(jiǎn)單,只為每個(gè)產(chǎn)品考慮一個(gè)裝配操作,這與現(xiàn)混合裝配企業(yè)生產(chǎn)中產(chǎn)品結(jié)構(gòu)多樣、存在多個(gè)裝配工序的情況并不相符。因此,進(jìn)一步研究考慮工藝約束的多階段集成調(diào)度問(wèn)題具有重要的應(yīng)用價(jià)值。該問(wèn)題需要同時(shí)考慮多層級(jí)物料清單(Bill of Materials with Multi -Level,BOM_ML)結(jié)構(gòu)中所有零部件的加工工序、運(yùn)輸和裝配工序調(diào)度,具有生產(chǎn)過(guò)程階段間耦合約束多、各階段間關(guān)聯(lián)性強(qiáng)的特點(diǎn),是一類典型多階耦合約束(Multi-stage Coupling Constraints,MCC)優(yōu) 化 問(wèn) 題。目前,已有學(xué)者將多階耦合性運(yùn)用到求解裝配作業(yè)車間調(diào)度問(wèn)題并取得了良好效果[9-10]。由此,進(jìn)一步探索結(jié)合耦合性的多階段集成調(diào)度問(wèn)題(Multi-stage Coupling Integrated Scheduling Problem with Process Constraints,MCISP_PC)的高效求解方法具有重要理論意義。

復(fù)雜系統(tǒng)集成調(diào)度問(wèn)題的求解難度較大,在運(yùn)用算法對(duì)其求解的過(guò)程中,融入啟發(fā)式規(guī)則或多種操作機(jī)制(策略)于改進(jìn)型算法中是目前較為有效的處理方式。譬如在群優(yōu)化算法中,YAVARI等[11]針對(duì)包含m次加工和1次裝配的集成調(diào)度問(wèn)題,以最大化兩階段裝配系統(tǒng)的利潤(rùn)為優(yōu)化目標(biāo),結(jié)合先進(jìn)先出規(guī)則(First In First Out,FIFO)分配機(jī)器,引入半置換(Semi-Permutation,SP)機(jī)制劃分種群,對(duì)遺傳算法進(jìn)行改進(jìn),從而提出半置換遺傳算法(SP Genetic Algorithm,SPGA)對(duì)問(wèn)題進(jìn)行求解。ZHENG等[12]針對(duì)加工-運(yùn)輸-裝配的集成調(diào)度問(wèn)題, 以最小化最大完工時(shí)間為目標(biāo),運(yùn)用FIFO規(guī)則分配機(jī)器,提出結(jié)合種群分類機(jī)制、高斯學(xué)習(xí)策略和精英學(xué)習(xí)策略的改進(jìn)混合蝙蝠算法(Improved Hybrid Bat Algorithm,IHBA)對(duì)問(wèn)題進(jìn)行求解。在學(xué)習(xí)型算法中,ZHANG等[13]對(duì)分布估計(jì)算法(Estimation of Distribution Algorithm,EDA)的概率學(xué)習(xí)模型進(jìn)行改進(jìn),針對(duì)分布式裝配置換流水車間調(diào)度問(wèn)題,將概率學(xué)習(xí)模型拓展至三維并結(jié)合多種變鄰域操作和加速策略,利用最短加工時(shí)間優(yōu)先規(guī)則(Shortest Processing Time,SPT)為工件分配工廠,從而完成復(fù)雜系統(tǒng)求解。郭晨等[14]則對(duì)EDA的局部搜索作進(jìn)一步細(xì)化,針對(duì)不確定環(huán)境下的分布式加工-裝配調(diào)度問(wèn)題,以最小化拖延期為優(yōu)化目標(biāo),提出基于多維編碼的混合差分搜索及變鄰域的混合EDA,設(shè)計(jì)基于概率模型相似度的變異策略動(dòng)態(tài)選擇搜索策略,提高算法的局部勘探能力。也有學(xué)者采用結(jié)合問(wèn)題性質(zhì),提出相關(guān)規(guī)則與算法結(jié)合的處理方式。JOO等[15]針對(duì)加工-運(yùn)輸兩階段集成問(wèn)題,對(duì)不同子問(wèn)題設(shè)計(jì)相關(guān)求解規(guī)則,在遺傳算法框架下進(jìn)行仿真實(shí)驗(yàn)以確定最佳規(guī)則組合,并利用最優(yōu)規(guī)則組形成元啟發(fā)框架對(duì)優(yōu)質(zhì)解進(jìn)行搜索。WANG等[16]針對(duì)兩階段混合裝配問(wèn)題,對(duì)問(wèn)題結(jié)構(gòu)性質(zhì)進(jìn)行分析,提出了10種不同情況下的優(yōu)勢(shì)規(guī)則(Dominance Rule,DR)并進(jìn)行了證明,結(jié)合反向粒子群算法(Opposition-based Particle Swarm Optimization algorithm,OPSO)形成DR_OPSO算法來(lái)對(duì)優(yōu)質(zhì)解進(jìn)行搜索。上述文獻(xiàn)表明,現(xiàn)有研究中結(jié)合問(wèn)題性質(zhì)設(shè)計(jì)有效的啟發(fā)式規(guī)則與算法結(jié)合可提升求解效率,但在算法層面仍將問(wèn)題本身和求解算法之間剝離開(kāi)來(lái),把精力集中在提升算法本身的性能上,缺少?gòu)姆治鰡?wèn)題特性的角度出發(fā)設(shè)計(jì)行之有效的算法操作,導(dǎo)致求解效果在問(wèn)題求解難度不斷增大時(shí)顯得收效甚微。因此,在面對(duì)復(fù)雜系統(tǒng)集成調(diào)度問(wèn)題上,不僅需要結(jié)合問(wèn)題特性的設(shè)計(jì)有效啟發(fā)式規(guī)則,還需考慮到算法全局和局部搜索與問(wèn)題本身的關(guān)聯(lián)性,從而探索融入問(wèn)題特性的高效求解方法是目前需進(jìn)一步解決的問(wèn)題。

綜上,結(jié)合問(wèn)題多階耦合性,本文提出一種結(jié)合規(guī)則啟發(fā)式的混合分布估計(jì)算法(Hybrid Estimation of Distribution Algorithm with Rule Heuristics,HEDA_RH)求解以最小化最大完工時(shí)間(Makespan)為優(yōu)化目標(biāo)的MCISP_PC。先分階段構(gòu)建問(wèn)題排列模型,在分析問(wèn)題耦合特性的基礎(chǔ)上,采用只針對(duì)加工階段的編碼,后續(xù)階段通過(guò)設(shè)計(jì)基于問(wèn)題性質(zhì)的求解規(guī)則完成問(wèn)題解碼。并設(shè)計(jì)HEDA_RH求解MCISP_PC。在HEDA_RH中,依據(jù)個(gè)體中發(fā)現(xiàn)的兩種塊結(jié)構(gòu)特征,結(jié)合問(wèn)題耦合性質(zhì),從全局角度設(shè)計(jì)兩種采樣機(jī)制以提升解的搜索效率;從局部角度設(shè)計(jì)矩陣立方學(xué)習(xí)模型,通過(guò)積累6種啟發(fā)式搜索操作的優(yōu)質(zhì)信息,自適應(yīng)地調(diào)整搜索深度及選擇搜索操作。

1 問(wèn)題描述及數(shù)學(xué)模型

1.1 問(wèn)題描述

MCISP_PC描述如下:根據(jù)訂單和產(chǎn)品多層級(jí)物料清單,組成產(chǎn)品的零件加工所需原材料由不同供應(yīng)商提供,再分別于加工階段完成多工序加工,后經(jīng)運(yùn)輸階段運(yùn)送至混裝階段完成產(chǎn)品裝配。加工階段中,零件根據(jù)加工工藝路線在M臺(tái)異構(gòu)并行機(jī)完成所有工序則視為加工完成。運(yùn)輸階段中,零件由T輛載重為Gmax的同型運(yùn)輸車分批運(yùn)送到混裝階段。混裝階段中,根據(jù)產(chǎn)品零件組成和裝配工藝約束在K臺(tái)裝配機(jī)器上完成裝配,從而完成整個(gè)生產(chǎn)。問(wèn)題模型如圖1所示,產(chǎn)品多層級(jí)物料清單如圖2所示,不同產(chǎn)品間存在相同零件和裝配工序。此外,若需了解MCISP_PC的詳細(xì)流程或?qū)嵗?請(qǐng)參見(jiàn)附錄中的問(wèn)題實(shí)例。

圖1 MCISP_PC示意圖

圖2 產(chǎn)品多層級(jí)物料清單

MCISP_PC中,零件在加工階段考慮釋放時(shí)間和不同型號(hào)零件間在機(jī)器上加工時(shí)的設(shè)置時(shí)間;運(yùn)輸階段考慮分批運(yùn)輸、車輛載重和運(yùn)輸速度;裝配階段考慮產(chǎn)品零件組成和裝配工藝約束。問(wèn)題中的假設(shè)如下:

(1)不同產(chǎn)品間可存在相同的零件;

(2)同種加工工序在某零件加工中至多為1次;

(3)同種裝配工序在某產(chǎn)品中至多為1次;

(4)加工工序、零件運(yùn)輸和產(chǎn)品裝配工序一旦開(kāi)始不可被中斷;

(5)加工機(jī)器與裝配機(jī)器某一時(shí)刻至多能處理一個(gè)工序,運(yùn)輸車輛某一時(shí)刻至多運(yùn)輸總重不超過(guò)車輛最大載重。

1.2 問(wèn)題數(shù)學(xué)模型

文中涉及到的符號(hào)說(shuō)明如下:

z為產(chǎn)品下標(biāo),z∈{1,2,…,P},P為產(chǎn)品種數(shù);

q為零件下標(biāo),q∈{1,2,…,Q},Q為零件種數(shù);

o為加工工序下標(biāo),o∈{1,2,…,O},O為加工工序種數(shù);

a為裝配工序下標(biāo),a∈{1,2,…,A},A為裝配工序種數(shù);

m為加工機(jī)器下標(biāo),m∈{1,2,…,M},M為加工機(jī)器數(shù);

t為運(yùn)輸車輛下標(biāo),t∈{1,2,…,T},T為運(yùn)輸車輛數(shù);

k為裝配機(jī)器下標(biāo),k∈{1,2,…,K},K為裝配機(jī)器數(shù);

Dz為產(chǎn)品z的需求量,Dq為零件q的需求量;

dP-A為加工階段到裝配階段的運(yùn)輸距離;

Rq為零件q的原材料到達(dá)(釋放)時(shí)間;

Tom為工序o在機(jī)器m上的加工時(shí)間;

Tak為裝配工序a在機(jī)器k上的裝配時(shí)間;

Tq,q′為零件q與q′間的設(shè)置時(shí)間;

Gmax為車輛最大載重;

V0為車輛空載時(shí)的速度;

jqr為第r個(gè)零件q,r∈{1,2,…,Dq};

pzh為第h個(gè)產(chǎn)品z,h∈{1,2,…,Dz};

nq為零件q的加工工序數(shù);

nz為產(chǎn)品z的裝配工序數(shù);

Um為機(jī)器m上的加工工序總數(shù);

Ut為車輛t的運(yùn)輸總趟數(shù);

Uk為裝配k機(jī)器上的裝配工序總數(shù);

Gtw為車輛t第w趟運(yùn)輸?shù)闹亓?w={1,2,…,Ut};

Vtw為車輛t第w趟運(yùn)輸?shù)乃俣?w={1,2,…,Ut};

1.2.1 加工階段

(1)

(2)

(3)

(4)

1.2.2 運(yùn)輸階段

(5)

(6)

1.2.3 混裝階段

(7)

(8)

(9)

(10)

1.2.4 優(yōu)化目標(biāo)

式(11) 定義Makespan(Cmax(π))為最后一個(gè)裝配產(chǎn)品的完工時(shí)間,優(yōu)化目標(biāo)為在加工、運(yùn)輸、裝配3個(gè)階段的排序π=[πst1,πst2,πst3]中找到最佳排序π*使得式(12)中三階段的總完工時(shí)間Makespan(Cmax(π))最小。

(11)

(12)

2 MCISP_PC多階耦合性分析

MCISP_PC是將加工、運(yùn)輸和裝配一同處理的車間與運(yùn)輸集成的多階段調(diào)度問(wèn)題。具有生產(chǎn)過(guò)程階段間耦合約束層階性、約束時(shí)序性和關(guān)聯(lián)性的特點(diǎn),是一類典型的多階耦合約束優(yōu)化問(wèn)題。

(1)耦合約束層階性 MCISP_PC涉及到產(chǎn)品的多級(jí)物料清單、零件加工工序約束及產(chǎn)品裝配工藝約束。產(chǎn)品的裝配需要滿足所組成的零件都到達(dá),零件能被運(yùn)輸需要滿足該零件所有工序都加工完成,層層遞進(jìn),各層級(jí)之間聯(lián)系緊密,這是實(shí)現(xiàn)耦合的前提。

(2)耦合約束時(shí)序性 各階段間在生產(chǎn)運(yùn)輸過(guò)程中存在互為因果的關(guān)系,且具有伴生性。產(chǎn)品裝配開(kāi)始時(shí)間受限于所需零件的運(yùn)達(dá)混裝廠的時(shí)間;運(yùn)輸開(kāi)始時(shí)間受限于零件的加工完成時(shí)間;加工階段零件開(kāi)始加工時(shí)間受限于工序釋放時(shí)間。階段間的發(fā)展關(guān)系并非靜止?fàn)顟B(tài),而是處于動(dòng)態(tài)變化之中。耦合狀態(tài)的形成過(guò)程就是各自階段在時(shí)序列上不斷交互銜接、前進(jìn)的過(guò)程。

3 編碼及解碼規(guī)則設(shè)計(jì)

針對(duì)MCISP_PC,若對(duì)[πst1,πst2,πst3]3個(gè)階段的序一一編碼,將會(huì)由于解空間極為龐大而出現(xiàn)搜索效率低和收斂困難等問(wèn)題。因此,結(jié)合MCISP_PC中存在的多階耦合特性采用只針對(duì)加工階段的編碼,并基于各階段耦合特征設(shè)計(jì)規(guī)則形成多個(gè)規(guī)則組完成后續(xù)階段的解碼。

3.1 編碼

圖3 編碼方式

3.2 解碼規(guī)則設(shè)計(jì)與實(shí)驗(yàn)

圖4 解碼過(guò)程

3.2.1 加工階段機(jī)器分配規(guī)則

采用帶釋放時(shí)間和設(shè)置時(shí)間的調(diào)度問(wèn)題兩種常見(jiàn)分配規(guī)則,設(shè)置-加工時(shí)間最短規(guī)則[15](Shortest Process time + Set time,SPST)和最早完工時(shí)間規(guī)則[7](Earliest Completion Time, ECT)。SPST規(guī)則將工序分配到設(shè)置時(shí)間與加工時(shí)間之和最小的機(jī)器上,ECT規(guī)則將工序分配到最早能夠完成加工的機(jī)器上。

3.2.2 運(yùn)輸階段零件分批規(guī)則

零件在加工完成后,需先進(jìn)行運(yùn)輸批次劃分,再為批次指派運(yùn)輸車輛。結(jié)合問(wèn)題多階耦合時(shí)序性及層級(jí)性,設(shè)計(jì)兩種規(guī)則:先完工先運(yùn)輸規(guī)則(First Finish First Ship, FFFS)和時(shí)間范圍內(nèi)最大載重規(guī)則(Maximum Load in Time Range,MLTR)。

(1)先完工先運(yùn)輸規(guī)則(FFFS)

僅根據(jù)零件加工階段的完工時(shí)間從小到大進(jìn)行排序,依次從前到后對(duì)零件的重量進(jìn)行相加,若加入后一個(gè)零件會(huì)導(dǎo)致該批零件總重超過(guò)車輛載重,則前面幾個(gè)零件就會(huì)被歸為同一批。如圖5a～圖5c所示,若在含有零件5、4的第一批運(yùn)輸加入零件3后會(huì)導(dǎo)致超載,則將零件3放入下一批;第二批在有[3,2,1]的情況下放入零件6會(huì)超載,則將零件6單獨(dú)放入下一批進(jìn)行運(yùn)輸,最終形成了[5,4]、[3,2,1]、[6]的運(yùn)輸批次和第二階段的零件運(yùn)輸排序πst2=[5,4,3,2,1,6]。

圖5 運(yùn)輸階段分批規(guī)則

(2)時(shí)間范圍內(nèi)最大載重規(guī)則(MLTR)

在FFFS規(guī)則的基礎(chǔ)上,給定一個(gè)時(shí)間范圍T_range,當(dāng)下一個(gè)零件無(wú)法滿足載重約束時(shí),考慮T_range內(nèi)能夠滿足載重約束的零件。如圖5d～圖5f所示,加入零件3后無(wú)法滿足第一批零件的載重約束,考慮T_range范圍內(nèi)的零件2且符合載重約束,則將零件2放入第一批運(yùn)輸中;第二批運(yùn)輸中,零件6在T_range內(nèi)但不符合載重約束,只能放到第三批運(yùn)輸中,最終形成3個(gè)運(yùn)輸批次[5,4,2]、[3,1]、[6]和第二階段的零件運(yùn)輸排序πst2=[5,4,2,3,1,6]。

3.2.3 產(chǎn)品裝配排序規(guī)則

完工零件被分批運(yùn)送到裝配階段后,將被分配到不同產(chǎn)品中完成裝配。當(dāng)運(yùn)達(dá)零件q滿足多個(gè)產(chǎn)品的裝配條件時(shí),為使混裝初期能有更多的產(chǎn)品得以裝配以平衡整個(gè)裝配階段的裝配壓力,結(jié)合問(wèn)題時(shí)序性與層級(jí)性設(shè)計(jì)兩種規(guī)則:最少零件產(chǎn)品優(yōu)先規(guī)則(Minimum Parts First, MPF)和最多后續(xù)可加工產(chǎn)品優(yōu)先規(guī)則(Maximum number of Subsequent Products First, MSPF)。

圖6 產(chǎn)品聚合的裝配工序排序

πst3生成的步驟如下,其中步驟5利用ECT規(guī)則為工序分配裝配機(jī)器。

算法1少零件產(chǎn)品優(yōu)先規(guī)則(MPF)。

輸入:可裝配產(chǎn)品(p1,p2,…,pn);

輸出:選擇可裝配的產(chǎn)品choice。

For i=1 To n

令ηi←0.

For q=1 To Q

若pi的裝配需要零件q,則ηi←ηi+1.

End

End

算法2最多后續(xù)可加工產(chǎn)品優(yōu)先規(guī)則(MSPF)。

輸入:可裝配產(chǎn)品(p1,p2,…,pn),當(dāng)前不同零件的擁有量(h1,h2,…,hQ);

輸出:選擇可裝配的產(chǎn)品choice。

For i=1 To n

統(tǒng)計(jì)(h1,h2,…,hQ)下可裝配產(chǎn)品的數(shù)量ηi.

End

步驟2構(gòu)建矩陣[Wab]A×A,若工序a為工序b的緊前裝配工序則wab=1,否則為0wab=0(a,b=1,2,…,A);

步驟4W的第a列是否全為0,若a列全為0則表示a沒(méi)有緊前工序,將a放入待加工數(shù)組Μ中;若a列中存在1,則說(shuō)明a還有緊前工序未完成;

步驟7令i=i+1,若i≤S則返回步驟3,否則結(jié)束。

4 HEDA_RH求解MCISP_PC

4.1 個(gè)體塊結(jié)構(gòu)描述

按上述編碼方式,通過(guò)對(duì)優(yōu)質(zhì)個(gè)體的統(tǒng)計(jì),出現(xiàn)了一些塊聚集現(xiàn)象。一種是塊中所有工序均為同一種零件,稱為同型聚集塊(Homotype Gather Block,HGB)。如圖7所示,在3個(gè)不同個(gè)體中,用同一顏色表示同一種零件,前后顏色相同的塊為HGB,如[1 1]、[2 2 3 3]和[ 8 6 9]等。另一種是塊中并非所有工序均為同一零件但在優(yōu)質(zhì)個(gè)體中出現(xiàn)多次的塊結(jié)構(gòu),稱為異型聚集塊(Isomerism Gather Block,IGB),圖7標(biāo)記長(zhǎng)度為3的IGB,如[4 4 1]、[1 1 7]和[7 1 4]等。

圖7 IGB與HGB示意圖

(13)

圖8 不同值下的和的變化趨勢(shì)

4.2 種群初始化

步驟1將π0隨機(jī)分為π和π′兩段,兩段長(zhǎng)度差值小于等于1,令i=1;

步驟2讀取πi的零件型號(hào);

步驟3在π′中選取一個(gè)同型零件插入到πi后,若π′中沒(méi)有同型零件則令i=i+1并返回步驟2;

步驟4刪除π′中剛插入的同型零件,i=i+1,若i≤L則返回步驟2。

4.3 概率模型初始化與更新

(14)

(15)

(16)

(17)

(18)

(19)

(20)

(21)

(22)

(23)

(24)

I1,I2,…,IΛ=1,2,…,J,s=Λ,…,L。

4.4 HEDA_RH采樣機(jī)制

4.4.1 采樣機(jī)制Ⅰ:結(jié)合HGB記錄矩陣的采樣

圖9 采樣機(jī)制Ⅰ示意圖

4.4.2 采樣機(jī)制Ⅱ:結(jié)合IGB記錄矩陣的采樣

步驟2令sit=Λ,統(tǒng)計(jì)零件j還需出現(xiàn)在π中的次數(shù)uj;

步驟4根據(jù)式(25)計(jì)算RInput;

步驟5若uj=0,則將RInput(j)置為0;

步驟7若sit

(25)

x=1,2,...,J。

圖10為采樣機(jī)制Ⅱ的采樣過(guò)程。

圖10 采樣機(jī)制Ⅱ示意圖

每一代的新種群都由3部分組成:上一代優(yōu)質(zhì)個(gè)體比率為α1;采樣機(jī)制Ⅰ生成的個(gè)體,比率為α2;采樣機(jī)制Ⅱ生成的個(gè)體,比率為α3;α1+α2+α3=1。

4.5 自適應(yīng)矩陣立方啟發(fā)式局部搜索

MCISP_PC解空間龐大,隨著問(wèn)題規(guī)模增加會(huì)出現(xiàn)解空間爆炸現(xiàn)象,全局搜索雖具有一定的搜索廣度但深度有所欠缺,往往無(wú)法讓算法跳出局部最優(yōu)。究其原因往往是因?yàn)槿炙阉魃疃炔粔蚯译S迭代次數(shù)增加種群多樣性逐漸減小。因此,需為算法設(shè)計(jì)合理有效的局部搜索操作,以兼顧算法搜索深度和種群多樣性。HEDA_RH中局部搜索部分結(jié)合問(wèn)題特性設(shè)計(jì)6種啟發(fā)式操作,通過(guò)矩陣立方啟發(fā)式操作學(xué)習(xí)模型,自適應(yīng)地調(diào)整搜索深度、學(xué)習(xí)啟發(fā)式規(guī)則執(zhí)行策略。最后通過(guò)個(gè)體替換策略來(lái)提升迭代更新后的個(gè)體差異性,從而確保種群多樣性。

4.5.1 矩陣立方啟發(fā)式操作學(xué)習(xí)模型

(26)

(27)

(28)

(29)

(30)

(31)

4.5.2 啟發(fā)式操作

續(xù)表1

4.5.3 個(gè)體替換策略

(32)

(33)

4.6 種群更新策略

(34)

(35)

4.7 HEDA_RH算法流程

本節(jié)設(shè)計(jì)HEDA_RH求解MCISP_PC。在定義了優(yōu)質(zhì)個(gè)體中兩種塊結(jié)構(gòu)基礎(chǔ)上,結(jié)合問(wèn)題性質(zhì)從全局角度設(shè)計(jì)概率更新模型及兩種采樣方式,從局部角度設(shè)計(jì)矩陣立方啟發(fā)式學(xué)習(xí)模型自適應(yīng)地選擇6種啟發(fā)式操作對(duì)優(yōu)質(zhì)個(gè)體進(jìn)行細(xì)致搜索。HEDA_RH的算法具體流程如圖11所示。

圖11 HEDA_RH算法流程圖

5 仿真實(shí)驗(yàn)與結(jié)果分析

本章實(shí)驗(yàn)中,MCISP_PC使用L/J/S_M/T/K表示問(wèn)題規(guī)模,其中L/J/S分別表示加工工序數(shù)、運(yùn)輸零件數(shù)和裝配工序數(shù),M/T/K分別表示加工機(jī)器數(shù)、運(yùn)輸車輛數(shù)和裝配機(jī)器數(shù)。所有算法程序均在MATLAB 2021b下編程實(shí)現(xiàn),實(shí)驗(yàn)設(shè)備為CPU:i7-11800h,RAM:16 GB。實(shí)驗(yàn)中產(chǎn)品的物料結(jié)構(gòu)、工序時(shí)間和不同規(guī)模下產(chǎn)品需求量如https://pan.baidu.com/s/19Jsp3bbBefK3gtGseEe9bQ?pwd=HEDA所示,不同規(guī)模的實(shí)驗(yàn)運(yùn)行時(shí)間T(s)由問(wèn)題規(guī)模確定,即T(s)=L×M+J×T+S×K,車輛運(yùn)輸速度設(shè)為Vtw=V0-0.085×Gtw。

5.1 規(guī)則有效性驗(yàn)證與規(guī)則組對(duì)比實(shí)驗(yàn)

將3個(gè)階段6種規(guī)則進(jìn)行組合得到8種規(guī)則組用于MCISP_PC求解,用三元組方式表示一個(gè)規(guī)則組,如ECT/FFFS/MSPF規(guī)則表示3個(gè)階段分別選取ECT、FFFS和MSPF規(guī)則,MLTR中T_range設(shè)為所有加工工序的平均加工時(shí)間。為驗(yàn)證8種規(guī)則組在求解MCISP_PC中的有效性,探尋不同規(guī)則在不同規(guī)模下的求解效率,將8種規(guī)則組與全編碼求解方式進(jìn)行對(duì)比,在18種不同問(wèn)題規(guī)模下均采用EDA算法進(jìn)行求解。實(shí)驗(yàn)中,全編碼(FullCode)指的是對(duì)加工工序排列及機(jī)器分配、零件運(yùn)輸分批及車輛分配、產(chǎn)品的零件分配、裝配工序排列及裝配機(jī)器分配進(jìn)行編碼求解。全編碼求解及8種規(guī)則組求解將分別在不同規(guī)模下于T(s)內(nèi)獨(dú)立運(yùn)行20次。實(shí)驗(yàn)結(jié)果如表2和表3所示,表中評(píng)價(jià)指標(biāo)best為最優(yōu)值、worst為最差值、avg為平均值、std為方差,加粗字體為該規(guī)模不該指標(biāo)的最優(yōu)值,NS為不同求解方式在特定評(píng)價(jià)指標(biāo)下獲得最優(yōu)值的次數(shù)。實(shí)驗(yàn)數(shù)據(jù)表明:8種規(guī)則組均比全編碼求解方式獲得較大的提升,且隨著問(wèn)題規(guī)模的增加提升效果越明顯;在大規(guī)模實(shí)驗(yàn)中規(guī)則幾乎獲得了一倍的提升,通過(guò)std值表明在求解穩(wěn)定性方面均有提高。由圖12可看出:規(guī)則組ECT/*/*明顯優(yōu)于SPST/*/*;ECT/FFFS/MPF與ECT/MLTR/MPF在四種對(duì)比參數(shù)下均獲得了更多的NS值。

表2 全編碼及前四組規(guī)則對(duì)比實(shí)驗(yàn)數(shù)據(jù)

表3 后四組規(guī)則對(duì)比實(shí)驗(yàn)數(shù)據(jù)

圖12 NS對(duì)比直方圖

為進(jìn)一步比較規(guī)則組ECT/*/*求解效率,以式(36)計(jì)算ECT/*/*在不同規(guī)模下的平均相對(duì)百分比偏差(ARPD),其中S為當(dāng)前所求結(jié)果,S*為該規(guī)模下運(yùn)行所得最優(yōu)值,n為實(shí)驗(yàn)重復(fù)次數(shù)。ARPD可反應(yīng)不同規(guī)則所求結(jié)果與S*的偏離程度和不同規(guī)模下的波動(dòng)情況,ARPD值越小越好。結(jié)合表2和表3與圖12和圖13,可得到以下結(jié)論:①ECT規(guī)則效果明顯優(yōu)于SPST規(guī)則;②規(guī)則組ECT/FFFS/MPF及ECT/MLTR/MPF的求解效果較優(yōu)。由此確定后續(xù)實(shí)驗(yàn)中HEDA_RH種群中所采用兩種規(guī)則組設(shè)定RGA為ECT/FFFS/MPF、RGB為ECT/MLTR/MPF來(lái)完成解碼。

(36)

圖13 不同規(guī)則ARPD隨實(shí)驗(yàn)規(guī)模變化曲線

5.2 參數(shù)設(shè)置

5.2.1 關(guān)鍵參數(shù)設(shè)置

為確定HEDA_RH中關(guān)鍵參數(shù)取值,采用試驗(yàn)設(shè)計(jì)方法(Design of Experiment,DOE)進(jìn)行參數(shù)試驗(yàn)分析。HEDA_RH中所涉及5個(gè)參數(shù)及選取的4個(gè)水平值如表4所示,即需完成規(guī)模為L(zhǎng)(45)的正交實(shí)驗(yàn)。實(shí)驗(yàn)規(guī)模選取中等規(guī)模(82/42/71_3/3/3),采樣機(jī)制Ⅱ個(gè)體比率α3=1-α1-α2。將平均值avg作為測(cè)試響應(yīng)值,每組參數(shù)組均分別進(jìn)行20次獨(dú)立實(shí)驗(yàn),運(yùn)行時(shí)間同為T(s)=L×M+J×T+S×K。

表4 關(guān)鍵參數(shù)水平值

所選測(cè)試參數(shù)正交表及avg統(tǒng)計(jì)值如表5所示,根據(jù)正交表得出各參數(shù)不同水平響應(yīng)值、極差和影響力等級(jí)如表6所示。由表4～由表6可知,γ1取水平3、γ2取水平4、ξ取水平2、α1取水平2、α2取水平2時(shí)算法性能相對(duì)較好,且由極差可知α1對(duì)HEDA_RH的性能影響最大,其次是ξ、α2、γ1、γ2。綜上,HEDA_RH的關(guān)鍵參數(shù)設(shè)置為γ1=0.85,γ2=0.9,ξ=0.75,α1=0.2,α2=0.4,α3=0.4。

5.2.2 IGB塊長(zhǎng)度Λ設(shè)置實(shí)驗(yàn)

表7 不同Λ取值下的ARPD值

5.3 算法對(duì)比實(shí)驗(yàn)

由于MCISP_PC為一種新的調(diào)度問(wèn)題,目前尚未有文獻(xiàn)對(duì)問(wèn)題進(jìn)行求解。為驗(yàn)證算法有效性,將HEDA_RH與國(guó)際期刊中用于求解與MCISP_PC類似集成調(diào)度問(wèn)題的半置換遺傳算法(SPGA[11])和離散蝙蝠算法(IHBA[12])進(jìn)行比較。SPGA與IHBA均選用文獻(xiàn)中設(shè)置的最優(yōu)參數(shù),HEDA_RH關(guān)鍵參數(shù)設(shè)置同5.2.1節(jié)。此外,根據(jù)5.2.2節(jié)實(shí)驗(yàn)結(jié)果在小、中、大規(guī)模中Λ分別取2、3、4進(jìn)行實(shí)驗(yàn)。對(duì)比算法采用規(guī)則組ECT/FFFS/MPF計(jì)算完工時(shí)間,編碼同為基于加工工序零件編碼。不同算法在18種問(wèn)題規(guī)模下于時(shí)間T(s)內(nèi)分別獨(dú)立運(yùn)行20次。表8以worst、best、avg、ARPD為評(píng)價(jià)指標(biāo)對(duì)實(shí)驗(yàn)結(jié)果進(jìn)行統(tǒng)計(jì)。圖14為6種問(wèn)題規(guī)模下,不同算法的所求結(jié)果箱線圖,可見(jiàn)隨著問(wèn)題規(guī)模的增加HEDA_RH的求解效果越明顯。通過(guò)上述實(shí)驗(yàn)可知,HEDA_RH在18種規(guī)模中均較其他兩種算法得到了較好值,由此表明了HEDA_RH能有效求解MCISP_PC。

表8 HEDA_RH與SPGA[11]、IHBA[12]對(duì)比實(shí)驗(yàn)結(jié)果

圖14 算法對(duì)比箱線圖

6 結(jié)束語(yǔ)

針對(duì)考慮裝配工藝約束的加工-運(yùn)輸-裝配多階耦合集成調(diào)度問(wèn)題(MCISP_PC),提出一種結(jié)合規(guī)則啟發(fā)式的混合分布估計(jì)算法(HEDA_RH)求解以最小化最大完工時(shí)間為優(yōu)化目標(biāo)的MCISP_PC。從復(fù)雜系統(tǒng)集成調(diào)度在多階耦合性質(zhì)下的高效求解方法出發(fā),利用問(wèn)題多階耦合特性,采用了只對(duì)加工階段進(jìn)行編碼,后續(xù)階段通過(guò)規(guī)則組合完成問(wèn)題解耦與解碼。最終將問(wèn)題耦合特性融入HEDA_RH中,利用個(gè)體中出現(xiàn)的兩種塊結(jié)構(gòu)特征設(shè)計(jì)采樣方式,引導(dǎo)全局解空間搜索方向以提升搜索效率,并設(shè)計(jì)矩陣立方學(xué)習(xí)模型對(duì)提出的啟發(fā)式搜索操作進(jìn)行學(xué)習(xí)和積累,在提高解質(zhì)量的同時(shí)增加搜索操作有效性。研究?jī)?nèi)容和結(jié)果作為現(xiàn)有調(diào)度領(lǐng)域的有效補(bǔ)充,以豐富和拓展求解一類復(fù)雜系統(tǒng)集成調(diào)度問(wèn)題思路提供方向。同時(shí),MCISP_PC符合現(xiàn)有一類復(fù)雜系統(tǒng)混合企業(yè)生產(chǎn)實(shí)際,將對(duì)應(yīng)的模型、設(shè)計(jì)的基于多階耦合特性的求解方法用于實(shí)際生產(chǎn)過(guò)程中,能夠?yàn)樘岣哐b配制造企業(yè)生產(chǎn)過(guò)程的整體效率、降低成本、提升智能化生產(chǎn)水平等方面提供方法指導(dǎo)。

后續(xù)研究可圍繞MCISP_PC的模型擴(kuò)展及探尋更加高效的求解方法進(jìn)行。在模型方面,可考慮更多的生產(chǎn)約束和階段,或是建立多目標(biāo)優(yōu)化模型。在求解方面,可探尋如何通過(guò)強(qiáng)化學(xué)習(xí)方法來(lái)簡(jiǎn)化HEDA_RH中的高維度學(xué)習(xí)模型。