機(jī)器帶中斷的若干延誤問(wèn)題研究.pdf

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

2、最小化；(2)兩臺(tái)平行機(jī)加工，n個(gè)工件，文章研究如何重新安排工件的加工順序，并將任意，n個(gè)交工期限怎樣分配給各個(gè)工件，使得目標(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)化、計(jì)算復(fù)雜性的基本理論，并對(duì)排序問(wèn)題的背景、研究方法等

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

4、將其推廣到m臺(tái)機(jī)的情形，當(dāng)交工期限為-C1，-G2，…，-Cn分配給先后加工的工件時(shí)，，考慮目標(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}，文章給出了一個(gè)最優(yōu)排序。對(duì)于上述給定的排序，當(dāng)交工期限d[1]，d[2]…，d[n]．按EDD序分配給先后加工的工件時(shí)，對(duì)上述目標(biāo)函數(shù)文章證明是最優(yōu)的。
　　 第四章是對(duì)全文的總結(jié)概括，并對(duì)以后