幾類加工時(shí)間與環(huán)境有關(guān)的排序問題.pdf

1、排序問題是一類重要的組合最優(yōu)化問題。本文包括六個(gè)部分： 第一章序言，介紹排序問題的一些背景知識(shí)。 第二章討論流水作業(yè)加權(quán)總完工時(shí)間問題中加工時(shí)間受資源影響的資源分配問題：F2｜ chain，P2j=b2j-a2jμ2j,∑j-1nμ2j≤u｜∑j=1nwjCj給出了求問題最優(yōu)解的多項(xiàng)式時(shí)間算法。 第三章研究具有學(xué)習(xí)和惡化效應(yīng)的單機(jī)排序問題：工件的加工時(shí)間是工件開工時(shí)間和工件加工位置的函數(shù)：Pjr(t)=pf(t

2、)ra；分別對(duì)目標(biāo)函數(shù)是時(shí)間表長(zhǎng)、總完工時(shí)間、完工時(shí)間平方和的問題給出了多項(xiàng)式時(shí)間算法。 第四章研究一類具有學(xué)習(xí)效應(yīng)的單機(jī)成組排序問題：工件在組內(nèi)具有與位置有關(guān)的學(xué)習(xí)效應(yīng)；不同的工件組具有不同的學(xué)習(xí)因子；分別對(duì)目標(biāo)函數(shù)是時(shí)間表長(zhǎng)和總完工時(shí)間的情況進(jìn)行討論，證明它們多項(xiàng)式時(shí)間可解。 第五章討論單機(jī)上工件的加工時(shí)間同時(shí)依賴于開工時(shí)間和所分配的資源量的排序問題；極小化的目標(biāo)是時(shí)間表長(zhǎng)與資源費(fèi)用之和：1｜pf=fj(u)-djt