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

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