發(fā)布時間：2021-12-31 08:31

　　為有效的生產(chǎn),排序模型和算法被廣泛地應(yīng)用于制造領(lǐng)域。然而,資源的短缺導(dǎo)致生產(chǎn)效率和生產(chǎn)收益越來越低。本文研究兩類資源受限的生產(chǎn)排序問題:問題一,考慮具有額外資源的平行機(jī)排序問題,即每個工件的加工不僅需要機(jī)器而且還需要一些額外的資源才能完成,且需要相同資源的兩個工件不能在同一時刻加工,目標(biāo)為極小化最大完工時間。問題二,我們考慮具有柔性維護(hù)周期的單機(jī)排序,此情形下,所有的工件必須在周期的時間窗口加工,目標(biāo)為極小化誤工工件數(shù)。全文共分為四章。第一章主要介紹一些排序問題和計算復(fù)雜性理論的基礎(chǔ)知識。特別地,我們對資源受限排序問題進(jìn)行了簡單介紹。第二章討論問題一。首先,根據(jù)決策變量的不同選擇,給出了所考慮問題的四種不同的數(shù)學(xué)規(guī)劃模型。其次,基于LPT算法設(shè)計了求解該問題的近似算法ILPT,并證明了該算法的最壞情況界為2-2m+1。最后,我們注意到文獻(xiàn)中一個基于LPT的算法LLPT和ILPT算法在理論上有相同的界,并且我們通過數(shù)值實驗評估了該算法的性能。第三章研究具有柔性維護(hù)周期的單機(jī)排序問題。首先證明了極小化誤工工件數(shù)問題是不可近似的,即不存在具有常數(shù)界的近似算法。接著給出了求解一般問題的偽多項式... 

【文章來源】：杭州電子科技大學(xué)浙江省

【文章頁數(shù)】：42 頁

【學(xué)位級別】：碩士

【文章目錄】：
摘要
ABSTRACT
1 緒論
    1.1 排序問題
    1.2 算法與復(fù)雜性
    1.3 經(jīng)典排序問題
    1.4 資源受限的排序問題
    1.5 論文概述
2 帶有額外資源的平行機(jī)排序問題
    2.1 問題描述
    2.2 研究現(xiàn)狀
    2.3 數(shù)學(xué)規(guī)劃模型
    2.4 ILPT算法及其近似比分析
    2.5 LLPT算法與數(shù)值實驗
    2.6 本章小結(jié)
3 具有柔性維護(hù)周期的單機(jī)排序問題
    3.1 問題描述及符號說明
    3.2 不可近似性證明
    3.3 動態(tài)規(guī)劃算法與可解情形
    3.4 本章小結(jié)
4 結(jié)論
致謝
參考文獻(xiàn)
附錄


【參考文獻(xiàn)】：
期刊論文
[1]2003年到2005年排序（調(diào)度）學(xué)科在中國的發(fā)展（I）[J]. 唐國春.  上海第二工業(yè)大學(xué)學(xué)報. 2006(03)
[2]排序問題的簡短歷史和國外發(fā)展動態(tài)[J]. 孫世杰.  運籌學(xué)雜志. 1991(01)
[3]排序問題的定義、分類和在國內(nèi)的某些研究進(jìn)展[J]. 唐國春.  運籌學(xué)雜志. 1990(02)

博士論文
[1]面向訂單生產(chǎn)的供應(yīng)鏈排序問題研究[D]. 王磊.暨南大學(xué) 2011

碩士論文
[1]兩種排序問題的近似算法[D]. 谷會昆.浙江大學(xué) 2004



本文編號：3559943