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

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

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

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