與位置相關(guān)的單機(jī)排序問題研究.pdf

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

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

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