資源描述：
《拉格朗日松弛方法在車間調(diào)度中的應(yīng)用研究》由會員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在學(xué)術(shù)論文-天天文庫。
1、上海交通大學(xué)碩士學(xué)位論文拉格朗日松弛方法在車間調(diào)度中的應(yīng)用研究摘要車間調(diào)度問題(Job-shopSchedulingProblem,JSP)是一類具有時間約束、順序約束和資源約束的組合優(yōu)化問題，是制造業(yè)生產(chǎn)規(guī)劃中最為重要的課題之一。車間調(diào)度問題具有NP-hard特性，不能在多項(xiàng)式時間內(nèi)獲得最優(yōu)解，因此大量有效的近似/啟發(fā)式算法得到了應(yīng)用。近似/啟發(fā)算法通常能夠在合理的計(jì)算時間內(nèi)產(chǎn)生調(diào)度結(jié)果，但是常常很難評估這些調(diào)度與最優(yōu)解之間的差距?，F(xiàn)有文獻(xiàn)表明，拉格朗日松弛方法(LagrangianRelax
2、ationApproach,LR)是獲取較好次優(yōu)解的有效方法之一，同時能給出最優(yōu)值的下界（對于最小化問題）以評價調(diào)度結(jié)果的優(yōu)劣，因而在實(shí)際調(diào)度中得到了廣泛應(yīng)用。本文在現(xiàn)有研究的基礎(chǔ)上主要完成以下工作：1.首先介紹了車間調(diào)度問題基于拉格朗日松弛方法的數(shù)學(xué)模型，規(guī)范了相關(guān)的概念以及參數(shù)的定義，剖析了拉格朗日松弛方法的關(guān)鍵技術(shù)環(huán)節(jié)，并在此基礎(chǔ)上建立了基于拉格朗日松弛方法求解車間調(diào)度問題的一般框架。2.針對性能指標(biāo)可分的車間調(diào)度問題，對算法進(jìn)行了研究和實(shí)現(xiàn)，驗(yàn)證了算法的有效性。在此基礎(chǔ)上，進(jìn)行了大量的仿
3、真研究，并分析上海交通大學(xué)碩士學(xué)位論文和討論了影響計(jì)算性能的關(guān)鍵因素。對懲罰因子的震蕩性及由此帶來的可行解不確定性進(jìn)行了分析，進(jìn)而給出了一種修正策略。總結(jié)了懲罰因子分段特性，為基于時間的集結(jié)策略奠定了基礎(chǔ)。3.針對性能指標(biāo)不可分的車間調(diào)度問題，提出了一種基于拉格朗日松弛的求解方法，并且給出了該方法架構(gòu)下的分解條件和一般描述，同時對算法的物理意義進(jìn)行了闡述說明，仿真驗(yàn)證了算法的正確性。4.在本文提出的不可分問題基于拉格朗日松弛方法的求解算法基礎(chǔ)上，針對調(diào)度規(guī)劃時間窗口較長所帶來的計(jì)算時間較長的問題
4、，提出了懲罰因子基于時間的集結(jié)策略對算法進(jìn)行了改進(jìn)，通過對Benchmark算例的仿真驗(yàn)證改進(jìn)算法在不影響調(diào)度結(jié)果的前提下，大大減少了計(jì)算時間。5.針對拉格朗日松弛方法解決不同車間調(diào)度問題時，對問題的依賴性強(qiáng)，算法實(shí)現(xiàn)復(fù)雜。本文提出了拉格朗日算法面向?qū)ο蟮脑O(shè)計(jì)方法，通過分析拉格朗日方法解決不同車間調(diào)度問題的特點(diǎn)，開發(fā)了通用的類模塊，面向?qū)ο蟮哪K關(guān)系和類層次使得算法可擴(kuò)展性強(qiáng)，便于改進(jìn)。仿真結(jié)果表明，用戶可以在該仿真平臺上方便地實(shí)現(xiàn)拉格朗日方法對多種車間調(diào)度問題的仿真，大大提高了代碼的可重用性和
5、軟件的通用性。關(guān)鍵詞：拉格朗日松弛方法，面向?qū)ο螅囬g調(diào)度上海交通大學(xué)碩士學(xué)位論文RESEARCHONLAGRANGIANRELAXATIONAPPROACHSOLVINGJOBSHOPPROBLEMSABSTRACTJob-shopSchedulingProblem(JSP)isacombinatorialoptimizationproblemconstrainedwithtime,sequenceandresource.TheoptimalschedulingsolutionforJSPca
6、nnotbeobtainedinpolynomialtimeduetoitsNP-hardcomputationalcomplexity.Thuslotsofapproximationandheuristicalgorithmshavebeendeveloped,whichcangeneratesatisfactoryscheduleinreasonabletime.Butgenerationofconsistentlygoodscheduleshasproventobeextremelydif
7、ficultandtheperformanceofmostapproximation/heuristicalgorithmsisdifficulttoestimateandvariesgreatlyfromoneproblemtoanother.LiteratureresearchshowsthatLagrangianRelaxationApproach(LR)isoneofthemostefficientwaystoobtainnear-optimalsolutionwhichalsocanc
8、omeupwithalowerbound(astominimizationproblem)toevaluatetheperformanceofthesolution.Recently,LagrangianRelaxation-basedmethodshavebeendevelopedtosolveproblemsofrealisticsize.Themaincontributionofthisdissertationcanbesummarizedasfollows:1.Amathematical
