機(jī)器帶維護(hù)的準(zhǔn)時排序問題研究.pdf

1、本文主要研究了可變維護(hù)下具有公共時間窗的單機(jī)準(zhǔn)時排序問題,可變維護(hù)下異型機(jī)上的排序問題,維護(hù)受資源影響下的公共時間窗單機(jī)準(zhǔn)時排序問題和維護(hù)受資源影響下的惡化工件具有松弛期限的單機(jī)準(zhǔn)時排序問題.
　　全文共分為六章,主要如下:
　　1.在第一章,介紹了組合優(yōu)化問題,計算復(fù)雜性以及排序問題的基本概念和相關(guān)知識,并系統(tǒng)地總結(jié)了國內(nèi)外研究現(xiàn)狀.
　　2.在第二章,研究了可變維護(hù)下具有公共時間窗的單機(jī)準(zhǔn)時排序問題.所有工件都享有

2、一個共同的交付時間窗.此外一個強(qiáng)制性的維護(hù)必須在給定的截止時刻前開始實(shí)施且維護(hù)的持續(xù)時間取決于它的開始時刻.目標(biāo)是給出所有工件加工的最優(yōu)序列,確定維護(hù)的開始時間,時間窗的開始時間和時間窗的尺寸大小使得給定目標(biāo)函數(shù)值最小.當(dāng)所有工件的加工時間相同時,給出了該問題的最優(yōu)多項(xiàng)式時間算法.
　　3.在第三章,討論了可變維護(hù)下工件在異型機(jī)上的排序問題.每臺機(jī)器必須在給定的截止時間之前執(zhí)行一次維護(hù)活動且維護(hù)的持續(xù)時間取決于它的開始時間,該問題

3、的目標(biāo)是給出最優(yōu)工件排序并決定所有機(jī)器上維護(hù)的開始時間使總的完工時間之和最小,我們證明了該問題是強(qiáng)NP困難的.考慮到問題的復(fù)雜性,本文設(shè)計了該問題的啟發(fā)式算法.
　　4.在第四章,研究了維護(hù)受資源影響下的公共時間窗單機(jī)準(zhǔn)時排序問題.在該問題中維護(hù)的持續(xù)時間受到維護(hù)的開始時間和分配到維護(hù)上的資源量這兩個因素的共同影響.此外所有工件都分配一個共同的交付時間窗.本文給出了該問題最優(yōu)解的性質(zhì)并據(jù)此設(shè)計了最優(yōu)多項(xiàng)式時間算法.
　　5.