寬容交貨加權(quán)超前延誤單機排序問題.pdf

1、本文考慮了下述寬容交貨加權(quán)超前延誤的單機排序問題：有n個工件需在同一臺機器上加工，各工件有一共同的寬容交貨期，寬容交貨期的大小已給定。工件在寬容交貨期內(nèi)完工不受罰，在寬容交貨期之前或之后完工將受到超前罰或延誤罰，懲罰系數(shù)依賴于工件。希望適當(dāng)排列這n個工件，使得目標(biāo)函數(shù)值即加權(quán)超前延誤罰總和最小。 這篇論文的結(jié)構(gòu)如下：第一章是引言和提出本文所研究的問題。第二章涉及本文的第一個問題，即在共同寬容交貨期位置需設(shè)定的條件下尋找一最優(yōu)寬容

2、交貨期及最優(yōu)序使得目標(biāo)函數(shù)值最小。證明了該問題是一般意義下NP-Completeness的，給出了一偽多項式時間的動態(tài)規(guī)劃方法并用實例加以說明。作者對一類特殊問題給出了一多項式時間的動態(tài)規(guī)劃方法。第三章涉及本文的第二個問題，即在共同寬容交貨期位置給定的條件下尋找一最優(yōu)序使得目標(biāo)函數(shù)值最小。問題分限制性和非限制性這兩種情況討論，找出了它們之間的臨界點。對限制性的問題，仍然證明了問題是一般意義下NP-Copleteness的，提出了一動態(tài)規(guī)