本文關(guān)鍵詞： 調(diào)度 拉格朗日松弛法 逐步次梯度法 可行解　出處：《上海交通大學(xué)》2014年碩士論文　論文類型：學(xué)位論文

【摘要】：調(diào)度作為生產(chǎn)制造系統(tǒng)中一個(gè)重要的環(huán)節(jié)，其質(zhì)量的好壞直接影響到生產(chǎn)的成本以及企業(yè)的服務(wù)聲譽(yù)。但是在實(shí)際生產(chǎn)過程中，處理機(jī)的數(shù)量和種類、作業(yè)的性質(zhì)、加工要求和限制、資源的種類和數(shù)量及其對(duì)加工的影響，以及性能指標(biāo)等是錯(cuò)綜復(fù)雜的，這使得產(chǎn)生一個(gè)好的調(diào)度通常是很難的。而且研究表明，大部分調(diào)度問題都具有NP-hard性，因此在實(shí)際應(yīng)用中，一個(gè)有效的調(diào)度算法的目的是在合理的計(jì)算時(shí)間內(nèi)得到一個(gè)較好的近似解。 大量文獻(xiàn)表明基于拉格朗日松弛的調(diào)度算法是一種求解NP-hard的調(diào)度問題的有效算法，，其不僅能提供一個(gè)較好的近似最優(yōu)解，還能為近似解提供一個(gè)下界。但是，該算法的有效性依賴于所構(gòu)造的對(duì)偶問題的求解效率以及可行化方法的優(yōu)劣。本文的研究正是在現(xiàn)有研究工作的基礎(chǔ)上，從這兩個(gè)方面出發(fā)，首先將逐步次梯度法應(yīng)用到對(duì)偶問題的求解，改善對(duì)偶問題的收斂速度，然后對(duì)可行化方法的設(shè)計(jì)進(jìn)行了細(xì)致的分析研究，在幾個(gè)關(guān)鍵環(huán)節(jié)上提出了新的策略，改善了可行解的質(zhì)量。歸納起來，本論文主要做了以下四個(gè)方面的工作： 從拉格朗日松弛法求解一般的優(yōu)化問題出發(fā)，介紹了一般的異順序的作業(yè)調(diào)度問題的數(shù)學(xué)規(guī)劃模型，從松弛問題的構(gòu)造及子問題的求解、對(duì)偶問題求解和解的可行化三個(gè)方面對(duì)基于LR的調(diào)度算法的求解框架進(jìn)行了總結(jié)與歸納。 針對(duì)標(biāo)準(zhǔn)的次梯度法收斂慢的問題，分析了次梯度法的求解特性，為了獲取一個(gè)次梯度，其需要精確求解所有的子問題。受即時(shí)利用信息的思想啟發(fā)，將逐步次梯度法應(yīng)用到對(duì)偶問題的求解，每求解一個(gè)工件級(jí)的子問題就更新一次乘子，闡述了具體的求解步驟，并通過近似的定量分析推導(dǎo)出了一個(gè)確定初始步長(zhǎng)的近似公式，通過大量的仿真驗(yàn)證了算法的有效性。 為了提高可行解的質(zhì)量，對(duì)可行化方法的設(shè)計(jì)展開了較為全面的研究，將其歸納為三個(gè)主要環(huán)節(jié)，對(duì)各個(gè)環(huán)節(jié)的不同做法進(jìn)行了闡述，提出了大窗口策略與插入空閑時(shí)間策略，給出了可行化方法設(shè)計(jì)的指導(dǎo)思想。在不同的加工環(huán)境下對(duì)各個(gè)環(huán)節(jié)的不同做法進(jìn)行大量的仿真比較。 為了輔助調(diào)度算法的設(shè)計(jì)與改進(jìn)，建立一個(gè)針對(duì)學(xué)術(shù)研究的可視化的調(diào)度算法仿真平臺(tái)，尤其是針對(duì)基于LR的調(diào)度算法，該仿真平臺(tái)能實(shí)時(shí)顯示中間迭代過程，同時(shí)繪制松弛解和相應(yīng)可行解的Gantt圖，并能在可行解的Gantt圖上手動(dòng)調(diào)整操作的可行化開工時(shí)間，比較其對(duì)調(diào)度性能的影響。
[Abstract]:As an important link in manufacturing system, the quality of scheduling directly affects the cost of production and service reputation of enterprises, but in the actual production process, the number and type of processors, the nature of the job, Processing requirements and constraints, the types and quantities of resources and their impact on processing, and performance indicators are complex, which makes it difficult to produce a good scheduling, and studies show that most scheduling problems are NP-hard. Therefore, in practical application, the purpose of an effective scheduling algorithm is to obtain a better approximate solution within a reasonable computation time. A large number of literatures show that the Lagrangian relaxation scheduling algorithm is an effective algorithm for solving the NP-hard scheduling problem. It can not only provide a better approximate optimal solution, but also provide a lower bound for the approximate solution. The validity of this algorithm depends on the efficiency of the dual problem and the feasibility method. Firstly, the stepwise subgradient method is applied to the solution of duality problem to improve the convergence rate of duality problem, then the design of feasible method is analyzed and studied in detail, and a new strategy is put forward in several key links. The quality of feasible solution is improved. To sum up, this paper mainly does the following four aspects of work:. Starting from the Lagrangian relaxation method to solve the general optimization problem, the mathematical programming model of the general disordered job scheduling problem is introduced, which is based on the construction of the relaxation problem and the solution of the sub-problem. In this paper, the framework of LR-based scheduling algorithm is summarized in three aspects of the feasibility of solving dual problems. In view of the problem of slow convergence of the standard subgradient method, the characteristics of the subgradient method are analyzed. In order to obtain a subgradient, it is necessary to solve all the subproblems accurately, which is inspired by the idea of instant utilization of information. The stepwise subgradient method is applied to the solution of the dual problem. For each workpiece level subproblem, the multiplier is renewed, and the concrete solution steps are expounded, and an approximate formula for determining the initial step size is derived by the approximate quantitative analysis. The effectiveness of the algorithm is verified by a large number of simulations. In order to improve the quality of the feasible solution, the design of the feasible method is studied comprehensively, which is summed up into three main links, and the different methods of each link are expounded. The strategy of large window and the strategy of inserting idle time are put forward, and the guiding idea of the design of feasible method is given, and a large number of simulation comparisons are carried out in different processing environments. In order to aid the design and improvement of scheduling algorithm, a visual simulation platform for scheduling algorithm is established for academic research, especially for the LR-based scheduling algorithm. The simulation platform can display the intermediate iterative process in real time. At the same time, the Gantt diagram of the relaxation solution and the corresponding feasible solution is drawn, and the feasible start time of the operation can be manually adjusted on the Gantt diagram of the feasible solution to compare its influence on the scheduling performance.
【學(xué)位授予單位】：上海交通大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位授予年份】：2014
【分類號(hào)】：TB497

【共引文獻(xiàn)】

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

1 齊學(xué)梅;;無等待流水調(diào)度問題迭代啟發(fā)式算法[J];安徽師范大學(xué)學(xué)報(bào)(自然科學(xué)版);2009年01期

2 卓奕君;成曄;;面向大型產(chǎn)品裝配的兩維勢(shì)能調(diào)度算法研究[J];北京信息科技大學(xué)學(xué)報(bào)(自然科學(xué)版);2009年04期

3 崔建雙,李鐵克,張文新;混合流水車間調(diào)度模型及其遺傳算法[J];北京科技大學(xué)學(xué)報(bào);2005年05期

4 李裕梅;谷云東;李洪興;;調(diào)度問題Pm|p_j=1,intree|∑C_j的兩個(gè)啟發(fā)式算法[J];北京師范大學(xué)學(xué)報(bào)(自然科學(xué)版);2006年02期

5 袁芬;谷云東;塵非;;關(guān)于模糊工期平行機(jī)調(diào)度問題的若干結(jié)果[J];北京師范大學(xué)學(xué)報(bào)(自然科學(xué)版);2006年03期

6 孫秀平;谷云東;李洪興;;任務(wù)無準(zhǔn)備時(shí)間最小化加權(quán)最大延誤單機(jī)調(diào)度問題的若干結(jié)果[J];北京師范大學(xué)學(xué)報(bào)(自然科學(xué)版);2006年05期

7 程貞敏;李洪興;;允許中斷的同速機(jī)調(diào)度問題的一個(gè)最優(yōu)算法[J];北京師范大學(xué)學(xué)報(bào)(自然科學(xué)版);2008年05期

8 程貞敏;李洪興;谷敏強(qiáng);;最小化時(shí)間表長(zhǎng)的平行機(jī)調(diào)度近似算法研究[J];北京師范大學(xué)學(xué)報(bào)(自然科學(xué)版);2012年01期

9 李曉峰;趙海;杜洪軍;劉小勇;;柔性流水作業(yè)排序問題的貪心算法求解[J];吉林大學(xué)學(xué)報(bào)(信息科學(xué)版);2009年06期

10 賈春玉;一類3×n流水型排序問題新近似最優(yōu)解法的探討[J];長(zhǎng)春大學(xué)學(xué)報(bào);2004年06期

相關(guān)會(huì)議論文 前3條

1 聞?wù)裥l(wèi);;一類平行機(jī)上的任務(wù)指派問題及其動(dòng)態(tài)規(guī)劃算法[A];中國(guó)運(yùn)籌學(xué)會(huì)第九屆學(xué)術(shù)交流會(huì)論文集[C];2008年

2 陳榮軍;唐國(guó)春;;自由作業(yè)環(huán)境下的供應(yīng)鏈排序問題[A];中國(guó)運(yùn)籌學(xué)會(huì)第九屆學(xué)術(shù)交流會(huì)論文集[C];2008年

3 ;The Lagrangian Relaxation based Resources Allocation Methods for Air-to-Ground Operations under Uncertainty Circumstances[A];2009中國(guó)控制與決策會(huì)議論文集（3）[C];2009年

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

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

2 鐘雪靈;帶強(qiáng)制工期非正則目標(biāo)函數(shù)的排序問題研究[D];暨南大學(xué);2010年

3 王楠;發(fā)電調(diào)度優(yōu)化模型與方法研究[D];華北電力大學(xué)（北京）;2011年

4 柳春鋒;工程項(xiàng)目中技能型員工調(diào)度問題研究[D];合肥工業(yè)大學(xué);2011年

5 許瑞;基于蟻群優(yōu)化算法的批調(diào)度問題研究[D];中國(guó)科學(xué)技術(shù)大學(xué);2011年

6 王磊;面向訂單生產(chǎn)的供應(yīng)鏈排序問題研究[D];暨南大學(xué);2011年

7 丁國(guó)生;多代理競(jìng)爭(zhēng)排序問題的研究[D];上海大學(xué);2009年

8 白芳;民航發(fā)動(dòng)機(jī)機(jī)群調(diào)度優(yōu)化與視情維修決策方法研究[D];南京航空航天大學(xué);2009年

9 鄭斐峰;占線訂單排序問題及其競(jìng)爭(zhēng)策略研究[D];西安交通大學(xué);2006年

10 付旭云;機(jī)隊(duì)航空發(fā)動(dòng)機(jī)維修規(guī)劃及其關(guān)鍵技術(shù)研究[D];哈爾濱工業(yè)大學(xué);2011年

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

1 張瑋虹;生產(chǎn)管理中的若干排序問題[D];浙江理工大學(xué);2010年

2 吳麗華;服裝零售供應(yīng)配送中的若干問題研究[D];浙江理工大學(xué);2010年

3 任立莉;可拒絕平行批平行機(jī)與在線平行批兩臺(tái)一致機(jī)排序[D];鄭州大學(xué);2010年

4 孟令玉;基于網(wǎng)絡(luò)流的開放式車間調(diào)度問題研究[D];哈爾濱工程大學(xué);2010年

5 王悅;存在批處理設(shè)備的復(fù)雜產(chǎn)品調(diào)度研究[D];哈爾濱理工大學(xué);2010年

6 于慶蓮;基于靜態(tài)并行時(shí)間確定可增加瓶頸設(shè)備的研究[D];哈爾濱理工大學(xué);2010年

7 蘇勝龍;帶一個(gè)服務(wù)器的兩臺(tái)平行機(jī)半在線排序問題[D];華東理工大學(xué);2011年

8 牟啟燕;帶一個(gè)服務(wù)器的兩臺(tái)機(jī)器自由作業(yè)排序問題的近似算法[D];華東理工大學(xué);2011年

9 陳杰;總延誤問題的一種貪婪啟發(fā)式算法分析[D];華東理工大學(xué);2011年

10 史媛媛;兩類雙目標(biāo)排序問題研究[D];武漢科技大學(xué);2010年

本文編號(hào)：1510668