本文選題：調(diào)度 + 差異工件��； 參考：《中國科學(xué)技術(shù)大學(xué)》2011年碩士論文

【摘要】：調(diào)度問題是組合優(yōu)化領(lǐng)域中一類重要的問題,它廣泛地應(yīng)用在制造業(yè)、現(xiàn)代物流和網(wǎng)絡(luò)通信等領(lǐng)域,本文主要研究的是生產(chǎn)調(diào)度問題,有效的調(diào)度能夠提高機器利用率、降低成本、增加利潤和提升客戶滿意度。本文的研究目標(biāo)是最小化差異工件平行機批調(diào)度問題的制造時間跨度Cmax,在調(diào)度問題的研究中,Cmax經(jīng)常被用來衡量調(diào)度的性能,與差異工件單機批調(diào)度問題相比,差異工件平行機批調(diào)度問題更接近現(xiàn)實生產(chǎn)活動,而且目前關(guān)于該問題的研究仍然較少。 本文首先簡述了調(diào)度問題的概念、研究意義、分類和參數(shù)表示、經(jīng)典調(diào)度與現(xiàn)代調(diào)度的區(qū)別以及差異工件批調(diào)度問題的概念。同時,我們也簡單介紹了組合優(yōu)化問題的概念與計算復(fù)雜性的相關(guān)基礎(chǔ)知識。 由于差異工件批調(diào)度問題是一類典型的NP-hard問題,所以解決該類問題的關(guān)鍵在于尋求有效的優(yōu)化算法。目前,求解差異工件批調(diào)度問題的主要方法有兩種:(1)數(shù)學(xué)規(guī)劃方法;(2)啟發(fā)式方法。前者雖然可以求得問題的最優(yōu)解,但是只適用在小規(guī)模問題中,后者雖然在大多數(shù)情況下不能得到最優(yōu)解,但是它能有效地解決大規(guī)模問題,在一定時間內(nèi)給出一個在可以接受范圍內(nèi)的近似最優(yōu)解,具有更強的實際可操作性。本文介紹了目前求解差異工件批調(diào)度問題的主要的數(shù)學(xué)規(guī)劃方法和啟發(fā)式方法及其研究情況。 根據(jù)問題的特性,本文設(shè)計了一種面向差異工件平行機批調(diào)度問題的模擬退火遺傳算法(Simulated Annealing Genetic Algorithm,SAGA)。SAGA算法集合了模擬退火算法(Simulated Annealing,SA)和遺傳算法(Genetic Algorithm,GA)在局部搜索與全局搜索能力方面的優(yōu)勢,并改進了遺傳算法的交叉方式和適應(yīng)函數(shù)的標(biāo)定方式。仿真實驗表明,SAGA算法的性能優(yōu)于現(xiàn)有文獻中的兩個經(jīng)典啟發(fā)式規(guī)則FFLPT和BFLPT以及GA算法。 最后,我們總結(jié)了本文的主要工作和創(chuàng)新點,并提出了未來可以繼續(xù)進行研究的方向。
[Abstract]:Scheduling problem is an important problem in the field of combinatorial optimization. It is widely used in manufacturing industry, modern logistics and network communication. Reduce costs, increase profits and improve customer satisfaction. The goal of this paper is to minimize the manufacturing time span of the different workpiece parallel machine batch scheduling problem (Cmax). In the research of the scheduling problem, Cmax is often used to measure the scheduling performance, compared with the differential workpiece single batch scheduling problem. The problem of batch scheduling of parallel machines is closer to real production activities, and the research on this problem is still less. In this paper, the concept of scheduling problem, its significance, classification and parameter representation, the difference between classical scheduling and modern scheduling, and the concept of different job batch scheduling problem are introduced in this paper. At the same time, we also briefly introduce the concept of combinatorial optimization problems and the basic knowledge of computational complexity. Because the differential job batch scheduling problem is a typical NP-hard problem, the key to solve this problem is to find an effective optimization algorithm. At present, there are two main methods for solving batch scheduling problem of different jobs: 1) mathematical programming method and 2) heuristic method. Although the former can obtain the optimal solution of the problem, it is only suitable for the small scale problem. Although the latter can not obtain the optimal solution in most cases, it can effectively solve the large-scale problem. An approximate optimal solution within an acceptable range is given in a certain time, which is more practical and operable. In this paper, the main mathematical programming methods and heuristic methods for solving batch scheduling problems with different jobs and their research situation are introduced. Depending on the nature of the problem, In this paper, a simulated Annealing Genetic algorithm named simulated Annealing Genetic algorithm is designed for batch scheduling of different jobs. The algorithm gathers the advantages of simulated annealing algorithm (SA) and genetic algorithm (GA) in local search and global search. The crossover method of genetic algorithm and the calibration method of adaptive function are improved. The simulation results show that the performance of the algorithm is better than the two classical heuristic rules FFLPT, BFLPT and GA. Finally, we summarize the main work and innovation of this paper, and propose the future research direction.
【學(xué)位授予單位】：中國科學(xué)技術(shù)大學(xué)
【學(xué)位級別】：碩士
【學(xué)位授予年份】：2011
【分類號】：TH186;TP18

【參考文獻】

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

1 邵浩;陳華平;許瑞;程八一;賈兆紅;;優(yōu)化差異工件單機批調(diào)度問題的混合微粒群算法[J];系統(tǒng)工程;2008年12期

2 王栓獅;陳華平;程八一;李燕;;一種差異工件單機批調(diào)度問題的蟻群優(yōu)化算法[J];管理科學(xué)學(xué)報;2009年06期

3 姜樺,李莉,喬非,吳啟迪;蟻群算法在生產(chǎn)調(diào)度中的應(yīng)用[J];計算機工程;2005年05期

4 王常青,操云甫,戴國忠;用雙向收斂蟻群算法解作業(yè)車間調(diào)度問題[J];計算機集成制造系統(tǒng);2004年07期

5 宋曉宇;朱云龍;尹朝萬;李富明;;應(yīng)用混合蟻群算法求解模糊作業(yè)車間調(diào)度問題[J];計算機集成制造系統(tǒng);2007年01期

6 王雪梅，，王義和;模擬退火算法與遺傳算法的結(jié)合[J];計算機學(xué)報;1997年04期

7 楊阿莉;一種改進蟻群算法在車間作業(yè)調(diào)度問題中的研究與應(yīng)用[J];機械與電子;2005年04期

8 王朝暉,陳浩勛,胡保生;一種基于Lagrangian松弛法求解化工批處理過程調(diào)度的方法[J];控制與決策;1997年S1期

9 陳知美,顧幸生;基于蟻群算法的不確定條件下的Job Shop調(diào)度[J];山東大學(xué)學(xué)報(工學(xué)版);2005年04期

10 高尚,鐘娟 ,莫述軍;多處理機調(diào)度問題的蟻群算法[J];微型電腦應(yīng)用;2003年04期

本文編號：1912577