本文關(guān)鍵詞： flow shop調(diào)度 蛙跳算法 不確定性 異步進(jìn)化　出處：《華東理工大學(xué)》2011年碩士論文　論文類型：學(xué)位論文

【摘要】：生產(chǎn)計(jì)劃和調(diào)度處于計(jì)算機(jī)集成制造系統(tǒng)的核心位置,它向上對企業(yè)的經(jīng)營戰(zhàn)略決策層負(fù)責(zé),向下對監(jiān)控控制層發(fā)出控制指令,確保生產(chǎn)的有序進(jìn)行,是CIMS成功實(shí)施與否的關(guān)鍵。生產(chǎn)調(diào)度問題關(guān)系著企業(yè)成本的控制和利益的最大化,對于促進(jìn)我國的制造業(yè)走向全球化、信息化、集成化有著深遠(yuǎn)的影響。Flowshop調(diào)度是一個典型的調(diào)度問題,本文著重研究通過設(shè)計(jì)和改進(jìn)智能優(yōu)化算法來解決flow shop調(diào)度問題,并通過大量的仿真實(shí)驗(yàn),驗(yàn)證了所提算法的可行性和有效性。 對于以Makespan為目標(biāo)的置換flow shop問題,引入了一種新的智能優(yōu)化算法蛙跳算法,蛙跳算法融合了SCE (Shuffled Complex Evolution)算法和離散粒子群算法的優(yōu)良思想,實(shí)現(xiàn)了全局的信息共享。針對蛙跳算法容易產(chǎn)生非法調(diào)度的問題,設(shè)計(jì)了一種新青蛙跳躍規(guī)則來改善基本蛙跳算法的算法性能,仿真實(shí)驗(yàn)表明改進(jìn)的蛙跳算法比基本的蛙跳算法和遺傳算法更加有效。 對于加工時間不確定的flow shop調(diào)度問題,通過模糊數(shù)學(xué)的方法來描述加工時間的不確定性,在基本蛙跳算法的基礎(chǔ)上,借鑒交換子和交換序的概念,提出了“交換序構(gòu)造的初始位置隨機(jī)機(jī)制”和“交換子的隨機(jī)插入機(jī)制”這兩種追蹤策略。通過與遺傳算法比較,仿真實(shí)驗(yàn)結(jié)果驗(yàn)證了改進(jìn)蛙跳算法在解決具有不確定性加工時間的flow shop問題上的有效性。 對于以總流經(jīng)時間為目標(biāo)的置換flow shop問題,提出了一種全新的遺傳算法,異步遺傳局部搜索算法AGA (Asynchronous Genetic Local Search Algorithm)。AGA包含三個階段：在第一個階段產(chǎn)生隨機(jī)的初始種群,其中的一個解由構(gòu)造型的啟發(fā)式算法產(chǎn)生；在第二個階段,種群內(nèi)的個體兩兩配對,進(jìn)行異步進(jìn)化操作,其中運(yùn)用了一個簡單的交叉算子和一個加強(qiáng)的鄰域搜索策略；在最后一個階段,采用一個重啟策略來防止算法陷入局部極小。仿真實(shí)驗(yàn)表明,AGA比一些經(jīng)典的算法和兩個最近提出的后啟發(fā)式算法更加有效,同時對于90個Benchmark問題,AGA得到了89個目前已知的最優(yōu)解,其中54個是由AGA最新得到的。
[Abstract]:Production planning and scheduling is the core of the computer integrated manufacturing system, which is responsible for the management strategy decision level of the enterprise, and issues control instructions to the monitoring and control layer to ensure the orderly production. Production scheduling is the key to the successful implementation of CIMS. The problem of production scheduling is related to the control of enterprise cost and the maximization of benefits. Integration has far-reaching influence. Flow shop scheduling is a typical scheduling problem. This paper focuses on the design and improvement of intelligent optimization algorithm to solve flow shop scheduling problem, and through a large number of simulation experiments. The feasibility and effectiveness of the proposed algorithm are verified. For the permutation flow shop problem with Makespan as the target, a new intelligent optimization algorithm is introduced. The leapfrog algorithm combines the excellent ideas of SCE Shuffled Complex Evolution algorithm and discrete Particle Swarm Optimization algorithm. The global information sharing is realized. A new frog jump rule is designed to improve the performance of the basic frog jump algorithm. Simulation results show that the improved leapfrog algorithm is more effective than the basic leapfrog algorithm and genetic algorithm. For the flow shop scheduling problem with uncertain processing time, the uncertainty of processing time is described by fuzzy mathematics. Based on the basic leapfrog algorithm, the concepts of commutator and exchange order are used for reference. In this paper, two kinds of tracking strategies are proposed, namely, the initial position random mechanism of commutative order construction and the random insertion mechanism of commutator. The simulation results show that the improved leapfrog algorithm is effective in solving the flow shop problem with uncertain processing time. For the permutation flow shop problem with total flowing time as the target, a new genetic algorithm is proposed. The asynchronous genetic local search algorithm AGA / Asynchronous Genetic Local Search Algorithm).AGA consists of three stages: generating random initial population in the first stage. One of the solutions is generated by a constructive heuristic algorithm, and in the second stage, the individuals in the population are paired together to perform asynchronous evolutionary operations, in which a simple crossover operator and an enhanced neighborhood search strategy are used. In the final phase, a restart strategy is adopted to prevent the algorithm from falling into local minimization. The simulation results show that the algorithm is more effective than some classical algorithms and two recently proposed post-heuristic algorithms. At the same time, 89 known optimal solutions are obtained for 90 Benchmark problems, 54 of which are obtained by AGA.
【學(xué)位授予單位】：華東理工大學(xué)
【學(xué)位級別】：碩士
【學(xué)位授予年份】：2011
【分類號】：TH166

【參考文獻(xiàn)】

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

1 徐震浩,顧幸生;不確定條件下的flow shop問題的免疫調(diào)度算法[J];系統(tǒng)工程學(xué)報(bào);2005年04期

2 劉民,吳澄,蔣新松;用遺傳算法解決并行多機(jī)調(diào)度問題[J];系統(tǒng)工程理論與實(shí)踐;1998年01期

，

本文編號：1544157