【摘要】：在傳統(tǒng)的排序中,工件的加工時(shí)間是一個(gè)固定不變的參數(shù),工件在機(jī)器上依次加工。但根據(jù)實(shí)際的需要,工件的實(shí)際加工時(shí)間已不再是固定不變的參數(shù),而是與實(shí)際問題相關(guān)的函數(shù)。本文主要研究工件的加工時(shí)間是可變的單機(jī)排序問題。其中,工件的實(shí)際加工時(shí)間是與工件位置和開始加工時(shí)間有關(guān)的函數(shù)。本文具體研究內(nèi)容概括如下:1)在工件同時(shí)帶有學(xué)習(xí)效應(yīng)和惡化效應(yīng)的單機(jī)排序問題中,工件的學(xué)習(xí)效應(yīng)是與工件的實(shí)際加工位置相關(guān)的函數(shù),工件的惡化效應(yīng)是與工件的開始加工時(shí)間相關(guān)的線性函數(shù)。討論單機(jī)情況下工件最大完工時(shí)間、總完工時(shí)間及總完工時(shí)間的絕對差之和的問題,證明了這些問題都是多項(xiàng)式時(shí)間可解的。進(jìn)一步,在線性資源分配情況下,討論了帶有學(xué)習(xí)效應(yīng)、惡化效應(yīng)和資源分配的工期指派問題,工件有一個(gè)共同的工期。目的為確定最優(yōu)工期、最優(yōu)資源分配量及工件加工順序,使公共工期、提前、延誤和資源分配之和為最小。通過將其轉(zhuǎn)化為指派問題,證明了帶有學(xué)習(xí)效應(yīng)、惡化效應(yīng)和資源分配的工期指派問題是多項(xiàng)式時(shí)間可解的。2)工件的學(xué)習(xí)效應(yīng)是與工件的實(shí)際加工位置相關(guān)的一般函數(shù),工件的惡化效應(yīng)是與工件的開始加工時(shí)間相關(guān)的線性函數(shù),分別得到了最大完工時(shí)間、總完工時(shí)間及總完工時(shí)間的絕對差之和問題的多項(xiàng)式時(shí)間算法。3)在機(jī)器在惡化維修時(shí)間的情況下,工件的實(shí)際加工時(shí)間是與工件基本加工時(shí)間和工件實(shí)際加工位置相關(guān)的一般函數(shù)。確定了最優(yōu)工期、加工順序及機(jī)器維修位置,使提前、延誤和工期的之和最小。通過將這個(gè)問題轉(zhuǎn)化為指派問題,證明了該問題在多項(xiàng)式時(shí)間內(nèi)是可解的,并給出此問題的一種特殊情況的最優(yōu)算法。
[Abstract]:In the traditional sorting, the processing time of the workpiece is a fixed and invariant parameter, and the workpiece is processed on the machine in turn. However, according to the actual needs, the actual processing time of the workpiece is no longer a fixed parameter, but a function related to the actual problem. This paper focuses on the single machine scheduling problem in which the processing time of the workpiece is variable. The actual processing time of the workpiece is a function related to the position and the starting time of the workpiece. The specific contents of this paper are summarized as follows: 1) in the single machine scheduling problem where the workpiece has both learning effect and deterioration effect, the learning effect of the workpiece is a function related to the actual processing position of the workpiece. The deterioration effect of the workpiece is a linear function related to the starting time of the workpiece. This paper discusses the sum of the absolute difference between the maximum completion time, the total completion time and the total completion time of the workpiece in the case of single machine, and proves that these problems are solvable with polynomial time. Furthermore, in the case of linear resource allocation, the assignment problem with learning effect, deterioration effect and resource allocation is discussed. The workpiece has a common duration. In order to determine the optimal time limit, the optimal allocation of resources and the processing order of the workpiece, the sum of common time limit, advance time, delay and resource allocation is minimized. By transforming it into assignment problem, it is proved that the assignment problem with learning effect, deterioration effect and resource allocation is polynomial time solvable. 2) the learning effect of workpiece is a general function related to the actual processing position of workpiece. The deterioration effect of the workpiece is a linear function related to the starting time of the workpiece, and the maximum completion time is obtained respectively. A polynomial time algorithm for summing the absolute difference between the total completion time and the total completion time. 3) when the machine is deteriorating the maintenance time, The actual processing time of the workpiece is a general function related to the basic processing time of the workpiece and the actual machining position of the workpiece. The optimal duration, processing sequence and machine maintenance position are determined to minimize the sum of advance, delay and duration. By transforming the problem into an assignment problem, it is proved that the problem is solvable in polynomial time, and an optimal algorithm for the special case of the problem is given.
【學(xué)位授予單位】：沈陽師范大學(xué)
【學(xué)位級別】：碩士
【學(xué)位授予年份】：2015
【分類號】：O223

【相似文獻(xiàn)】

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

1 周泓,張惠民;求解多目標(biāo)作業(yè)排序問題的遺傳算法[J];系統(tǒng)工程理論與實(shí)踐;2001年08期

2 周泓,姬彬;求解作業(yè)排序問題的通用混合遺傳算法研究[J];系統(tǒng)工程理論與實(shí)踐;2001年12期

3 陳德伍,張 峰;一類新的可控排序問題(英文)[J];運(yùn)籌學(xué)學(xué)報(bào);2001年04期

4 張瑞,劉國珍;單機(jī)排序問題最優(yōu)解方法[J];聊城師院學(xué)報(bào)(自然科學(xué)版);2001年02期

5 黎群;單臺機(jī)器多目標(biāo)作業(yè)排序問題的探討[J];系統(tǒng)工程理論方法應(yīng)用;2001年02期

6 方保昒,徐漢忠;用單親遺傳算法解具有窗口式交貨期的多機(jī)加工排序問題[J];系統(tǒng)工程理論方法應(yīng)用;2001年04期

7 宋政芳,孫世杰,吳春燕;一個(gè)超前有獎(jiǎng)遲后受罰的排序問題(英文)[J];運(yùn)籌學(xué)學(xué)報(bào);2002年04期

8 趙傳立,唐恒永;具有相關(guān)調(diào)整時(shí)間的排序問題[J];沈陽師范學(xué)院學(xué)報(bào)(自然科學(xué)版);2002年01期

9 鄭自途;關(guān)于"三臺以上機(jī)床作業(yè)排序問題"的算法[J];天津理工學(xué)院學(xué)報(bào);2002年04期

10 張玉忠,苗翠霞;復(fù)制法及其在分批排序問題中的應(yīng)用[J];曲阜師范大學(xué)學(xué)報(bào)(自然科學(xué)版);2004年02期

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

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

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

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

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

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

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

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

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

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

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

相關(guān)重要報(bào)紙文章 前1條

1 山東 趙玉勇;數(shù)組，你的規(guī)律機(jī)器[N];電腦報(bào);2004年

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

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

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

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

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

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

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

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

8 丁國生;多代理競爭排序問題的研究[D];上海大學(xué);2009年

9 葉德仕;通訊網(wǎng)絡(luò)中排序問題的若干在線和高性能算法[D];浙江大學(xué);2005年

10 王成飛;幾類新型在線分批排序問題[D];曲阜師范大學(xué);2011年

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

1 董柳毅;與誤工有關(guān)的多目標(biāo)排序問題[D];重慶師范大學(xué);2009年

2 王迅娣;成組加工排序和供應(yīng)鏈在線排序問題[D];曲阜師范大學(xué);2010年

3 王潔明;有關(guān)代理競爭排序問題的研究[D];華東理工大學(xué);2011年

4 劉麗麗;分批排序問題[D];曲阜師范大學(xué);2000年

5 鄢楚楠;2，4-逆序變換的置換排序問題[D];浙江大學(xué);2006年

6 張兵權(quán);單位加工時(shí)間的公共時(shí)間窗單機(jī)分組排序問題[D];浙江大學(xué);2006年

7 姜冠成;分批排序問題和資源約束排序問題[D];蘇州大學(xué);2005年

8 胡榮;一類分裝式排序問題的計(jì)算方法和計(jì)算復(fù)雜性研究[D];武漢科技大學(xué);2006年

9 馬蕾;帶傳遞時(shí)間的通信模型中的樹約束排序問題[D];蘭州大學(xué);2007年

10 王小明;不允許等待的混合流水兩車間排序問題[D];清華大學(xué);2002年

，

本文編號：2265979