本文選題：兩階段裝配流水車間　切入點(diǎn)：集成調(diào)度　出處：《武漢大學(xué)》2017年碩士論文

【摘要】：兩階段裝配流水車間調(diào)度(Two-Stage Assembly Flowshop Scheduling Problem,TSAFSP)屬于經(jīng)典的組合優(yōu)化問題,廣泛存在于制造企業(yè)中。隨著競爭的加劇,客戶需求的多樣化要求企業(yè)能夠在適當(dāng)?shù)臅r(shí)間完成產(chǎn)品運(yùn)輸,這就需要企業(yè)在確定調(diào)度方案時(shí)能同時(shí)考慮生產(chǎn)階段和運(yùn)輸階段,本文對(duì)兩階段裝配流水車間生產(chǎn)運(yùn)輸集成調(diào)度問題(Two-Stage Assembly Flowshop Scheduling Problem with Batch Delivery,TSAFSP-BD)進(jìn)行了研究。該問題基于實(shí)際生產(chǎn)領(lǐng)域需求,不僅研究制造企業(yè)生產(chǎn)過程中的工件調(diào)度,還研究生產(chǎn)結(jié)束后產(chǎn)品的批量運(yùn)輸,可有效提升企業(yè)整體效率,降低不必要的庫存持有成本、提前懲罰成本、延遲懲罰成本等。TSAFSP-BD問題具有強(qiáng)NP難特性,需要采用近似算法進(jìn)行求解,本文采用混合優(yōu)化策略,提出了一種基于遺傳算法(GeneticAlgorithm,GA)與反向變鄰域搜索(Opposition-Based Variable Neighborhood Search,OVNS)的混合智能優(yōu)化算法GA-OVNS。GA作為一種廣泛應(yīng)用的全局優(yōu)化策略,通過采用交叉、變異操作進(jìn)行優(yōu)化迭代,從而獲取最優(yōu)解。但由于其缺乏連鎖學(xué)習(xí)的能力,局部搜索能力較差,容易導(dǎo)致算法過早收斂。VNS(Variable Neighborhood Search,VNS)作為一種局部搜索算法,通過搜索鄰域結(jié)構(gòu)集獲取最優(yōu)解,其最優(yōu)解的質(zhì)量依賴于鄰域結(jié)構(gòu)。OVNS中結(jié)合了反向?qū)W習(xí)(Opposition-Based Learning,OBL)思想,在構(gòu)造鄰域結(jié)構(gòu)的同時(shí)考慮反向鄰域結(jié)構(gòu),擴(kuò)大鄰域結(jié)構(gòu)集,提升局部搜索能力。因此,本文采用基于GA和OVNS的混合智能優(yōu)化方法GA-OVNS求解TSAFSP-BD問題,能有效提高算法的全局搜索功能和局部搜索功能,主要研究內(nèi)容如下:對(duì)于單客戶下TSAFSP-BD問題,GA-OVNS采用基于工序的擴(kuò)展編碼,即第一行為工件的加工次序,第二行用于劃分產(chǎn)品運(yùn)輸批次,為了提高初始解的質(zhì)量,在隨機(jī)產(chǎn)生的初始種群中加入部分基于SPT(Shortest Processing Time)規(guī)則生成的個(gè)體。種群采取兩點(diǎn)交叉和改進(jìn)變異操作進(jìn)行迭代,每代種群的最優(yōu)解作為OVNS的初始解。OVNS在采用插入、交換、逆序等鄰域結(jié)構(gòu)的同時(shí),通過構(gòu)造基于OBL的反向鄰域結(jié)構(gòu)增加搜索范圍,從而快速有效地快速有效地求解該問題。對(duì)于多客戶下TSAFSP-BD問題,在進(jìn)行迭代的過程中需要明確劃分工件的客戶群體,因此需要針對(duì)提出的GA-OVNS的原有編碼方式行改進(jìn),同時(shí)識(shí)別產(chǎn)品的運(yùn)輸批次以及客戶群體,并在迭代的過程中合理調(diào)整交叉、變異、鄰域搜索等操作,避免出現(xiàn)解碼混亂。考慮到實(shí)際生產(chǎn)中需要同時(shí)優(yōu)化多個(gè)目標(biāo)的情況,本文以最小化庫存持有成本、提前懲罰成本、期懲罰成本以及運(yùn)輸費(fèi)用為目標(biāo),將GA-OVNS和啟發(fā)式啟發(fā)式算法 EDD(Earliest Due Data Rule)、SLACK(Slack Time Rule)以及智能優(yōu)化算法GA、GA-VNS進(jìn)行比較。混合智能優(yōu)化方法各參數(shù)設(shè)置采用正交試驗(yàn)設(shè)計(jì)進(jìn)行確定。通過多組算例測試,實(shí)驗(yàn)結(jié)果表明GA-OVNS的優(yōu)化性能優(yōu)于其他算法。
[Abstract]:Two-Stage Assembly Flowshop Scheduling problem of Two-Stage Assembly Scheduling problem (TSAFSP), which is widely used in manufacturing enterprises, belongs to the classical combinatorial optimization problem.With the intensification of competition, the diversification of customer demand requires enterprises to complete product transportation in an appropriate time, which requires enterprises to consider both production and transportation stages when determining scheduling schemes.In this paper, the Two-Stage Assembly Flowshop Scheduling Problem with Batch delivery problem TSAFSP-BDD of two-stage assembly income workshop is studied.This problem is based on the actual production requirements. It not only studies the scheduling of jobs in the production process of manufacturing enterprises, but also studies the batch transportation of products after the end of production, which can effectively improve the overall efficiency of enterprises and reduce the unnecessary inventory holding costs.The TSAFSP-BD problem has strong NP-hard properties and needs to be solved by approximate algorithm. In this paper, a hybrid optimization strategy is used to solve TSAFSP-BD problem.A hybrid intelligent optimization algorithm (GA-OVNS.GA) based on genetic algorithm (GA) and reverse variable neighborhood search (GA-OVNS.GA) is proposed as a widely used global optimization strategy. The optimal solution is obtained by using crossover and mutation operations.However, due to its lack of linkage learning ability and poor local search ability, it is easy to lead to premature convergence of the algorithm. As a local search algorithm, the optimal solution can be obtained by searching the neighborhood structure set.The quality of the optimal solution depends on the neighborhood structure. OVNS combines the idea of reverse learning Opposition-Based learning OBL.Constructing the neighborhood structure, the reverse neighborhood structure is considered at the same time, the set of neighborhood structures is enlarged, and the local search ability is improved.Therefore, in this paper, the hybrid intelligent optimization method based on GA and OVNS, GA-OVNS, is used to solve the TSAFSP-BD problem, which can effectively improve the global search function and the local search function of the algorithm.The main research contents are as follows: for single customer TSAFSP-BD problem, GA-OVNS adopts the extended coding based on working procedure, that is, the processing order of the first behavior work piece, the second line is used to divide the product transportation batch, in order to improve the quality of the initial solution,An individual generated by the SPT(Shortest Processing time rule is added to the randomly generated initial population.The population adopts two points crossing and improved mutation operation to iterate. The optimal solution of each generation population as the initial solution of OVNS. OVNS uses neighborhood structure such as insert, exchange, reverse order, and increases the search range by constructing the reverse neighborhood structure based on OBL.Thus the problem can be solved quickly and efficiently.For the multi-customer TSAFSP-BD problem, it is necessary to clearly divide the client group of the workpiece in the process of iteration, so it is necessary to improve the original coding method of the proposed GA-OVNS, and identify the transportation batches and customer groups of the product at the same time.In the process of iteration, crossover, mutation, neighborhood search and other operations are adjusted reasonably to avoid decoding confusion.Considering the need to optimize multiple objectives simultaneously in actual production, this paper aims at minimizing inventory holding cost, penalty cost in advance, penalty cost in time and transportation cost.The GA-OVNS is compared with the heuristic heuristic algorithm EDD(Earliest Due Data SLACKSlack Time rule and the intelligent optimization algorithm GAGA-VNS.The parameters of the hybrid intelligent optimization method are determined by orthogonal design.The experimental results show that the optimization performance of GA-OVNS is better than that of other algorithms.
【學(xué)位授予單位】：武漢大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位授予年份】：2017
【分類號(hào)】：TB497

【參考文獻(xiàn)】

相關(guān)期刊論文 前8條

1 謝謝;吳星瑤;李曉麗;孔祥玉;;帶有不可用區(qū)間、工件可拒絕的單機(jī)生產(chǎn)與運(yùn)輸協(xié)調(diào)調(diào)度問題[J];沈陽大學(xué)學(xué)報(bào)(自然科學(xué)版);2015年03期

2 嚴(yán)洪森;萬曉琴;熊福力;;基于VNS-EM混合算法的兩階段裝配流水車間調(diào)度[J];東南大學(xué)學(xué)報(bào)(自然科學(xué)版);2014年06期

3 何啟巍;張國軍;朱海平;劉敏;;一種多目標(biāo)置換流水車間調(diào)度問題的優(yōu)化算法[J];計(jì)算機(jī)系統(tǒng)應(yīng)用;2013年09期

4 宋代立;張潔;;蟻群算法求解混合流水車間分批調(diào)度問題[J];計(jì)算機(jī)集成制造系統(tǒng);2013年07期

5 宮華;唐立新;;并行機(jī)生產(chǎn)與具有等待時(shí)間限制的成批運(yùn)輸協(xié)調(diào)調(diào)度問題[J];控制與決策;2011年06期

6 葛繼科;邱玉輝;吳春明;蒲國林;;遺傳算法研究綜述[J];計(jì)算機(jī)應(yīng)用研究;2008年10期

7 潘全科;王文宏;朱劍英;趙保華;;基于粒子群優(yōu)化和變鄰域搜索的混合調(diào)度算法[J];計(jì)算機(jī)集成制造系統(tǒng);2007年02期

8 徐俊剛,戴國忠,王宏安;生產(chǎn)調(diào)度理論和方法研究綜述[J];計(jì)算機(jī)研究與發(fā)展;2004年02期

，

本文編號(hào)：1708829