本文選題：排序 + 學(xué)習(xí)效應(yīng)��； 參考：《華東理工大學(xué)》2017年碩士論文

【摘要】：排序問(wèn)題作為一類在管理科學(xué)、計(jì)算科學(xué)和控制科學(xué)等領(lǐng)域有著廣泛應(yīng)用的問(wèn)題,近年來(lái)受到了廣泛的關(guān)注。本文基于依賴于工件加工位置的學(xué)習(xí)效應(yīng),研究了單機(jī)和平行機(jī)環(huán)境下的三個(gè)排序問(wèn)題:最小化時(shí)間表長(zhǎng)的兩臺(tái)平行機(jī)問(wèn)題,最小化加權(quán)完工時(shí)間和的單機(jī)排序問(wèn)題以及最小化最大延遲的單機(jī)排序問(wèn)題。這三個(gè)問(wèn)題均為NP-hard問(wèn)題。對(duì)于平行機(jī)上帶學(xué)習(xí)效應(yīng)的時(shí)間表長(zhǎng)問(wèn)題,本文首先建立了求解該問(wèn)題最優(yōu)解的整數(shù)規(guī)劃模型,其次,基于模擬退火算法給出了該問(wèn)題的近似算法SA,并證明了該算法依概率1全局收斂到最優(yōu)解,并通過(guò)數(shù)值模擬對(duì)所提出的算法進(jìn)行了性能分析。數(shù)值模擬結(jié)果表明,本文提出的近似算法SA可以達(dá)到最優(yōu)值的99%,準(zhǔn)確度高,算法較有效。對(duì)于單機(jī)環(huán)境下帶學(xué)習(xí)效應(yīng)的最小化加權(quán)完工時(shí)間和問(wèn)題,本文討論了它的三種特殊情形:P_j=P,w_j=w以及w_j =kP_j,說(shuō)明了在這三種特殊情況下,問(wèn)題均為多項(xiàng)式時(shí)間可解的,分別給出了問(wèn)題的算法并證明了算法的最優(yōu)性。我們還研究了單機(jī)環(huán)境下帶學(xué)習(xí)效應(yīng)的最小化最大延遲問(wèn)題,討論了問(wèn)題的三種特殊情形:P_j=P,d_j= d以及d_j= kP_j,說(shuō)明了在這三種特殊情況下,問(wèn)題均為多項(xiàng)式時(shí)間可解的,分別給出了問(wèn)題的算法并證明了算法的最優(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.

【學(xué)位授予單位】：華東理工大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位授予年份】：2017
【分類號(hào)】：O223

【相似文獻(xiàn)】

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

1 張淑娟;楊明明;韓翔凌;;帶學(xué)習(xí)效應(yīng)的供應(yīng)鏈排序算法研究[J];濱州學(xué)院學(xué)報(bào);2010年06期

2 楊明明;;具有學(xué)習(xí)效應(yīng)和遺忘效應(yīng)的間歇批生產(chǎn)的單機(jī)排序問(wèn)題[J];棗莊學(xué)院學(xué)報(bào);2010年05期

3 王吉波,王明征,夏尊銓;具有一般學(xué)習(xí)效應(yīng)的單機(jī)排序問(wèn)題(英文)[J];數(shù)學(xué)研究與評(píng)論;2005年04期

4 楊明明;張淑娟;韓翔凌;;具有學(xué)習(xí)效應(yīng)的間歇批生產(chǎn)的單機(jī)排序問(wèn)題[J];重慶師范大學(xué)學(xué)報(bào)(自然科學(xué)版);2011年03期

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

6 婁敏;婁宗山;;極小化兩種目標(biāo)函數(shù)的具有學(xué)習(xí)效應(yīng)的單機(jī)排序問(wèn)題[J];泰山學(xué)院學(xué)報(bào);2011年06期

7 劉洋;唐恒永;趙傳立;;同時(shí)具有學(xué)習(xí)效應(yīng)和退化效應(yīng)的單機(jī)排序問(wèn)題[J];運(yùn)籌與管理;2012年03期

8 苑麗華;朱路寧;;一類具有學(xué)習(xí)效應(yīng)的分批排序問(wèn)題[J];棗莊學(xué)院學(xué)報(bào);2009年02期

9 徐海燕;;一類基于開(kāi)工時(shí)間惡化效應(yīng)和基于位置學(xué)習(xí)效應(yīng)的單機(jī)調(diào)度問(wèn)題的求解[J];湖南師范大學(xué)自然科學(xué)學(xué)報(bào);2013年06期

10 王純;趙傳立;;帶有學(xué)習(xí)效應(yīng)和機(jī)器可用性限制的排序問(wèn)題[J];系統(tǒng)工程與電子技術(shù);2009年06期

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

1 張雪菲;機(jī)器具有學(xué)習(xí)效應(yīng)的博弈排序問(wèn)題[D];曲阜師范大學(xué);2015年

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

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

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

5 吳祝紅;中國(guó)企業(yè)對(duì)外直接投資的學(xué)習(xí)效應(yīng)及其路徑檢驗(yàn)[D];暨南大學(xué);2016年

6 周博;工程施工中的學(xué)習(xí)效應(yīng)及應(yīng)用[D];西安建筑科技大學(xué);2016年

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

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

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

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

，

本文編號(hào)：1828384