可重入混合流水車間負(fù)荷平衡排產(chǎn)問(wèn)題研究(終稿)

1、修改稿可重入混合流水車間負(fù)荷平衡排產(chǎn)優(yōu)化問(wèn)題研究 國(guó)家重大科技專項(xiàng)項(xiàng)目（2011ZX02601-005）；遼寧省教育廳項(xiàng)目（L2013237）。韓忠華* * 董曉婷 通訊作者，E-mail：dxt199211* 史海波*(* 沈陽(yáng)建筑大學(xué)信息與控制工程學(xué)院,遼寧 沈陽(yáng) 110168)(* 中國(guó)科學(xué)院沈陽(yáng)自動(dòng)化研究所,遼寧 沈陽(yáng) 110016)摘要：針對(duì)可重入混合流水車間負(fù)荷平衡排產(chǎn)優(yōu)化“排產(chǎn)優(yōu)化“改為”調(diào)度“問(wèn)題，建立可重入混合流水車間負(fù)荷平衡優(yōu)化問(wèn)題數(shù)學(xué)規(guī)劃模型，將工位加工時(shí)間負(fù)荷平衡代價(jià)和總工位等待時(shí)間加權(quán)求和后作為負(fù)荷平衡綜合評(píng)價(jià)指標(biāo)。設(shè)計(jì)了基于工件加工流程的編碼方法并結(jié)合時(shí)間窗約束與最

2、大剩余時(shí)間規(guī)則進(jìn)行解碼，采用動(dòng)態(tài)自適應(yīng)差分進(jìn)化算法(Dynamic Self-adaptive Differential Evolution Algorithm)進(jìn)行全局優(yōu)化。該算法根據(jù)個(gè)體間漢明距離判斷個(gè)體相似度，動(dòng)態(tài)更新具有高相似性的個(gè)體，以增加種群多樣性。并引入了隨停止代數(shù)自適應(yīng)調(diào)整進(jìn)化參數(shù)的策略，以增強(qiáng)躍出局部極值，持續(xù)進(jìn)化的能力。并基于客車制造中涂裝車間多遍彩條工序段的實(shí)例數(shù)據(jù)與已有GA、DE、SADE算法進(jìn)行仿真比較，負(fù)荷平衡評(píng)價(jià)指標(biāo)平均降低幅度超過(guò)20%。關(guān)鍵詞：可重入混合流水車間；負(fù)荷平衡；差分進(jìn)化算法；個(gè)體相似度；涂裝車間Researching on Reentrant Hy

3、brid Flowshop Load Balancing Scheduling ProblemHan Zhonghua* * Dong Xiaoting* Shi Haibo*（* Faculty of Information and Control Engineering, Shenyang Jianzhu University, Shenyang, China 110168) (*. Department of Digital Factory, Shenyang Institute of Automation, CAS, Shenyang, China110016) 校驗(yàn)稿里，英文摘要部分

4、第一單位和第二單位相反了AbstractA mathematical model of reentrant hybrid flowshop was formulated to solve the reentrant hybrid flowshop load balancing scheduling problem, put the weighted summation of the processing time load balancing cost and the total parallel machine waiting time as load balancing comprehen

5、sive evaluation index. A new encoding method based on job processing procedure was designed, coupled with time-window constraint and the largest remaining time rules to finish the decoding process, and also cooperated with Dynamic Self-adaptive Differential Evolution Algorithm to complete the global

6、 optimization. In order to increase the diversity of population, presented a new dynamic population update mechanism on the basis of hamming distance. Furthermore, brought in a self-adaptive parameter adjusting strategy along with stop iterations to enhance the ability to jump out of local extreme v

7、alue. Finally, an example of production scheduling problem for multi-pass color strip procedure in bus manufacturing painting workshop was simulated. Through comparison with GA,DE and SADE algorithm, the results show that the rate of decrease for load balance evaluation index is more than 20% Key wo

8、rds: reentrant hybrid flowshop scheduling problem; load balancing; DE algorithm; individual similarity; painting workshop引言可重入混合流水車間排產(chǎn)優(yōu)化問(wèn)題（Reentrant Hybrid Flowshop scheduling Problem, RHFSP）是以半導(dǎo)體封裝、客車制造為代表的一類生產(chǎn)調(diào)度問(wèn)題?？芍厝牖旌狭魉囬g（Reentrant Hybrid Flowshop, RHFS）與傳統(tǒng)混合流水車間(Hybrid Flowshop, HFS)生產(chǎn)一樣有著固定的工藝

9、流程，它的顯著特點(diǎn)是工件的不同工序可能重復(fù)訪問(wèn)同一設(shè)備或設(shè)備組，從而造成產(chǎn)品加工流程中出現(xiàn)大量的重入加工流 1- 2。HFS具有多任務(wù)、多工序、多并行機(jī)特點(diǎn)，RHFSP多是復(fù)雜的串并混合型可重入問(wèn)題。受可重入工序的制約，加工完的工件需多次回到排產(chǎn)任務(wù)隊(duì)列等待工位和加工順序的再次分配，使得生產(chǎn)系統(tǒng)的不穩(wěn)定性與不確定性增大，各并行工位加工任務(wù)的統(tǒng)計(jì)也愈加困難，再加上HFS并行機(jī)加工能力與不同加工任務(wù)工藝差異的影響，常出現(xiàn)各并行機(jī)之間負(fù)荷嚴(yán)重不平衡現(xiàn)象，即部分設(shè)備空閑或過(guò)載情況頻發(fā)，降低設(shè)備利用率，延長(zhǎng)生產(chǎn)周期。因此，研究可重入混合流水車間負(fù)荷平衡排產(chǎn)優(yōu)化問(wèn)題（Reentrant Hybrid Fl

10、owshop-Load Balancing Scheduling Problem, RHFS-LBSP）具有重要的學(xué)術(shù)意義與工程應(yīng)用價(jià)值。RHFSP自1983年被Graves提出以來(lái)3，已取得較大研究進(jìn)展，Yalaoui等針對(duì)具有多批次帶可重入流的HFSP，提出一種基于模糊邏輯控制器的粒子群算法優(yōu)化最小拖期工件數(shù)4。Hekmatfar研究了只含兩道工序，第一道工序是具有可重入性質(zhì)的HFSP，以最小makespan為優(yōu)化目標(biāo)提出了一種混合遺傳算法5。劉小華，林杰等利用粒子群算法和遺傳算法的互補(bǔ)性，設(shè)計(jì)了一種兩者結(jié)合的混合算法優(yōu)化可重入生產(chǎn)調(diào)度系統(tǒng)6。通過(guò)對(duì)已有關(guān)于RHFSP文獻(xiàn)研究發(fā)現(xiàn)，目前RH

11、FSP的研究普遍集中在最小makespan與交貨期問(wèn)題上，研究方法主要采用的群體智能算法。因此，本文依托具有典型可重入混合流水車間特點(diǎn)的客車涂裝車間多遍彩條工序段問(wèn)題，建立同時(shí)考慮工位加工時(shí)間和工位等待時(shí)間的負(fù)荷平衡綜合評(píng)價(jià)指標(biāo)，并將其作為適應(yīng)度函數(shù)，采用具有較好全局搜索能力的動(dòng)態(tài)自適應(yīng)差分進(jìn)化算法作為全局優(yōu)化方法深入研究RHFS-LBSP。1 RHFS-LBSP描述與數(shù)學(xué)模型在混合流水車間中個(gè)工件加工隊(duì)列進(jìn)行個(gè)工序的加工，工件依照加工流程中工序順序進(jìn)行排產(chǎn)，工件的加工流程中至少有一個(gè)工序是可重入工序，個(gè)工序中至少有一個(gè)工序包含多個(gè)并行工位，工件在并行工位上的加工時(shí)間可以不同，但工件在并行工位

12、上至少要選擇一個(gè)工位進(jìn)行加工，排產(chǎn)結(jié)果要確定工件的工位分配、加工順序以及在其加工流程上每個(gè)工序的開(kāi)工時(shí)間、完工時(shí)間。1.1模型參數(shù)考慮到客車生產(chǎn)加工工時(shí)由車型和加工流程共同決定，增加了對(duì)工件類型的描述。表示加工的工件總數(shù)；表示第個(gè)工件，；表示排產(chǎn)的工序總數(shù)；表示第個(gè)工序，；表示工序的最大并行工位數(shù)；表示工序的第個(gè)工位，；表示加工流程的總數(shù)；表示工件的加工流程，是生產(chǎn)過(guò)程中工件順序經(jīng)過(guò)加工工序的集合，重復(fù)加工的工序會(huì)重復(fù)出現(xiàn)在加工流程中，；表示加工流程中工件經(jīng)過(guò)加工工序的總數(shù)，對(duì)重復(fù)加工的工序進(jìn)行累計(jì)計(jì)數(shù)，；表示加工流程中加工工序的執(zhí)行順序的序號(hào)，；表示工序是在加工流程中第個(gè)執(zhí)行的加工工序；表示

13、工件類型的總數(shù)；表示HFS中能夠生產(chǎn)的工件類型，在客車制造行業(yè)中表示制造車間能夠生產(chǎn)的客車車型，。表示給工件指定的加工流程，；表示工件自身的類型，；表示工件的加工流程中加工工序的總數(shù)。表示工件的加工流程中加工工序的執(zhí)行順序的序號(hào)，；表示工件，其流程中第個(gè)執(zhí)行的工序在工位上的加工開(kāi)始時(shí)間；表示工件，其流程中第個(gè)執(zhí)行的工序在工位上的加工結(jié)束時(shí)間。表示類型的工件，其流程中第個(gè)執(zhí)行的工序中，在工位上的加工時(shí)間；表示工序的工位上的加工工件個(gè)數(shù)。1.2假設(shè)變量和基本約束關(guān)系假設(shè)變量表示工件是否在其流程第個(gè)執(zhí)行的工序中，在工位上的加工狀態(tài)。 (1) (2)(3) ,， (4)， ， (5) (6)公式1和2

14、說(shuō)明排產(chǎn)流程和工件類型與工件是一對(duì)多的關(guān)系，在排產(chǎn)過(guò)程包括的工件中，可能會(huì)存在多個(gè)工件采用同樣加工流程或是多個(gè)工件具有同樣的類型。公式3說(shuō)明在加工流程中可以包含多個(gè)重復(fù)加工的工序（通過(guò)加工順序序號(hào)區(qū)分）；公式4說(shuō)明在具有可重入工序情況下，工件在其加工流程中開(kāi)始加工時(shí)間、加工時(shí)間和結(jié)束加工時(shí)間之間的關(guān)系；公式5說(shuō)明同一工件在其加工流程中連續(xù)加工工序的開(kāi)始加工時(shí)間和結(jié)束加工時(shí)間的之間關(guān)系；公式6說(shuō)明在具有可重入工序的車間中，統(tǒng)計(jì)工位上加工工件的個(gè)數(shù)，要累計(jì)重復(fù)加工工件的數(shù)量.其它約束條件如下：每個(gè)工位在同一時(shí)刻只能加工一個(gè)工件，每個(gè)工件在同一時(shí)刻只能在一個(gè)工位加工；工件加工過(guò)程不允許中斷；涂裝車間

15、中設(shè)有大量緩沖工位,在排產(chǎn)過(guò)程中不考慮緩沖工位限制；現(xiàn)場(chǎng)承載客車的滑殼平移車是人工操作的，時(shí)間難以統(tǒng)計(jì)，所以把轉(zhuǎn)運(yùn)時(shí)間計(jì)入加工時(shí)間。1.3時(shí)間窗約束模型對(duì)可重入HFS-LBSP排產(chǎn)模型進(jìn)行調(diào)整，加入時(shí)間窗約束，使每個(gè)工序在固定的時(shí)間節(jié)點(diǎn)開(kāi)始工作，有利于均勻分配加工任務(wù)，更加均衡各并行機(jī)所承受的負(fù)載，提高設(shè)備利用率7。每個(gè)工序的開(kāi)始加工時(shí)間為，表示兩個(gè)順序相鄰的工序和工序的開(kāi)始加工時(shí)間的時(shí)間間隔。，(7) (8)公式(8)是工序的開(kāi)始加工時(shí)間與工件的開(kāi)工時(shí)間的約束關(guān)系，表示在工序所有工件的開(kāi)工時(shí)間都要大于等于工序開(kāi)始加工時(shí)間。公式9進(jìn)行了修改 (9)如公式(9)所示，如果前一道“前一道”改為“當(dāng)

16、前”工序的工位數(shù)大于等于當(dāng)前“當(dāng)前”改為“緊后”工序的工位數(shù)，則等于在這個(gè)“在這個(gè)”改為“當(dāng)前”工序全部加工任務(wù)的工時(shí)的均值；如果前一道“前一道”改為“當(dāng)前”工序的工位數(shù)小鄰兩于“小鄰兩于”改為“小于等于”當(dāng)前“當(dāng)前”改為“緊后”工序的并行工位數(shù)，則等于相個(gè)“相個(gè)”改為“相鄰兩個(gè)”工序的工位數(shù)比值取整加1，再乘上這個(gè)“這個(gè)”改為“當(dāng)前”工序加工時(shí)間的均值。2 RHFS-LBSP數(shù)學(xué)模型各并行工位有效加工時(shí)間是否均衡是車間負(fù)荷平衡的主要判斷依據(jù)，同時(shí)，工位上加工任務(wù)之間的等待時(shí)間體現(xiàn)車間運(yùn)作效率，所以在研究HFS-LBSP問(wèn)題時(shí)，需要綜合考慮工位加工時(shí)間和工位加工等待時(shí)間，兩者重要程度通過(guò)權(quán)值進(jìn)

17、行體現(xiàn)。2.1 建立基于工位加工時(shí)間的負(fù)荷平衡評(píng)價(jià)指標(biāo)將車間中每一個(gè)工位上的總加工時(shí)間與其所處工序的并行工位加工時(shí)間平均值的差值進(jìn)行平方后再求和，建立基于工位加工時(shí)間的負(fù)荷平衡代價(jià)。 (10)在公式10中表示在工序的工位上的加工時(shí)間之合。其中表示工件根據(jù)其加工流程多次在工序的工位上進(jìn)行加工的加工時(shí)間之和。 (11)在公式11中表示在工序的個(gè)并行機(jī)上的平均加工工時(shí)。 (12)在公式12中，表示基于工位加工時(shí)間的負(fù)荷平衡代價(jià)，越小說(shuō)明并行工位負(fù)荷分配越平衡。2.2 總工位加工等待時(shí)間通過(guò)對(duì)工位在加工過(guò)程中等待時(shí)間進(jìn)行求和得到工位加工等待時(shí)間，作為負(fù)荷平衡問(wèn)題的輔助評(píng)價(jià)指標(biāo)。 (13)在公式13中表

18、示的是工位上每?jī)蓚€(gè)連續(xù)加工工件之間的工位等待時(shí)間之合；表示在工位上進(jìn)行加工工件中的最后一次加工的完工時(shí)間，表示在工位上進(jìn)行加工的工件中最早一次加工的開(kāi)工時(shí)間，二者的差表示工位上加工過(guò)程的時(shí)間跨度，再減去該工位有效加工時(shí)間，得到工位的加工等待時(shí)間之和。 (14)在公式14中表示混合流水車間中所有工位等待時(shí)間之和。2.3 混合流水車間負(fù)荷平衡綜合評(píng)價(jià)指標(biāo)混合流水車間的綜合負(fù)荷平衡評(píng)價(jià)指標(biāo)是將基于工位加工時(shí)間的負(fù)荷平衡代價(jià)和工位加工等待時(shí)間進(jìn)行加權(quán)得到總負(fù)荷平衡代價(jià)，其反映混合流水車間調(diào)度結(jié)果要達(dá)到負(fù)荷平衡所需的代價(jià)。在加權(quán)前使用公式15、公式16進(jìn)行歸一化處理，引入和權(quán)值，滿足條件，進(jìn)一步建立式公

19、式17作為負(fù)荷平衡代價(jià)。通過(guò)歸一化處理使得兩個(gè)代價(jià)的數(shù)值在一個(gè)數(shù)量級(jí)上，有利于更好控制兩者對(duì)于負(fù)荷平衡排刪除“排”優(yōu)化問(wèn)題中作用，其中和分別表示初始種群中負(fù)荷不平衡代價(jià)的最小值和最大值，和分別表示初始種群中工位加工等待時(shí)間的最小值和最大值。 (15)表示基于工位加工時(shí)間負(fù)荷平衡代價(jià)按公式(15)進(jìn)行歸一化處理后的數(shù)值。 (16)工位加工等待時(shí)間按公式(16)進(jìn)行歸一化處理后的數(shù)值 (17)為混合流水車間加權(quán)總負(fù)荷平衡代價(jià)。根據(jù)公式17，混合流水車間負(fù)荷平衡調(diào)度問(wèn)題的優(yōu)化目標(biāo)是。 3 動(dòng)態(tài)自適應(yīng)差分進(jìn)化算法（DSADE）設(shè)計(jì)動(dòng)態(tài)自適應(yīng)差分進(jìn)化算法在經(jīng)典差分進(jìn)化算法（Differential Ev

20、olution Algorithm，DE）8的基礎(chǔ)上，采用了參數(shù)自適應(yīng)策略與種群動(dòng)態(tài)更新機(jī)制，以鞏固算法的進(jìn)化活力與種群個(gè)體的多樣性，進(jìn)一步提高算法的搜素精度與全局搜索能力。3.1編碼和解碼種群中每一個(gè)個(gè)體對(duì)應(yīng)問(wèn)題的一個(gè)解，為了反映可重入工序的特征，個(gè)體中基因編碼依托工件的加工流程，即每個(gè)種子由多段編碼構(gòu)成，每段編碼表述的是每個(gè)工件在加工過(guò)程中所走過(guò)的加工流程。種群的基因表示的是一個(gè)工件在其流程中排位置的工序選擇加工的工位，。的取值為區(qū)間上的一個(gè)隨機(jī)數(shù)，將包含基因的個(gè)體作為混合流水車間排產(chǎn)優(yōu)化解時(shí)，使用的是的值，“”表示取下整數(shù)，即表示出工件在工序選擇加工的工位。每個(gè)工件依據(jù)加工流程構(gòu)成一個(gè)基

21、因編碼段，代表了加工過(guò)程中指定加工工位的數(shù)列，多個(gè)基因片段合并到一起構(gòu)成一個(gè)個(gè)體。，表示出全部工件經(jīng)過(guò)加工流程的工位分配情況。若出現(xiàn)，表示多個(gè)工件的同一道工序在同一個(gè)工位加工，則根據(jù)剩余加工時(shí)間最大規(guī)則確定其加工順序，即把每個(gè)工件剩余的待加工工時(shí)求和，最大者優(yōu)先加工。一個(gè)個(gè)體中包含的基因個(gè)數(shù)是全部工件的流程中工序數(shù)之和，即。這種種群個(gè)體構(gòu)造方法是基于矩陣的編碼方法而來(lái)9，巧妙的依據(jù)加工流程中包含的工序進(jìn)行編碼，以向量序列代替矩陣表示染色體，克服了基于矩陣的編碼方法受矩陣位置信息與元素的限制，無(wú)法描述加工流程中包含可重入工序的缺陷。3.2 種群初始化DE算法通常采用隨機(jī)方法產(chǎn)生初始種群中的解，本

22、文同樣采用隨機(jī)初始化產(chǎn)生種群, 以保證初始種群的分散性。3.3 動(dòng)態(tài)更新機(jī)制在染色體編碼設(shè)計(jì)中，漢明距離常被用來(lái)描述兩個(gè)染色體間的不相似程度?；谌旧w編碼的兩個(gè)個(gè)體間的漢明距離是所有對(duì)應(yīng)位置不同基因的個(gè)數(shù)10。漢明距離越大，相似性越低。當(dāng)種群進(jìn)化到一定代數(shù)后，種群中相似個(gè)體增多，進(jìn)化活力降低，此時(shí)引進(jìn)種群動(dòng)態(tài)更新機(jī)制能有效改善解空間中個(gè)體的分布性，以增強(qiáng)算法的全局搜索性能。具體操作步驟如下：步驟1：將所有個(gè)體按照適應(yīng)度進(jìn)行排序。步驟2：從最優(yōu)個(gè)體開(kāi)始，依照式（18）、（19）、（20）計(jì)算其他個(gè)體與這個(gè)體的相似度，如果大于閥值就說(shuō)明兩個(gè)個(gè)體是相似個(gè)體，找到的相似個(gè)體構(gòu)造一個(gè)臨時(shí)子種群。步驟3

23、：對(duì)剩余個(gè)體，重復(fù)步驟1,2，構(gòu)造臨時(shí)子種群，直到篩選完全部個(gè)體。步驟4：采用初始種群中個(gè)體建立方法建立新個(gè)體，并通過(guò)漢明距離檢測(cè)新個(gè)體與種群中個(gè)體的相似度如果與種群中任意一個(gè)個(gè)體相似度大于閥值則舍棄這個(gè)個(gè)體，繼續(xù)重新生成新個(gè)體。（18）假設(shè)變量表示種群兩個(gè)不同的個(gè)體、中對(duì)應(yīng)基因片段、取整后是否相同，如果相同，表示工件選擇加工工位是否刪除“是否”相同，則，否則。 (19)在公式(19)中表示兩個(gè)個(gè)體相同基因片段的個(gè)數(shù)。 (20)在公式(20)中是個(gè)體之間的相似度，是兩個(gè)個(gè)體相同基因片段的個(gè)數(shù)與個(gè)體的基因總數(shù)的比值，如果大于相似度閥值，則說(shuō)明兩個(gè)個(gè)體相似。3.4進(jìn)化參數(shù)自適應(yīng)調(diào)整策略為了進(jìn)一步改

24、善進(jìn)化停滯的問(wèn)題，防止早熟，文獻(xiàn)11-12提出了基于不同隨機(jī)分布函數(shù)的自適應(yīng)策略，能有效平衡算法的全局探索和局部開(kāi)發(fā)能力,但這些進(jìn)化策略沒(méi)有進(jìn)化過(guò)程的指導(dǎo)，具有很大的盲目性。對(duì)此，本文根據(jù)DE算法實(shí)際進(jìn)化規(guī)律，引進(jìn)了隨停止代數(shù)自適應(yīng)調(diào)整與的策略。如公式15、16所示，在進(jìn)化過(guò)程中，如果一代進(jìn)化沒(méi)有提高進(jìn)化效果，則隨著進(jìn)化停止代數(shù)自適應(yīng)的調(diào)整交叉因子和變異因子。 (20)， (21)3.5 DSADE算法流程這一節(jié)在校驗(yàn)稿中由于版本原因，所有公式都沒(méi)顯示出來(lái)，這里重新對(duì)公式進(jìn)行了編輯，并按編輯給的修改建議做了相應(yīng)修改如圖1所示的是DSADE的算法流程。步驟1 設(shè)置初始化進(jìn)化參數(shù)和記錄進(jìn)化迭代次數(shù)

25、初值。步驟2 進(jìn)化代數(shù)是否大于最大進(jìn)化代數(shù)，如果大于，則保存最優(yōu)解退出優(yōu)化；如果不大于，則繼續(xù)執(zhí)行進(jìn)化。步驟3 對(duì)刪除“對(duì)”采取DE/rand/1/bin方式對(duì)種群進(jìn)行增添“進(jìn)行”差分進(jìn)化運(yùn)算。步驟4 判斷是否找到最優(yōu)個(gè)體和滿足停止進(jìn)化條件，如果滿足停止進(jìn)化條件，則退出優(yōu)化；如果不滿足停止進(jìn)化條件，則繼續(xù)執(zhí)行進(jìn)化。步驟5 如果這代進(jìn)化種群沒(méi)有更新最優(yōu)個(gè)體，則需要記錄停止進(jìn)化代數(shù)=+1，重新調(diào)整精英種群自進(jìn)化交叉算子和變異算子；否則，=0。步驟6 判斷是否進(jìn)化過(guò)程到達(dá)開(kāi)啟動(dòng)態(tài)更新種群相似個(gè)體的代數(shù)，如果<，則表示未到開(kāi)啟動(dòng)態(tài)運(yùn)算過(guò)程的代數(shù)，則轉(zhuǎn)到步驟2執(zhí)行；否則，開(kāi)始動(dòng)態(tài)更新相似性個(gè)體運(yùn)算

26、過(guò)程。步驟7 計(jì)算個(gè)體之間的相似度，將大于相似度閥值的個(gè)體組成臨時(shí)子種群，這些臨時(shí)子群集合為，臨時(shí)子種群集合中包含個(gè)子種群，每個(gè)臨時(shí)子種群中個(gè)體數(shù)。步驟8 設(shè)一個(gè)臨時(shí)新種群中個(gè)體計(jì)數(shù)變量，依次根據(jù)優(yōu)秀個(gè)體保留比例提取每個(gè)臨時(shí)子種群中優(yōu)秀的個(gè)體，即提取適應(yīng)度值符合進(jìn)化趨勢(shì)的個(gè)體，并將提取最優(yōu)秀個(gè)體放入到一個(gè)新種群 中，然后令=+。步驟9 要使得中個(gè)體數(shù)達(dá)到設(shè)定的種群規(guī)模，設(shè)一個(gè)新增加個(gè)體計(jì)數(shù)變量。步驟10 判斷新增個(gè)體計(jì)數(shù)是否大于等于，如果大于等于，則轉(zhuǎn)到步驟12；如果小于，則繼續(xù)執(zhí)行。步驟11 根據(jù)種群個(gè)體建立方法，生產(chǎn)新個(gè)體，判斷這個(gè)新個(gè)體與新種群中每個(gè)個(gè)體的相似度，只要新個(gè)體與中個(gè)體相似度

27、大于相似度閥值，則舍棄這個(gè)新個(gè)體；如果新個(gè)體與中個(gè)體相似度小于等于相似度閥值，則保留這個(gè)新生成的個(gè)體，并將這個(gè)個(gè)體加入到，并將=+1，然后轉(zhuǎn)到步驟10。步驟12 將作為新一代進(jìn)化的種群，并，然后轉(zhuǎn)到步驟2執(zhí)行。圖1 動(dòng)態(tài)自適應(yīng)差分進(jìn)化算法流程4 DSADE算法求解RHFS-LBSP驗(yàn)證分析在客車生產(chǎn)企業(yè)的涂裝車間多遍彩條工序段中，客車車體上噴繪的不同彩條圖案是企業(yè)技術(shù)人員事先依據(jù)彩條模板復(fù)雜程度，將彩條分解成多種顏色，每經(jīng)過(guò)一遍“貼彩條”、“噴漆”、“烘漆”工序噴繪一種顏色，經(jīng)過(guò)多遍噴繪形成整體圖案，所以多遍彩條工序段是典型的可重入生產(chǎn)階段13；該工序段中包含多個(gè)工序、多個(gè)并行工位，并且由于技

28、術(shù)人員工作能力不同導(dǎo)致客車在并行工位上加工工時(shí)不同，所以該工序段又具有典型的混合流水車間特征。針對(duì)涂裝車間多遍彩條工序段的排產(chǎn)問(wèn)題應(yīng)用案例，運(yùn)用遺傳算法（GA）、DE、SADE、DSADE算法進(jìn)行全局優(yōu)化，求解這類具有可重入工序的混合流水車間的負(fù)荷平衡排產(chǎn)問(wèn)題。4.1排產(chǎn)數(shù)據(jù)排產(chǎn)數(shù)據(jù)采用某客車制造企業(yè)的涂裝車間中多遍彩條工序段的實(shí)際生產(chǎn)數(shù)據(jù)，如圖2所示的是多遍彩條工序段工位配置圖。 貼彩條工序貼彩條工序緩沖區(qū)貼彩條工位1貼彩條工位2噴漆工序噴漆工序緩沖區(qū)噴房1噴房3噴房2烘漆工序烘漆工序緩沖區(qū)烘房2烘房3烘房4烘房1圖2 多遍彩條工序段工位配置圖求解包含15輛客車車體的在多遍彩條工序段的負(fù)荷平

29、衡排產(chǎn)優(yōu)化問(wèn)題，工序表示多遍彩條工序段中“貼彩條”、“噴漆”、“烘漆”3個(gè)工序，這3個(gè)工序包含的并行工位數(shù)是，在排產(chǎn)過(guò)程中將“噴漆”工序的漆房和“烘漆”工序的烘房都當(dāng)成工位處理。工件代表15輛待加工客車的車體，15輛客車分屬15個(gè)車型，每個(gè)車型按照其加工流程進(jìn)行加工，客車加工流程信息如表1所示。表1客車加工流程信息表待加工的客車流程流程中工序加工工序的總數(shù)是否重入彩條遍數(shù)，=9，是3，=6，是2，=3，否1多遍彩條工序段客車生產(chǎn)加工時(shí)間如表2所示，每輛客車根據(jù)車型不同，在各工序的加工工時(shí)也不相同?！昂嫫帷惫ば虻暮娣吭诤嫫徇^(guò)程沒(méi)有人工參與，同一車型在不同烘房烘漆的時(shí)間相同，工時(shí)差別只與車型相關(guān)。

30、表2涂裝車間多遍彩條工序段加工時(shí)間表（單位: min）工序工位涂裝車間多遍彩條工序段加工時(shí)間一遍彩條121515121515152012181515152015151812151012201815151218201818151820181518202015181518202525182016201515202020221515252518151515181820222218201820202020202020202020252525252020252525二遍彩條151512101215151512121512101510121815151515201515151818151015151518

31、151515151520202018181818202020三遍彩條101212121010101512151015151510181818表3 每個(gè)工序時(shí)間窗時(shí)間范圍表（單位: min）工序工序工序工序開(kāi)始時(shí)間03575工序間時(shí)間間隔35404.2設(shè)置進(jìn)化參數(shù)驗(yàn)證過(guò)程中采用GA算法、DE算法、SADE算法和DSADE算法進(jìn)行全局優(yōu)化，三種算法設(shè)置的參數(shù)如表4所示，除公共參數(shù)外，還要設(shè)置每種算法特有參數(shù)。表4 進(jìn)化算法配置參數(shù)群體進(jìn)化算法算法特有參數(shù)公共參數(shù)GA算法交叉概率，變異概率種群規(guī)模，最大進(jìn)化代數(shù)，DE算法變異算子，交叉因子SADE算法變異算子，交叉算子DSADE算法變異算子，交叉算子

32、，動(dòng)態(tài)更新相似性個(gè)體算法啟動(dòng)代數(shù)，個(gè)體相似性閥值，保留比例。4.3 評(píng)價(jià)指標(biāo)設(shè)計(jì)為了更好研究分析HFS-LBSP排產(chǎn)結(jié)果，將HFS總負(fù)荷平衡代價(jià)、工位加工等待時(shí)間和基于工位加工時(shí)間的負(fù)荷平衡代價(jià)作為評(píng)價(jià)指標(biāo)，并且增加總設(shè)備利用率和最大完工時(shí)間個(gè)評(píng)價(jià)指標(biāo)，從而體現(xiàn)HFS負(fù)荷平衡排產(chǎn)優(yōu)化效果。(22)公式22中表示的HFS中所有工位的總設(shè)備利用率，是全部工位有效加工時(shí)間與工位工作時(shí)間跨度之比，這個(gè)時(shí)間跨度從工位開(kāi)始第一個(gè)加工任務(wù)到最后加工任務(wù)之間跨度，是一個(gè)時(shí)間段。l 最大完工時(shí)間(23)公式23中表示全部工件在最后一道工序加工完工時(shí)間中最大值，也是全部工件完成加工的時(shí)間。4.4 仿真結(jié)果與分析驗(yàn)

33、證程序采用WPF(Windows Presentation Foundation)技術(shù)開(kāi)發(fā)，使用XAML、C#語(yǔ)言編寫程序代碼，面向企業(yè)網(wǎng)絡(luò)化應(yīng)用環(huán)境的瘦客戶端（Browser/Server，B/S）模式下運(yùn)行，測(cè)試環(huán)境CPU Core2 P8600，主頻2.4G，內(nèi)存為2G，將20次仿真運(yùn)算的平均統(tǒng)計(jì)結(jié)果放入到表4中。其中優(yōu)化目標(biāo)的適應(yīng)度函數(shù)采用公式(12)，其中權(quán)值=0.6和=0.4。表5 排產(chǎn)結(jié)果的評(píng)價(jià)指標(biāo)對(duì)照表評(píng)價(jià)指標(biāo)優(yōu)化算法GADESADEDSADE最優(yōu)解0.11220.101370.099030.05742最差解0.134330.127040.116940.09639平均值0.11

34、9610.115690.105440.08607最優(yōu)解22.1330719.7609717.493229.51797最差解41.9617838.6744533.2084226.66119平均值29.4624329.2314428.8485423.35518最優(yōu)解88617550最差均值112105.989.2573.5最優(yōu)解232235226230最差解256260263286平均值248.2252251.75251.2最優(yōu)解0.938630.957370.947440.96441最差解0.905460.908780.92030.93407平均值0.923530.92

35、7300.938030.94854平均執(zhí)行時(shí)間(S)206.4235187.4821219.7638224.3247從表5中可以看出，采用DSADE算法的RHFS加工時(shí)間負(fù)荷平衡代價(jià)平均值比采用GA、DE、SADE算法分別減少20.73%、20.1%、19.04%。采用DSADE算法的RHFS工位加工等待時(shí)間比采用GA、DE、SADE算法分別減少34.38%、30.59%、17.65%。采用DSADE算法的RHFS-LBSP綜合代價(jià)平均值比采用GA、DE、SADE算法分別減少28.04%、25.60%、18.37%。采用DSADE算法的RHFS總設(shè)備利用率比采用GA、DE、SADE算法都有所提

36、高，最大完工時(shí)間無(wú)明顯變化，說(shuō)明并行機(jī)負(fù)載越均衡，設(shè)備總閑置時(shí)間越小，設(shè)備利用率越高，且并未影響車間的生產(chǎn)效率。實(shí)驗(yàn)結(jié)果證明了在采用相同進(jìn)化代數(shù)條件下，DSADE算法能更好的平衡全局探索能力與局部開(kāi)發(fā)之間矛盾，在進(jìn)化停滯時(shí)能自動(dòng)調(diào)節(jié)控制參數(shù)與種群分布密度及時(shí)躍出局部極值，用該算法求解RHFS-LBSP問(wèn)題，能取得更好優(yōu)化效果。圖3 基于時(shí)間窗的排產(chǎn)結(jié)果Gantt圖圖4 無(wú)時(shí)間窗約束的排產(chǎn)結(jié)果Gantt圖通過(guò)圖3、圖4可以看出對(duì)每道工序設(shè)置加工時(shí)間節(jié)點(diǎn)后，工位加工等待時(shí)間減少，各并行工位負(fù)荷相當(dāng)，設(shè)備利用率提高。 圖5 方案1,2,3,4適應(yīng)度值與訓(xùn)練代數(shù)關(guān)系圖從圖5中可以看出隨著訓(xùn)練代數(shù)的增加

37、，4組方案的適應(yīng)度值都在減少，采用GA進(jìn)化算法的方案1在93代之前迅速下降，在423到674間完成兩次進(jìn)化后停止進(jìn)化；采用DE算法方案2在6代之前迅速下降趨勢(shì)，從382代開(kāi)始停滯進(jìn)化；采用SADE算法的方案3在18代之前持續(xù)下降，之后進(jìn)化速度減慢，但仍保持進(jìn)化趨勢(shì)，在926代以后停滯進(jìn)化。采用DSADE算法的方案4，在6代和1443代內(nèi)保持進(jìn)化活力。方案1與方案2、3、4對(duì)比可見(jiàn)DE算法比GA算法收斂速度快。方案2與方案3的曲線對(duì)比，說(shuō)明加入?yún)?shù)自適應(yīng)策略能加強(qiáng)DE算法躍出局部極值的能力。方案4與方案3曲線對(duì)照證明，引進(jìn)動(dòng)態(tài)種群更新機(jī)制能在保持SADE算法較強(qiáng)局部搜索能力的基礎(chǔ)上進(jìn)一步增強(qiáng)SA

38、DE算法的全局搜索能力。四組方案曲線對(duì)照?qǐng)D證明了采用基于漢明距離動(dòng)態(tài)更新種群的DSADE算法能更持久的保持進(jìn)化活力，增強(qiáng)逃離局部極值的能力，具有更強(qiáng)搜索最優(yōu)解的能力。從另一個(gè)角度來(lái)講，由于本次仿真實(shí)驗(yàn)設(shè)置的進(jìn)化代數(shù)是2000代，四種算法進(jìn)化2000代的時(shí)間有所差別，DSADE算法執(zhí)行時(shí)間稍長(zhǎng)，但可以從進(jìn)化曲線看出，在進(jìn)化過(guò)程中，DSADE算法有較好的進(jìn)化活力，且在取得相同進(jìn)化效果時(shí)，DSADE算法明顯速度快，所需進(jìn)化代數(shù)小。當(dāng)增大進(jìn)化代數(shù)，DSADE能取得更好的進(jìn)化效果，這有待下一步繼續(xù)探究。5結(jié)論本文研究可重入混合流水車間負(fù)荷平衡排產(chǎn)優(yōu)化調(diào)度問(wèn)題，將加工時(shí)間負(fù)荷不平衡代價(jià)和總工位等待時(shí)間加權(quán)

39、求和后作為負(fù)荷平衡綜合評(píng)價(jià)指標(biāo)。全局優(yōu)化方法采用DSADE算法，為適合可重入生產(chǎn)系統(tǒng)的要求，算法的編碼依托工件的加工流程，每個(gè)染色體表示全部工件經(jīng)過(guò)加工流程的工位分配情況，并結(jié)合最大剩余時(shí)間優(yōu)先加工規(guī)則和時(shí)間窗約束進(jìn)行解碼。該算法設(shè)計(jì)了一種基于漢明距離的動(dòng)態(tài)更新種群機(jī)制，實(shí)時(shí)更新具有高相似性個(gè)體，起到保持進(jìn)化活力，增強(qiáng)全局搜索能力的作用，并通過(guò)加入隨著停止代數(shù)自適應(yīng)調(diào)整進(jìn)化參數(shù)的方法，提高躍出局部極值的能力。應(yīng)用算例的結(jié)果表明，相比與經(jīng)典的GA算法、DE算法，帶時(shí)間窗約束的DSADE算法對(duì)可重入混合流水車間負(fù)荷平衡優(yōu)化問(wèn)題具有更好地求解能力。參考文獻(xiàn)1 Cho H M, Bae S J, Ki

40、m J, et al. Bi-objective scheduling for reentrant hybrid flow shop using Pareto genetic algorithm. Computers & Industrial Engineering, 2011, 61(3):529-541.2 Kumar P R. Re-entrant lines. Queueing systems, 1993, 13(1-3): 87-1103 Graves S C, et al. Scheduling of re-entrant flow shops. Journal of Operati