本文關鍵詞：幾類加工時間可變的單機排序問題，由筆耕文化傳播整理發(fā)布。

【摘要】：本文考慮幾類加工時間可變的單機排序問題,詳述如下：首先,第一章介紹排序問題的研究背景、研究現(xiàn)狀及研究內(nèi)容。其次,第二章針對帶有學習效應、加工時間可控和退化工件在單機環(huán)境下進行了研究,目標為確定工件最優(yōu)排序、最優(yōu)加工時間和最優(yōu)資源分配量,將最大完工時間、總完工時間、完工時間差和資源消耗的費用之和進行極小化�？紤]了學習因子與工件有關的線性資源函數(shù),學習效應與工件的實際加工時間依賴開始時間結合在一起的凸資源函數(shù)兩種情況,通過分析最優(yōu)解的一些重要性質(zhì),將這兩個問題分別轉(zhuǎn)化為指派問題,給出了兩個計算復雜性為O(n3)的最優(yōu)算法。再次,第三章針對帶有配送時間、加工時間與位置相關和多個工期在單機問題下進行研究。假設工件配送時間與工件等待時間成比例,將帶有配送時間和加工時間依賴位置的單機排序問題與多個工期的單機排序問題結合成新的模型。首先分析了此類問題相關重要的性質(zhì);然后將這個問題轉(zhuǎn)化為一個指派問題,證明出這個問題可以在多項式時間內(nèi)可以解決的;最后,通過復雜性為O(n3)的算法,確定了最優(yōu)排序、最優(yōu)工期和極小化工件的提前、延誤和工期的總費用。然后,第四章研究了帶有分段線性遞減加工時間和拒絕工件的單機排序問題。在這一模型中,工件的實際加工時間是關于開始時間的分段線性遞減函數(shù),目標是使被接受工件最大完工時間與被拒絕工件總懲罰達到最優(yōu)的值,即最小值。該問題為NP難的問題。在對此問題的分析的基礎上,設計了一個全多項式近似策略。全多項式近似策略的計算復雜性為O(n4L4/ε3)。最后,對本文的主要結論進行歸納總結。
【關鍵詞】：加工時間可控 加工時間依賴位置 分段線性遞減 拒絕 全多項式近似策略
【學位授予單位】：沈陽師范大學
【學位級別】：碩士
【學位授予年份】：2016
【分類號】：F224;F273
【目錄】：

• 摘要3-4
• Abstract4-7
• 第一章 緒論7-10
• 一、排序問題簡介7
• 二、排序問題的三參數(shù)表示法7-8
• 三、相關問題研究現(xiàn)狀8-9
• 四、本文主要工作9-10
• 第二章 帶有學習效應的加工時間可控退化工件單機排序問題10-18
• 一、引言10
• 二、問題描述10-11
• 三、加工時間是線性資源函數(shù)11-14
• 四、加工時間是凸資源函數(shù)14-17
• 五、小結17-18
• 第三章 帶有配送時間和加工時間依賴位置的多個工期的單機排序問題18-25
• 一、引言18
• 二、問題描述18-19
• 三、主要結論19-24
• 四、小結24-25
• 第四章 帶有分段線性遞減加工時間和拒絕工件的單機排序問題25-34
• 一、引言25
• 二、問題描述25-26
• 三、全多項式近似策略26-33
• 四、小結33-34
• 結論34-35
• 參考文獻35-39
• 致謝39-40
• 個人簡歷40
• 在學期間的研究成果和發(fā)表的學術論文40

【參考文獻】

中國期刊全文數(shù)據(jù)庫 前5條

1 王吉波;牛玉萍;劉璐;郭倩;;同時具有學習和惡化效應的不同工期指派問題研究[J];沈陽師范大學學報(自然科學版);2014年03期

2 陳東;趙傳立;;帶有交貨期窗口和工件可拒絕的單機排序問題[J];重慶師范大學學報(自然科學版);2013年06期

3 張敏嬌;羅成新;;帶有退化工件和機器維修區(qū)間的單機排序問題[J];沈陽師范大學學報(自然科學版);2013年03期

4 范雁鵬;趙傳立;;帶有交貨期和加工時間可控的單機排序問題[J];重慶師范大學學報(自然科學版);2013年03期

5 劉澈;羅成新;;帶到達時間、不可用區(qū)間、拒絕工件的單機排序問題[J];重慶師范大學學報(自然科學版);2013年01期

  本文關鍵詞：幾類加工時間可變的單機排序問題，由筆耕文化傳播整理發(fā)布。

，

本文編號：332043