單機(jī)雙目標(biāo)分批排序中的幾個(gè)問題.pdf

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

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