單機雙目標分批排序中的幾個問題.pdf

1、排序論又稱時間表理論，已經(jīng)發(fā)展成為運籌學的一個重要分支，作為一門應(yīng)用科學，它有深刻的實際背景和廣闊的應(yīng)用前景.分批排序問題、多目標排序問題是近年來新興起的兩類現(xiàn)代排序模型，因其顯著的現(xiàn)實意義，更具研究價值.本文將以上兩種現(xiàn)代排序模型相結(jié)合，討論了幾類特殊的單機雙目標分批排序問題.論文主要結(jié)構(gòu)安排如下： 第一章(緒論)首先介紹了排序問題的應(yīng)用背景及問題描述，然后給出了必要的預(yù)備知識，最后概述了本文的主要研究結(jié)果. 第二章主

2、要研究了兩類批容量無限的單機雙目標平行分批排序問題模型t約束模型與線性加權(quán)模型.目標函數(shù)主要涉及一些常見目標函數(shù)，如Cmax，Lmax，∑wjCj等的組合，通過動態(tài)規(guī)劃就相應(yīng)問題分別給出了多項式時間算法，并作了時間復(fù)雜性分析.最后我們證明在本文約束模型解決前提之下，問題對應(yīng)的主次指標模型也可相應(yīng)解決. 第三章主要研究了平行分批排序問題(p-batch)中一類主指標為∑wjCj,次指標為Cmax的主次指標排序問題.首先討論了單機上