與位置相關的單機排序問題研究.pdf

1、排序問題是組合優(yōu)化問題的一類重要分支，這一問題最早起源于機器制造業(yè)，現(xiàn)在已普遍應用于運籌學，經(jīng)濟管理科學、系統(tǒng)控制和計算機科學等多個學科。在經(jīng)典排序問題當中，一般假設工件的加工時間為常數(shù)，但在很多實際問題中，工件的實際加工時間可能與其所在位置，開工時間，所分配的資源等多種因素有著各種聯(lián)系，使得工件的加工時間不再是固定常數(shù)。本文主要研究工件的實際加工時間與位置相關的單機排序問題，主要結果如下：
　　1、帶有線性位置惡化及維修區(qū)間的單

2、機排序問題
　　(1)工件的實際加工時間與其所在的位置線性相關，且位置具有惡化效應，維修區(qū)間長度與其前一組工件的完工時間和成線性關系，目標函數(shù)是最小化最大完工時間和最小化總完工時間問題，在最大完工時間問題模型中，證明了工件序列滿足組平衡原則，并給出了相關結論與算法。
　　(2)對于總完工時間問題，可以轉(zhuǎn)化為線性指派問題進行求解，證明該問題也是多項式時間可解的，其算法的時間復雜度為O(nfcl0+3)。
　　2、帶有位置

3、效應和到達時間的單機組排序問題
　　(1)在工件獨立，組相關的情形下，工件具有到達時間，且其實際加工時間是工件加工位置的函數(shù)，組準備時間與前一組完工時間線性相關。在開始加工之前，工件的分組已經(jīng)確定，考慮工件的最大完工時間問題，確定了組內(nèi)工件和組與組之間的最優(yōu)排列順序，并給出相應定理及算法。
　　(2)在組準備時間為常數(shù)的特殊情況下證明工件的最大完工時間問題是多項式可解的，并給出相關結論。
　　3、具有對數(shù)學習效應且與已