本文選題：排序 + 速率修改活動(dòng)��； 參考：《寧波大學(xué)》2017年碩士論文

【摘要】：組合優(yōu)化是運(yùn)籌學(xué)和理論計(jì)算機(jī)科學(xué)的一個(gè)重要分支,其中,人們熱衷于討論的一個(gè)方向便是排序問(wèn)題.一般排序模型是在一定的工件特征和機(jī)器環(huán)境下考慮的.近年來(lái),隨著實(shí)際生產(chǎn)需求的不斷提高和改變,逐漸衍生出一些新的排序問(wèn)題.針對(duì)工件特征,人們研究工件加工時(shí)間可控或者不可控的問(wèn)題.針對(duì)機(jī)器環(huán)境,人們研究機(jī)器需要速率修改活動(dòng)情形下的排序問(wèn)題.速率修改活動(dòng)有兩個(gè)關(guān)鍵的參數(shù),進(jìn)行活動(dòng)的開(kāi)始時(shí)間和活動(dòng)持續(xù)的時(shí)長(zhǎng).不同要求下的參數(shù)對(duì)應(yīng)著不同的排序問(wèn)題.圍繞上述兩點(diǎn)進(jìn)行展開(kāi),本文主要討論了下面兩類新型排序問(wèn)題:帶速率修改活動(dòng)且工件加工時(shí)間離散可控下的單機(jī)排序問(wèn)題和帶速率修改活動(dòng)且工件加工時(shí)間離散可控下的平行機(jī)排序問(wèn)題.全文共分為四章:第一章的緒論中主要介紹了組合優(yōu)化問(wèn)題,排序問(wèn)題及計(jì)算復(fù)雜性的基本概念和相關(guān)知識(shí),系統(tǒng)的總結(jié)了國(guó)內(nèi)外研究現(xiàn)狀和發(fā)展趨勢(shì).第二章研究了帶速率修改活動(dòng)且工件加工時(shí)間離散可控下的單機(jī)排序問(wèn)題,其中速率修改活動(dòng)的時(shí)長(zhǎng)是其開(kāi)始時(shí)刻的非降函數(shù).將給定的n個(gè)獨(dú)立工件J= {J1,J2,…,Jn}安排在一臺(tái)機(jī)器上進(jìn)行加工,每個(gè)工件有多個(gè)加工時(shí)間可選,當(dāng)工件的加工時(shí)間不同時(shí),其對(duì)應(yīng)的加工成本也不相同.此外,我們對(duì)機(jī)器是否進(jìn)行速率修改活動(dòng)分情況進(jìn)行討論,目標(biāo)是找到所有工件的最優(yōu)排序,確定每個(gè)工件的加工時(shí)間,加工成本及速率修改活動(dòng)的開(kāi)始時(shí)間,使得目標(biāo)函數(shù)的值最小.當(dāng)極小化目標(biāo)函數(shù)是最大完工時(shí)間加總加工成本時(shí),給出多項(xiàng)式時(shí)間的精確算法.當(dāng)極小化目標(biāo)函數(shù)分別是完工時(shí)間和加總加工成本,提前延遲與截止時(shí)間懲罰和加總加工成本時(shí),也分別設(shè)計(jì)了計(jì)算復(fù)雜度均為O(n4m)的多項(xiàng)式時(shí)間精確算法.第三章對(duì)第二章的內(nèi)容進(jìn)行了拓展,考慮的是帶速率修改活動(dòng)且工件加工時(shí)間離散可控的平行機(jī)排序問(wèn)題,將給定的有n個(gè)獨(dú)立工件的工件集J = {J1, J2,..., Jn}安排在m (m n)臺(tái)機(jī)器(Mi,i= 1,2,…,m)上加工,所有工件在0時(shí)刻同時(shí)到達(dá).每個(gè)工件在每臺(tái)機(jī)器上都有多個(gè)加工時(shí)間可選擇.目標(biāo)仍是給出所有工件的最優(yōu)排序,確定每個(gè)工件的加工時(shí)間,加工成本及速率修改活動(dòng)的開(kāi)始時(shí)間,使得目標(biāo)函數(shù)的值最小.當(dāng)極小化目標(biāo)函數(shù)是最大完工時(shí)間加總加工成本時(shí),給出計(jì)算復(fù)雜度是O(mkn)的算法.當(dāng)極小化目標(biāo)函數(shù)是機(jī)器總負(fù)載加總加工成本時(shí),給出計(jì)算復(fù)雜度是O(nm|+4)的算法,當(dāng)極小化目標(biāo)函數(shù)提前與延誤的懲罰和加總加工成本時(shí),給出計(jì)算復(fù)雜度是O(mkn2 + nm+4)的算法.第四章對(duì)全文進(jìn)行了總結(jié),并給出了今后仍需繼續(xù)探索的方向和內(nèi)容。
[Abstract]:Combinatorial optimization is an important branch of Computer Science in operational research and theory. One of the directions that people are keen on is the sort problem. The general ordering model is considered under certain job features and machine environment. In recent years, with the continuous improvement and change of actual production demand, some new sorts are gradually derived. Problem. In view of the feature of the workpiece, people study the problem of controllable or uncontrollable processing time of the workpiece. In the machine environment, people study the sorting problem under the condition of rate modification. Rate modification activities have two key parameters, starting time of activity and duration of activity. The corresponding parameters are corresponding to different requirements. In this paper, the following two kinds of new sorting problems are discussed in this paper: single machine scheduling with rate modification activities, single machine scheduling with discrete processing time of the workpiece and parallel machine scheduling with rate modification activities and discrete processing time of work pieces. The full text is divided into four chapters: first In the introduction of the chapter, the basic concepts and related knowledge of combinatorial optimization, sorting and computing complexity are introduced, and the research status and development trend at home and abroad are summarized systematically. The second chapter studies the single machine sorting problem with rate modification activities and the discrete-time controllable processing time of the workpiece, in which the rate modification activity is long The non decreasing function of its starting time. The given n independent jobs J= {J1, J2,... Jn} is arranged on a machine. Each workpiece has multiple processing times. When the working time of the workpiece is different, the corresponding processing cost is different. In addition, we discuss the rate modification activities of the machine. The goal is to find the optimal order of all the workpieces and determine the processing of each workpiece. When the minimum target function is the maximum completion time and the total processing cost, the exact algorithm of polynomial time is given. When the minimization target function is the completion time and the total processing cost, the advance delay and the deadline penalty and the sum of the total processing cost are respectively. At the cost of processing, a polynomial time precise algorithm for calculating the complexity of O (n4m) is also designed. The third chapter extends the content of the second chapter, considering the parallel machine sorting problem with the rate modification activity and the discrete processing time of the workpiece. The set of artifacts with a given n independent workpiece is J = {J1, J2,..., Jn} arrangement. On the M (m n) machine (Mi, i= 1,2,... M) is processed, all work pieces arrive at the same time at the same time at 0 time. Each workpiece has multiple processing times on each machine. The target still gives the optimal order of all the workpieces, determines the processing time of each workpiece, the processing cost and rate changes the start time of the activity, making the target function minimum. When minimizing the target function, When the maximum completion time is added to the total processing cost, the calculation complexity is an algorithm of O (MKN). When the minimization objective function is the total machine load plus the total processing cost, the calculation complexity is an algorithm of O (nm|+4). When the penalty and total processing cost of the target function are minimized and the total processing cost is minimized, the computational complexity is O (mkn2 + nm+4). The fourth chapter summarizes the full text and gives directions and contents to be explored in the future.
【學(xué)位授予單位】：寧波大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位授予年份】：2017
【分類號(hào)】：O223

【相似文獻(xiàn)】

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

1 黃春毅;董笑菊;龍環(huán);;用P系統(tǒng)解決排序問(wèn)題[J];上海交通大學(xué)學(xué)報(bào);2008年02期

2 姜振多;孫世杰;吳志剛;;排序問(wèn)題的穩(wěn)定性分析(英文)[J];Journal of Shanghai University(English Edition);2008年01期

3 譚素平;;排序問(wèn)題的分類與特點(diǎn)[J];科技信息;2012年36期

4 越民義,韓繼業(yè);排序問(wèn)題中的一些數(shù)學(xué)問(wèn)題[J];數(shù)學(xué)的實(shí)踐與認(rèn)識(shí);1976年03期

5 越民義,韓繼業(yè);同順序m×n排序問(wèn)題的一個(gè)新方法[J];科學(xué)通報(bào);1979年18期

6 吳家強(qiáng);用分段選優(yōu)法求解“排序問(wèn)題”[J];武漢水利電力學(xué)院學(xué)報(bào);1979年03期

7 戴志勇;;一類排序問(wèn)題最優(yōu)工序定義的等價(jià)性[J];武漢鋼鐵學(xué)院學(xué)報(bào);1979年02期

8 韓繼業(yè);排序問(wèn)題的一個(gè)判別條件和一類特殊的m×n排序問(wèn)題[J];應(yīng)用數(shù)學(xué)學(xué)報(bào);1980年04期

9 吳在德;梁學(xué)信;;排序問(wèn)題計(jì)算加工時(shí)間的一種方法及其一個(gè)應(yīng)用[J];華僑大學(xué)學(xué)報(bào);1981年01期

10 葉懋冬;;關(guān)于過(guò)竿問(wèn)題與多臺(tái)機(jī)床上零件加工的排序問(wèn)題(Ⅰ)[J];浙江大學(xué)學(xué)報(bào);1982年04期

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

1 柏孟卓;唐國(guó)春;;加工時(shí)間可控的同時(shí)加工排序問(wèn)題[A];2006年中國(guó)運(yùn)籌學(xué)會(huì)數(shù)學(xué)規(guī)劃分會(huì)代表會(huì)議暨第六屆學(xué)術(shù)會(huì)議論文集[C];2006年

2 張蓮珠;;關(guān)于六角鏈的極值和排序問(wèn)題的一些結(jié)果[A];中國(guó)運(yùn)籌學(xué)會(huì)第六屆學(xué)術(shù)交流會(huì)論文集（上卷）[C];2000年

3 周支立;李懷祖;;有重疊區(qū)域的兩抓鉤周期性排序問(wèn)題的求解[A];Systems Engineering, Systems Science and Complexity Research--Proceeding of 11th Annual Conference of Systems Engineering Society of China[C];2000年

4 孫世杰;陳躍;;參數(shù)可控的排序問(wèn)題[A];2001年全國(guó)數(shù)學(xué)規(guī)劃及運(yùn)籌研討會(huì)論文集[C];2001年

5 張玉忠;;分批排序問(wèn)題研究[A];中國(guó)運(yùn)籌學(xué)會(huì)第七屆學(xué)術(shù)交流會(huì)論文集（上卷）[C];2004年

6 張玉忠;;分批排序問(wèn)題研究[A];中國(guó)運(yùn)籌學(xué)會(huì)第七屆學(xué)術(shù)交流會(huì)論文集（中卷）[C];2004年

7 譚萬(wàn)達(dá);;二元對(duì)比排序中的最少逆序原理[A];中國(guó)系統(tǒng)工程學(xué)會(huì)模糊數(shù)學(xué)與模糊系統(tǒng)委員會(huì)第五屆年會(huì)論文選集[C];1990年

8 呂緒華;楊漢興;;求解裝配式排序問(wèn)題的歸并算法及其性能比研究[A];中國(guó)運(yùn)籌學(xué)會(huì)第六屆學(xué)術(shù)交流會(huì)論文集（下卷）[C];2000年

9 樊保強(qiáng);;帶倉(cāng)儲(chǔ)約束的準(zhǔn)時(shí)排序問(wèn)題[A];中國(guó)運(yùn)籌學(xué)會(huì)第九屆學(xué)術(shù)交流會(huì)論文集[C];2008年

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

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

1 高強(qiáng);一些現(xiàn)代排序問(wèn)題的算法設(shè)計(jì)與分析[D];華東理工大學(xué);2015年

2 谷存昌;工件的加工和配送協(xié)作排序問(wèn)題[D];曲阜師范大學(xué);2015年

3 殷娜;依賴于資源分配的排序問(wèn)題研究[D];上海大學(xué);2015年

4 仲維亞;供應(yīng)鏈管理中的若干排序問(wèn)題研究[D];浙江大學(xué);2008年

5 尹曉;基因組重組排序問(wèn)題的算法研究[D];山東大學(xué);2010年

6 余煒;若干網(wǎng)絡(luò)排序問(wèn)題的算法和復(fù)雜性研究[D];華東理工大學(xué);2010年

7 張安;帶服務(wù)等級(jí)的在線排序問(wèn)題及相關(guān)問(wèn)題研究[D];浙江大學(xué);2009年

8 鄭睿;鋼鐵生產(chǎn)中的批處理機(jī)作業(yè)排序問(wèn)題算法研究[D];復(fù)旦大學(xué);2009年

9 季敏;當(dāng)代工業(yè)中的若干排序問(wèn)題研究[D];浙江大學(xué);2006年

10 李好好;若干排序問(wèn)題研究[D];浙江大學(xué);2014年

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

1 李姣;帶速率修改活動(dòng)且工件加工時(shí)間離散可控下的排序問(wèn)題研究[D];寧波大學(xué);2017年

2 李韋萱;兩類帶有維修的排序問(wèn)題[D];沈陽(yáng)師范大學(xué);2015年

3 周雨波;與工件釋放時(shí)間和交貨時(shí)間有關(guān)的排序問(wèn)題及近似算法[D];蘭州大學(xué);2015年

4 張龍;優(yōu)化交貨期窗口的單機(jī)供應(yīng)鏈排序問(wèn)題[D];曲阜師范大學(xué);2015年

5 于萌萌;工件帶有惡化效應(yīng)的博弈排序問(wèn)題[D];曲阜師范大學(xué);2015年

6 李雨潔;恒速機(jī)下的有限資源博弈排序最優(yōu)性研究[D];曲阜師范大學(xué);2015年

7 尚明明;帶有GDD假設(shè)的幾類重新排序問(wèn)題研究[D];鄭州大學(xué);2015年

8 黃保斌;分批的供應(yīng)、加工、配送供應(yīng)鏈排序問(wèn)題[D];曲阜師范大學(xué);2015年

9 程琦;交貨期可指派的新型排序問(wèn)題研究[D];東華理工大學(xué);2014年

10 沈園園;不確定環(huán)境下的機(jī)器排序問(wèn)題[D];清華大學(xué);2015年

，

本文編號(hào)：2090983