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

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

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

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

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


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

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



本文編號(hào)：3266312