可控分批排序及供應(yīng)鏈排序問題研究.pdf

1、排序問題是一類重要的組合優(yōu)化問題，有著深刻的實(shí)際背景和廣闊的應(yīng)用前景，它廣泛應(yīng)用于管理科學(xué)、計(jì)算機(jī)科學(xué)、工農(nóng)業(yè)生產(chǎn)、交通運(yùn)輸?shù)仍S多領(lǐng)域，已經(jīng)取得了許多有意義的成果.分批排序和可控排序是兩類很重要的現(xiàn)代排序模型，本文中把這兩類排序模型相結(jié)合，討論加工時(shí)間離散可控的單機(jī)分批排序問題.另外，對(duì)于近年來出現(xiàn)的將供應(yīng)鏈管理和排序理論相結(jié)合的供應(yīng)鏈排序問題，對(duì)于其中一個(gè)模型，考慮了平行機(jī)分批配送問題. 論文共分三章： 第一章首先介紹

2、了排序問題的應(yīng)用背景及問題描述，然后給出了必要的預(yù)備知識(shí)，最后概述了本文研究的主要問題及研究結(jié)果. 第二章主要討論加工時(shí)間離散可控的單機(jī)分批排序問題：分別考慮機(jī)器容量有限及無限兩種情況下，分別使最大完工時(shí)間和總完工時(shí)間加上加工時(shí)間可控所需費(fèi)用的總和為最小作為優(yōu)化的目標(biāo)，討論了這四個(gè)問題的最優(yōu)解的性質(zhì)，并在此基礎(chǔ)上提出了相應(yīng)的多項(xiàng)式時(shí)間最優(yōu)算法. 第三章主要討論平行機(jī)分批配送問題中的一個(gè)模型，首先指出該問題是強(qiáng)NP-har