可控分批排序及供應鏈排序問題研究.pdf

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

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