機器帶中斷的若干延誤問題研究.pdf

1、本文研究機器帶中斷的排序問題。該問題可以描述為：兩臺平行機加工一批工件，加工過程中，由于某種原因，其中一臺機器發(fā)生故障可能在某一個時刻產(chǎn)生中斷，這使得安排在該機器上加工的工件無法及時加工，因而這些工件要么等待中斷結(jié)束后繼續(xù)在原機器上加工，要么轉(zhuǎn)移到另一臺正常運行的機器上加工，當(dāng)發(fā)生故障的機器恢復(fù)加工后，安排在正常運行的機器上加工的工件也可以轉(zhuǎn)移到恢復(fù)以后的機器上加工。(1)文章研究如何安排新的加工順序，使得目標(biāo)函數(shù)為誤工工件個數(shù)∑∪ij

2、最小化；(2)兩臺平行機加工，n個工件，文章研究如何重新安排工件的加工順序，并將任意，n個交工期限怎樣分配給各個工件，使得目標(biāo)函數(shù)P2|d[I]|Tmax，P2|d[I]|n∑I=1Ti，P2|d[I]|max｛Ei，Ti｝，P2|d[I]max{Ei，Ti}為最小，其中d[I]是分配給工件Ji的交工期限。
　　 全文共分為四章。
　　 第一章是緒論，主要介紹組合優(yōu)化、計算復(fù)雜性的基本理論，并對排序問題的背景、研究方法等

3、知識進(jìn)行闡述。
　　 第二章討論問題(1)。當(dāng)工件轉(zhuǎn)移時間T=0時，證明問題P2|D，T=0|∑∪'ij是多項式時間可解問題，本文給出了相應(yīng)的算法，并證明了算法的最優(yōu)性；當(dāng)轉(zhuǎn)移時間T>0時，問題P2|D，T≠0|∑∪'ij是NP難問題，對該問題文章提出了一個差界為1的多項式時間的近似算法，并給出了證明，算法的計算復(fù)雜度為O(nlogn)。
　　 第三章討論問題(2)。研究交工期限可分配的機器帶中斷的兩臺平行機排序問題，并

4、將其推廣到m臺機的情形，當(dāng)交工期限為-C1，-G2，…，-Cn分配給先后加工的工件時，，考慮目標(biāo)函數(shù)P2|d[I]|Tmax，P2|d[I]|n∑I=1Ti，P2|d[I]|max{Ei，Ti)，P2|d[I]|n∑I=1{Ei+Ti}，文章給出了一個最優(yōu)排序。對于上述給定的排序，當(dāng)交工期限d[1]，d[2]…，d[n]．按EDD序分配給先后加工的工件時，對上述目標(biāo)函數(shù)文章證明是最優(yōu)的。
　　 第四章是對全文的總結(jié)概括，并對以后