帶有拒絕工件的工期指派的排序問題.pdf

1、隨著現(xiàn)代工業(yè)的發(fā)展,排序模型被不斷突破。在一些排序模型中,如果所有工件都不被拒絕,當(dāng)一個(gè)工件的加工時(shí)間或加工費(fèi)用太大時(shí),將導(dǎo)致完工時(shí)間變大或費(fèi)用太大,因此需要考慮該工件是否被加工。若工件被拒絕則有一個(gè)懲罰費(fèi)用。每個(gè)工件需要確定一個(gè)工期。本文討論帶有拒絕工件的工期指派的排序問題。具體內(nèi)容概括如下:
　　1.工件的實(shí)際加工時(shí)間是其開始加工時(shí)間的線性增函數(shù)。討論的工期指派分為 CON(公共工期指派)和 SLK(相同松弛工期指派)兩種情況

2、。對(duì)于 CON工期指派問題,其目的是確定最優(yōu)公共工期及工件的加工順序,使工期、提前、延誤和拒絕的加權(quán)總費(fèi)用最小。我們將該問題歸結(jié)為一系列指派問題,給出了求解此問題的多項(xiàng)式時(shí)間的最優(yōu)算法;對(duì)于 SLK工期指派問題,目的是確定最優(yōu)的松弛量及工件的加工順序,使松弛、提前、延誤和拒絕的加權(quán)總費(fèi)用最小。將其歸結(jié)為一系列指派問題,從而得到了一個(gè)復(fù)雜性為O(n4)的算法來求解此問題。
　　2.分析了兩種資源分配函數(shù)和三種工期指派方法。資源分配分

3、為線性資源分配和凸資源分配。在線性資源分配條件下,討論了三種工期指派方法,工期指派分為 CON(公共工期指派),SLK(相同松弛工期指派)和 DIF(無限制工期指派),分別給出了多項(xiàng)式時(shí)間算法來確定最優(yōu)的加工順序,工期和資源分配量,使得工期、提前、延誤、資源分配和拒絕的加權(quán)總費(fèi)用最小;在凸資源分配條件下,也討論了CON,SLK和DIF三種工期,目的是確定最優(yōu)的加工順序,工期和資源分配量,使得工期、提前、延誤、資源分配和拒絕的加權(quán)總費(fèi)用最