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

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

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