排序問題是一類經典的組合最佳化問題，從上世紀50年代受到了許多行業的從業人員與理論研究者的密切關注。
基本介紹
中文摘要
本文主要研究排序問題在供應鏈管理中的套用。眾所周知，供應鏈是由多個環節構成的，因此我們不能孤立地研究排序問題，而要把排序問題與其它過程綜合考慮。全文共分四章。 第一章主要介紹了供應鏈與排序問題的一些知識和概念，並且總結了近些年來在綜合考慮排序與運輸的問題研究方面取得的一些成果。 第二章研究工件占用運輸工具空間不同的綜合考慮運輸和排序的問題。在這類問題中，工件在機器上完成加工後，需要由唯一的一輛運輸工具運送到相應的顧客處。運輸工具的空間是有限的，每個工件占用運輸工具的空間各不相同。目標函式是極小化最後一個到達顧客的工件的到達時間。當機器環境是單台機，所有工件的顧客相同時，我們設計了最壞情況界為3/2+ε(ε是任意正常數)的漸近最優算法。當機器環境是兩台平行機，所有工件的顧客相同時，我們給出了了最壞情況界為5/3的近似算法。 第三章討論了允許在兩個加工工廠之間運送原材料或成品的排序問題。每個工廠可以加工所有屬於本身的工件，也可以把一些工件運送到另一個工廠去加工。這樣的運送需要一定的時間。若某個工廠需要另一家工廠加工一些工件，根據工廠和工件的不同要求，有以下三種情形：(1)在工件加工之前，原材料不需要運送，工件完成加工後，需要被運送回有需求的工廠；(2)在工件加工之前，需要先運送原材料，工件完成加工後不需要被送回有需求的工廠； (3)在工件加工之前，需要先運送原材料，工件完成加工後，需要被運送回有需求的工廠。問題的目標函式都是極小化最後一個完工工件的完工時間。對這三個問題，我們分別設計了最壞情況界為4/3，4/3和3/2的線性時間近似算法，並且給出了動態規划算法。 第四章研究了帶承諾到貨時間的排序問題。在該問題中，企業根據顧客的訂單來加工產品，並把完成的訂單交由第三方物流公司運送給顧客。每個訂單包含不同的產品數量，而且必須在顧客要求的時間之前送達。訂單產生的運輸費用與其中的產品數量以及運輸需要的時間有關。我們的目標是安排一個加工訂單的排序並為每個訂單選擇運輸時間，使得所有訂單都能在承諾的最遲到貨時間之前到達其顧客處，並且產生的總運輸費用儘量地少。我們給出了此問題的最壞情況界為2的近似算法，並且證明了這個界是緊的。
