加工時(shí)間依賴(lài)開(kāi)工時(shí)間的排序問(wèn)題.pdf

1、排序問(wèn)題是一類(lèi)重要的組合最優(yōu)化問(wèn)題。本文討論了分段惡化排序問(wèn)題和帶資源約束的惡化排序問(wèn)題。 第二章討論分段惡化排序問(wèn)題。本章考慮了單機(jī)分段惡化排序問(wèn)題1|P<,j>=αorα+b<,j>|Σ w<,j>C<,j>，根據(jù)最優(yōu)解的性質(zhì)給出了遺傳算法和分支定界法。對(duì)于問(wèn)題的較小規(guī)模情形分支定界法能精確地求得最優(yōu)解；對(duì)于問(wèn)題的較大規(guī)模情形遺傳算法能很快地求得近似最優(yōu)解；算例及大量實(shí)驗(yàn)表明用遺傳算法來(lái)求問(wèn)題的近似解是成功的。 第三

2、章討論帶資源約束的單機(jī)惡化排序問(wèn)題。本章討論了兩類(lèi)問(wèn)題：一類(lèi)是資源量滿(mǎn)足一定要求，目標(biāo)函數(shù)為極小化最大完工時(shí)間的單機(jī)惡化排序問(wèn)題1 |p<,j>=b<,j>t<,j>-α<,j>u<,j>，∑u<,j>≤U|C<,max>和1 |P<,j>=S<,j>+bt<,j>-α<,j>u<,j>，∑u<,j>≤U|C<,max>，對(duì)于這兩個(gè)問(wèn)題分別給出了針對(duì)任意給定排列的最優(yōu)資源分配及在某些特殊情況下求得最優(yōu)解的多項(xiàng)式時(shí)間算法；另一類(lèi)是完工時(shí)間