排序理論是組合優(yōu)化方向的一個活躍的分支,它起源于制造業(yè),后來被推廣到越來越多高新技術(shù)領(lǐng)域.隨著各個行業(yè)間的交叉與融合,許多生產(chǎn)和運輸問題都會作為排序問題里的新模型,被專家學(xué)者們關(guān)注與交流.本文中主要討論了工件具有入樹或鏈約束的幾類排序問題.在考慮工件之間帶有優(yōu)先約束關(guān)系這類排序問題時需要注意工件在有向無圈圖中的位置.本論文分四個章節(jié)對這類模型做了如下研究工作.第一章介紹了排序論的背景、相關(guān)基本知識以及符號.第二章研究了工件具有入樹約束和單位加工時間的兩臺同類機(jī)排序問題,工件具有不同的到達(dá)時間,目標(biāo)為極小化最大完工時間.對于該NP-難問題,首先我們設(shè)計了一個分支定界算法并證明了算法的正確性,然后通過一個具體的算例執(zhí)行了該分支定界算法的運算過程.第三章研究了工件具有鏈優(yōu)先約束的平行機(jī)排序問題,目標(biāo)為極小化加權(quán)總完工時間.對于該NP-難問題,首先我們針對兩臺平行機(jī)設(shè)計了偽多項式時間動態(tài)規(guī)劃算法,并證明了工件具有相同的加工時間的特殊情形是多項式可解的.然后將相應(yīng)的算法和結(jié)論推廣到了m臺平行機(jī)上以及同類機(jī)上.第四章考慮工件具有鏈優(yōu)先約束和成比例線性退化的單機(jī)排序問題,其中工件的加工時間是其開始時... 

【文章來源】：曲阜師范大學(xué)山東省

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

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

【文章目錄】：
摘要
Abstract
第一章 緒論
    1.1 具有優(yōu)先約束的排序問題
    1.2 退化效應(yīng)的排序問題
    1.3 P類問題和NP類問題
    1.4 算法
    1.5 三參數(shù)法
    1.6 符號說明
第二章 具有入樹約束的同類機(jī)排序問題的分支定界算法
    2.1 引言
    2.2 基礎(chǔ)知識介紹
    2.3 分支定界算法及算例
        2.3.1 分支定界算法
        2.3.2 算例
    2.4 小結(jié)
第三章 具有鏈約束的極小化加權(quán)總完工時間的平行機(jī)排序問題
    3.1 引言
    3.2 問題及符號
    3.3 問題P2|chains|∑wjCj
        3.3.1 一般情形
        3.3.2 多項式可解情形
    3.4 問題Pm|chains|∑w_jC_j
    3.5 問題Q2|chains|∑w_jC_j
    3.6 小結(jié)
第四章 工件具有鏈約束及成比例線性退化的單機(jī)排序問題
    4.1 引言
    4.2 問題及符號
    4.3 問題1|strong chains,pij=b_(ij)(A+Bt)|∑w_(ij)C_(ij)
    4.4 問題1|weak chains,pij=b_(ij)(A+Bt)|∑w_(ij)C_(ij)
    4.5 小結(jié)
參考文獻(xiàn)
在校期間發(fā)表的學(xué)術(shù)論文、專利及藝術(shù)作品等
致謝


【參考文獻(xiàn)】：
期刊論文
[1]關(guān)于問題Pm|chains|Cmax的PTAS算法[J]. 張傳林,曹麗霞,鄭培華.  北方工業(yè)大學(xué)學(xué)報. 2008(03)
[2]單位加工時間有鏈約束的恒速機(jī)排序問題[J]. 左蘭.  紹興文理學(xué)院學(xué)報(自然科學(xué)版). 2008(02)
[3]含作業(yè)到達(dá)時間的同類機(jī)調(diào)度問題啟發(fā)式算法[J]. 李凱,靳鵬.  系統(tǒng)工程理論與實踐. 2007(10)
[4]一類處理機(jī)具有準(zhǔn)備時間的恒速機(jī)排序問題[J]. 石銳,趙傳立.  沈陽師范大學(xué)學(xué)報(自然科學(xué)版). 2007(01)
[5]關(guān)于問題Pm|intree;pj=1;rj|Cmax的分支定界算法[J]. 張玉忠,張咸昭,孫志慧.  運籌學(xué)學(xué)報. 2006(02)
[6]帶機(jī)器準(zhǔn)備時間的同類機(jī)在線與半在線排序問題[J]. 丁際環(huán),曲桂東,張偉,岳麗,張玉忠.  曲阜師范大學(xué)學(xué)報(自然科學(xué)版). 2003(03)
[7]任務(wù)具有鏈約束的平行機(jī)調(diào)度問題[J]. 趙傳立,張慶靈,唐恒永.  控制與決策. 2001(S1)
[8]處理機(jī)具有準(zhǔn)備時間的恒速機(jī)排序問題[J]. 趙傳立,唐恒永,張慶靈.  系統(tǒng)工程學(xué)報. 2001(02)
[9]處理機(jī)具有準(zhǔn)備時間的Qm,aj｜pj=1｜Cmax排序問題[J]. 趙玉芳,趙傳立,唐恒永.  運籌與管理. 1999(03)

碩士論文
[1]帶有鏈優(yōu)先約束的兩類排序問題[D]. 鄒娟.曲阜師范大學(xué) 2004



本文編號：3266312