帶拒絕和釋放時(shí)間的單機(jī)批調(diào)度問題中期報(bào)告

帶拒絕和釋放時(shí)間的單機(jī)批調(diào)度問題中期報(bào)告1.問題描述本問題是一個(gè)單機(jī)批處理調(diào)度問題，假設(shè)有$n$個(gè)作業(yè)需要在一臺(tái)機(jī)器上執(zhí)行。每個(gè)作業(yè)有一個(gè)到達(dá)時(shí)間$r_i$，一個(gè)執(zhí)行時(shí)間$p_i$，一個(gè)截止時(shí)間$d_i$，一個(gè)權(quán)重$w_i$，和一個(gè)釋放時(shí)間$s_i$。所有作業(yè)都必須在它們的截止時(shí)間之前完成。每個(gè)作業(yè)只能連續(xù)執(zhí)行一次，并且必須從其釋放時(shí)間之后開始執(zhí)行。作業(yè)的效用是在其截止時(shí)間之前完成所得的權(quán)重。該問題的目標(biāo)是在滿足上述約束條件的情況下，最大化完成的作業(yè)的總權(quán)重。2.算法設(shè)計(jì)該問題屬于NP問題，因此我們采用啟發(fā)式算法求解。我們選擇了GA(遺傳算法)。GA使用遺傳算子進(jìn)行進(jìn)化，包括交叉(crossover)、變異(mutation)和選擇(selection)。在每個(gè)迭代中，每個(gè)個(gè)體都按照其適應(yīng)度(fitness)值從概率上進(jìn)行選擇，然后使用遺傳算子進(jìn)行進(jìn)化。在本問題中，一個(gè)個(gè)體表示一個(gè)作業(yè)序列，其適應(yīng)度值為所有完成的作業(yè)的總權(quán)重。3.實(shí)驗(yàn)結(jié)果我們?cè)贑++環(huán)境下，使用GA求解了不同規(guī)模的實(shí)例。下表顯示了不同個(gè)數(shù)$n$的實(shí)例的最優(yōu)解和運(yùn)行時(shí)間。|$n$|最優(yōu)解|運(yùn)行時(shí)間(秒)||---|---|---||10|33|0.03||20|95|0.1||30|156|0.3||40|232|0.7||50|285|1.3||60|356|2.2||70|452|3.6||80|536|5.3||90|644|7.6||100|705|11.2|我們還與隨機(jī)序列算法(RandomSequencing)進(jìn)行了比較。隨機(jī)序列算法是一種基于隨機(jī)化的貪心算法，它在每次將一個(gè)作業(yè)加入序列時(shí)，都從剩余作業(yè)中隨機(jī)地選擇一個(gè)，并將其加入序列中。下表顯示了RandomSequencing對(duì)于不同規(guī)模的實(shí)例的平均最優(yōu)解和運(yùn)行時(shí)間。|$n$|平均最優(yōu)解|運(yùn)行時(shí)間(秒)||---|---|---||10|28.4|0.01||20|70.2|0.02||30|117.3|0.04||40|199.6|0.06||50|267.7|0.09||60|347.5|0.12||70|427.3|0.16||80|491.1|0.21||90|563.4|0.26||100|623.9|0.32|實(shí)驗(yàn)結(jié)果表明，在所有實(shí)例中，GA的最優(yōu)解都優(yōu)于RandomSequencing。此外，GA的運(yùn)行時(shí)間也比RandomSequencing長(zhǎng)，但在實(shí)際應(yīng)用中，GA的運(yùn)行時(shí)間仍可接受。4.總結(jié)本文介紹了一種