本文關(guān)鍵詞：差異工件且容量不同的批調(diào)度啟發(fā)式算法研究　出處：《安徽大學(xué)》2015年碩士論文　論文類型：學(xué)位論文

  更多相關(guān)文章： 動(dòng)態(tài)到達(dá) 差異工件批調(diào)度 啟發(fā)式算法 容量不同 平行機(jī)

【摘要】：生產(chǎn)調(diào)度問題是一種應(yīng)用背景非常廣泛的組合優(yōu)化問題,如今已經(jīng)被應(yīng)用到許多實(shí)際生產(chǎn)及生活領(lǐng)域,如物流、現(xiàn)代通訊、生產(chǎn)制造及通信網(wǎng)絡(luò)等。它是指在一段時(shí)間中,對(duì)共享資源進(jìn)行合適的排序分配,且在生產(chǎn)過程中對(duì)各個(gè)任務(wù)進(jìn)行合理的規(guī)劃和分配以達(dá)到某項(xiàng)或者多項(xiàng)目標(biāo)最優(yōu)化的過程,而合理的調(diào)度方案可以提高資源的利用率及生產(chǎn)效率,并降低生產(chǎn)成本,從而提高企業(yè)的競(jìng)爭(zhēng)力,推動(dòng)社會(huì)的發(fā)展。批處理機(jī)調(diào)度是對(duì)經(jīng)典調(diào)度問題的一個(gè)重要擴(kuò)展,在批處理機(jī)調(diào)度中,允許多個(gè)工件同時(shí)在一臺(tái)機(jī)器上進(jìn)行加工,且由于批調(diào)度廣泛應(yīng)用于大規(guī)模的實(shí)踐活動(dòng)中,因而已成為當(dāng)前生產(chǎn)調(diào)度領(lǐng)域的一個(gè)研究熱點(diǎn)。批調(diào)度問題根據(jù)不同的約束條件還會(huì)分出一些新的分支,例如,差異工件的批處理機(jī)調(diào)度,是考慮加工時(shí)間和尺寸均有差異的工件在批處理機(jī)上進(jìn)行加工的調(diào)度問題；動(dòng)態(tài)批調(diào)度是針對(duì)帶有到達(dá)時(shí)間的工件在進(jìn)行加工時(shí),由于工件不是機(jī)器開始加工時(shí)即可用,因而各工件的的加工還要受到不同的影響。這些調(diào)度問題往往更加接近真實(shí)的生產(chǎn)加工環(huán)境,但也因?yàn)橐獌?yōu)化的目標(biāo)函數(shù)種類多、各種約束條件多及它的不確定性等特征而更加復(fù)雜,且其中有許多問題已經(jīng)被證明是NP-難的。因此針對(duì)復(fù)雜的生產(chǎn)環(huán)境,如何去設(shè)計(jì)一個(gè)簡(jiǎn)單而又高效的調(diào)度求解算法始終是批調(diào)度研究領(lǐng)域的一個(gè)重點(diǎn)。本文首先簡(jiǎn)要介紹了生產(chǎn)調(diào)度問題的相關(guān)概念,例如調(diào)度問題通用的三參數(shù)表示法及調(diào)度問題的分類。其次,對(duì)批調(diào)度問題、差異工件批調(diào)度問題及工件動(dòng)態(tài)到達(dá)的差異工件批調(diào)度問題分別進(jìn)行了介紹；再從單機(jī)環(huán)境、并行機(jī)環(huán)境和車間環(huán)境分別介紹了批處理機(jī)調(diào)度問題的研究現(xiàn)狀,并指出了當(dāng)前研究存在的問題。然后詳細(xì)的介紹了求解批調(diào)度問題的方法,并同時(shí)給出了各類求解算法的具體例子,如FFLPT、BFLPT等經(jīng)典的啟發(fā)式算法和蟻群算法、遺傳算法及模擬退火算法等元啟發(fā)式算法。接著,探討了本文研究的動(dòng)態(tài)環(huán)境及機(jī)器容量不同的約束下差異工件批調(diào)度問題。當(dāng)前關(guān)于多機(jī)批調(diào)度的研究中,其約束條件及加工環(huán)境都是比較簡(jiǎn)單的,如工件到達(dá)時(shí)間為0且機(jī)器容量相同,即靜態(tài)調(diào)度環(huán)境。本文針對(duì)工件動(dòng)態(tài)到達(dá)的差異工件且機(jī)器容量不同的批調(diào)度問題進(jìn)行研究,給出了幾種啟發(fā)式優(yōu)化算法對(duì)其分別進(jìn)行求解。將本文的問題分為兩個(gè)子問題：首先采用FFLPT和BFLPT啟發(fā)式規(guī)則將所有工件進(jìn)行分批；然后針對(duì)工件分組所得的批集合,分別采用FFLPT和BFLPT算法進(jìn)行批調(diào)度,將批集合分配到機(jī)器上進(jìn)行加工。此外,在批調(diào)度過程中,通過MultiFit算法來優(yōu)化目標(biāo)函數(shù)。通過仿真實(shí)驗(yàn)對(duì)文中所提的啟發(fā)式算法和下界LB進(jìn)行比較,驗(yàn)證性能并進(jìn)行了性能分析,實(shí)驗(yàn)結(jié)果表明本文所給幾種算法的有效性,其中BB(BFLPT-BFLPT)算法的性能明顯優(yōu)于其他幾種算法。最后,總結(jié)本文的研究內(nèi)容,并對(duì)今后的研究方向進(jìn)行了展望。
[Abstract]:The production scheduling problem is combinatorial optimization problem with a very wide application background, has now been applied to many practical production and life field, such as modern logistics, communications, manufacturing and communication network. It refers to a period of time, sort the appropriate allocation of shared resources, and in the production process rational planning and allocation of tasks to achieve a number of goals or process optimization, and a reasonable control scheme can improve the resource utilization rate and production efficiency, and reduce the production cost, so as to improve the competitiveness of enterprises, promote the development of the society. A batch scheduling is an important extension of the classical scheduling problem in the batch processor scheduling, allowing a plurality of workpieces processed simultaneously on a single machine, and because the batch scheduling is widely used in large-scale practice, which has become the current students A research hotspot in production scheduling field. Batch scheduling problem with different constraints, but also from some new branches, for example, a batch scheduling between the workpiece, is the scheduling problem considering the processing time and size were different processed in batch processor; dynamic batch scheduling is to arrive at the workpiece with time when processing the workpiece, due not to start processing machine is available, so the processing of parts have different effects. These scheduling problems tend to be more close to the real production environment, but also because of the objective function to optimize the multi species, multi constraints and its uncertainty and other characteristics are more complex, and there are many problems have been proved to be NP- hard. So according to the complex production environment, how to design a simple and efficient scheduling algorithm Batch scheduling is always one of the most important research field. This paper firstly introduces the related concepts of the production scheduling problems, such as scheduling problems with three parameters general representation classification and scheduling problem. Secondly, the batch scheduling problem, different workpiece batch scheduling problem and the workpiece to the different workpiece dynamic batch scheduling problem were carried out introduction; from single environment, research status of a batch scheduling problem is introduced parallel machine environment and workshop environment respectively, and points out the problems in current research. Then it introduces the method to solve the batch scheduling problem, and gives specific examples, different algorithms such as FFLPT, BFLPT and other classical heuristic algorithm and ant colony algorithm, genetic algorithm and simulated annealing algorithm and heuristic algorithm. Then, discusses the dynamic environment and the capacity of the machine is studied in this paper under different constraints difference Different batch scheduling problem. The current research on multi machine batch scheduling, the constraints and the processing environment is relatively simple, such as the arrival time is 0 and the capacity of the machine is the same, namely static scheduling environment. This paper studies the dynamic job arrivals different workpieces and machine capacity is not the same batch scheduling problem given several heuristic optimization algorithm to solve them respectively. This problem is divided into two sub problems: first of all the jobs into batches using FFLPT and BFLPT heuristic rules; then according to the number of work grouping sets, respectively using FFLPT and BFLPT algorithm for batch scheduling, the number of sets assigned to the machine. In addition, in the process of batch scheduling, optimization of objective function by the MultiFit algorithm. Based on the proposed heuristic algorithm and the lower bound of LB for simulation, verification of And the performance analysis is carried out. The experimental results show the effectiveness of several algorithms. The performance of BB (BFLPT-BFLPT) algorithm is obviously better than the other algorithms. Finally, the research contents of this paper are summarized, and the future research directions are prospected.

【學(xué)位授予單位】：安徽大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位授予年份】：2015
【分類號(hào)】：F273;TP18

【參考文獻(xiàn)】

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

1 張智聰;鄭力;張濤;;半導(dǎo)體測(cè)試調(diào)度研究[J];半導(dǎo)體技術(shù);2008年01期

2 席裕庚，柴天佑，，惲為民;遺傳算法綜述[J];控制理論與應(yīng)用;1996年06期

相關(guān)博士學(xué)位論文 前2條

1 馬英;考慮維護(hù)時(shí)間的機(jī)器調(diào)度問題研究[D];合肥工業(yè)大學(xué);2010年

2 劉彥鵬;蟻群優(yōu)化算法的理論研究及其應(yīng)用[D];浙江大學(xué);2007年

本文編號(hào)：1432353