幾類交貨期指派的排序問題.pdf

1、作為一門應用科學，排序問題有著廣闊的應用前景，它主要應用于機械制造領域，后來被廣泛應用于工程技術，交通運輸，計算機科學等眾多行業(yè)。隨著工業(yè)的快速發(fā)展，排序問題的模型不斷突破。在一些排序模型中，工件在規(guī)定的交貨期前完工需要儲存，產(chǎn)生一定費用；在交貨期后完工要引發(fā)消費懲罰。在排序問題中交貨期指派問題是重要因素之一。本文將討論三種不同的交貨期指派問題。具體內容概括如下：
　　1.討論帶有公共交貨期的排序問題。工件的加工時間是與工件在排序

2、中的位置、資源分配、維修活動的位置和工件的開始加工時間有關的函數(shù)。目標是確定工件的最優(yōu)排序、最優(yōu)的資源分配、最優(yōu)的維修位置和最優(yōu)的交貨期指派，使得總目標函數(shù)值最小。將該問題歸結為指派問題，得到了一個最優(yōu)算法，其時間復雜性為O?n4?。
　　2.討論帶有多個交貨期窗口的單機排序問題，且工件的加工時間是退化的。研究了兩種目標函數(shù)，第一種是帶有提前、延誤、最大完工時間及交貨期的開始位置與大小的總費用；第二種是帶有提前、延誤、所有工件完工