本文選題：排序 + 學習效應�。� 參考：《華東理工大學》2017年碩士論文

【摘要】：排序問題作為一類在管理科學、計算科學和控制科學等領域有著廣泛應用的問題,近年來受到了廣泛的關注。本文基于依賴于工件加工位置的學習效應,研究了單機和平行機環(huán)境下的三個排序問題:最小化時間表長的兩臺平行機問題,最小化加權完工時間和的單機排序問題以及最小化最大延遲的單機排序問題。這三個問題均為NP-hard問題。對于平行機上帶學習效應的時間表長問題,本文首先建立了求解該問題最優(yōu)解的整數(shù)規(guī)劃模型,其次,基于模擬退火算法給出了該問題的近似算法SA,并證明了該算法依概率1全局收斂到最優(yōu)解,并通過數(shù)值模擬對所提出的算法進行了性能分析。數(shù)值模擬結果表明,本文提出的近似算法SA可以達到最優(yōu)值的99%,準確度高,算法較有效。對于單機環(huán)境下帶學習效應的最小化加權完工時間和問題,本文討論了它的三種特殊情形:P_j=P,w_j=w以及w_j =kP_j,說明了在這三種特殊情況下,問題均為多項式時間可解的,分別給出了問題的算法并證明了算法的最優(yōu)性。我們還研究了單機環(huán)境下帶學習效應的最小化最大延遲問題,討論了問題的三種特殊情形:P_j=P,d_j= d以及d_j= kP_j,說明了在這三種特殊情況下,問題均為多項式時間可解的,分別給出了問題的算法并證明了算法的最優(yōu)性。
[Abstract]:As a class of problems in the fields of management science, computational science and control science, sort problems have been widely used in recent years. Based on the learning effect dependent on the working position of the workpiece, this paper studies three sorting questions in single and parallel machine environments: two parallel machine problems that minimize the length of the timetable, The problem of minimizing the weighted completion time and single machine sorting and minimizing the single machine ordering with maximum delay. These three problems are all NP-hard problems. For the long time problem with learning effect on parallel machines, this paper first establishes an integer programming model for solving the optimal solution of the problem. Secondly, the simulated annealing algorithm is given. The approximate algorithm SA of the problem is proved that the algorithm converges to the optimal solution according to the probability 1, and performs the performance analysis of the proposed algorithm by numerical simulation. The numerical simulation results show that the approximate algorithm SA proposed in this paper can reach 99% of the optimal value, the accuracy is high, and the calculation method is more effective. To minimize the weighted completion time and problem, this paper discusses three special cases of it: P_j=P, w_j=w and w_j =kP_j. It shows that in these three special cases the problem is polynomial time solvable, the algorithm of the problem is given and the optimality of the algorithm is proved. We also study the minimization of the learning effect in a single machine environment. The problem of maximum delay is discussed. Three special cases of the problem are discussed: P_j=P, d_j= D and d_j= kP_j. It shows that in these three special cases the problem is polynomial time solvable, the algorithm is given and the optimality of the algorithm is proved.

【學位授予單位】：華東理工大學
【學位級別】：碩士
【學位授予年份】：2017
【分類號】：O223

【相似文獻】

相關期刊論文 前10條

1 張淑娟;楊明明;韓翔凌;;帶學習效應的供應鏈排序算法研究[J];濱州學院學報;2010年06期

2 楊明明;;具有學習效應和遺忘效應的間歇批生產(chǎn)的單機排序問題[J];棗莊學院學報;2010年05期

3 王吉波,王明征,夏尊銓;具有一般學習效應的單機排序問題(英文)[J];數(shù)學研究與評論;2005年04期

4 楊明明;張淑娟;韓翔凌;;具有學習效應的間歇批生產(chǎn)的單機排序問題[J];重慶師范大學學報(自然科學版);2011年03期

5 楊楓玉;葉春明;;基于學習效應的項目員工調(diào)度模型研究[J];科技與管理;2013年03期

6 婁敏;婁宗山;;極小化兩種目標函數(shù)的具有學習效應的單機排序問題[J];泰山學院學報;2011年06期

7 劉洋;唐恒永;趙傳立;;同時具有學習效應和退化效應的單機排序問題[J];運籌與管理;2012年03期

8 苑麗華;朱路寧;;一類具有學習效應的分批排序問題[J];棗莊學院學報;2009年02期

9 徐海燕;;一類基于開工時間惡化效應和基于位置學習效應的單機調(diào)度問題的求解[J];湖南師范大學自然科學學報;2013年06期

10 王純;趙傳立;;帶有學習效應和機器可用性限制的排序問題[J];系統(tǒng)工程與電子技術;2009年06期

相關碩士學位論文 前10條

1 張雪菲;機器具有學習效應的博弈排序問題[D];曲阜師范大學;2015年

2 邵利潔;考慮學習效應的重復性項目總工期優(yōu)化方法研究[D];華北電力大學;2015年

3 劉佳樂;通脹預期形成中的學習效應：測度、影響因素與政策啟示[D];東北財經(jīng)大學;2015年

4 張仁騫;經(jīng)濟開放與企業(yè)生產(chǎn)率的關系研究[D];南京大學;2016年

5 吳祝紅;中國企業(yè)對外直接投資的學習效應及其路徑檢驗[D];暨南大學;2016年

6 周博;工程施工中的學習效應及應用[D];西安建筑科技大學;2016年

7 王加俊;學習效應下的地震傷員手術調(diào)度問題研究[D];安徽工業(yè)大學;2016年

8 賈馨云;基于學習效應與退化效應的雙渠道供應鏈生產(chǎn)策略研究[D];西南財經(jīng)大學;2016年

9 張小林;基于學習效應的調(diào)度博弈[D];浙江工商大學;2017年

10 楊驃;基于成本學習效應的供應鏈兩階段價格產(chǎn)量和渠道決策研究[D];華中科技大學;2015年

，

本文編號：1828384