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

帶拒絕和釋放時間的單機(jī)批調(diào)度問題中期報告1.問題描述本問題是一個單機(jī)批處理調(diào)度問題，假設(shè)有$n$個作業(yè)需要在一臺機(jī)器上執(zhí)行。每個作業(yè)有一個到達(dá)時間$r_i$，一個執(zhí)行時間$p_i$，一個截止時間$d_i$，一個權(quán)重$w_i$，和一個釋放時間$s_i$。所有作業(yè)都必須在它們的截止時間之前完成。每個作業(yè)只能連續(xù)執(zhí)行一次，并且必須從其釋放時間之后開始執(zhí)行。作業(yè)的效用是在其截止時間之前完成所得的權(quán)重。該問題的目標(biāo)是在滿足上述約束條件的情況下，最大化完成的作業(yè)的總權(quán)重。2.算法設(shè)計該問題屬于NP問題，因此我們采用啟發(fā)式算法求解。我們選擇了GA(遺傳算法)。GA使用遺傳算子進(jìn)行進(jìn)化，包括交叉(crossover)、變異(mutation)和選擇(selection)。在每個迭代中，每個個體都按照其適應(yīng)度(fitness)值從概率上進(jìn)行選擇，然后使用遺傳算子進(jìn)行進(jìn)化。在本問題中，一個個體表示一個作業(yè)序列，其適應(yīng)度值為所有完成的作業(yè)的總權(quán)重。3.實(shí)驗(yàn)結(jié)果我們在C++環(huán)境下，使用GA求解了不同規(guī)模的實(shí)例。下表顯示了不同個數(shù)$n$的實(shí)例的最優(yōu)解和運(yùn)行時間。|$n$|最優(yōu)解|運(yùn)行時間(秒)||---|---|---||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ī)化的貪心算法，它在每次將一個作業(yè)加入序列時，都從剩余作業(yè)中隨機(jī)地選擇一個，并將其加入序列中。下表顯示了RandomSequencing對于不同規(guī)模的實(shí)例的平均最優(yōu)解和運(yùn)行時間。|$n$|平均最優(yōu)解|運(yùn)行時間(秒)||---|---|---||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)行時間也比RandomSequencing長，但在實(shí)際應(yīng)用中，GA的運(yùn)行時間仍可接受。4.總結(jié)本文介紹了一種