帶拒絕和釋放時(shí)間的單機(jī)批調(diào)度問(wèn)題.pdf

1、隨著科技的日益革新與制造業(yè)的發(fā)展，調(diào)度問(wèn)題的重要性得到了加強(qiáng)。有許多相關(guān)的研究者對(duì)于調(diào)度問(wèn)題進(jìn)行了大量的研究。大部分的研究都是在工件必須被加工這一前提條件下進(jìn)行的，但是有些情況下可以選擇拒絕加工一些工件，本文就是在這一前提條件下進(jìn)行研究的。
　　調(diào)度問(wèn)題的研究方向有很多。比如車間調(diào)度問(wèn)題，單機(jī)調(diào)度問(wèn)題，并行機(jī)調(diào)度問(wèn)題。本文主要研究單機(jī)調(diào)度問(wèn)題。研究的問(wèn)題具體如下:給定n個(gè)工件，其中每個(gè)工件的屬性包括:處理時(shí)間pj;到達(dá)時(shí)間rj（在

2、這個(gè)時(shí)刻之前，該工件不能被調(diào)度）;懲罰值ej（工件是可以被拒絕的，但是當(dāng)拒絕工件時(shí)，我們必須付出一定的代價(jià)，即為ej）。在加工期間，機(jī)器是不能暫停的，只能當(dāng)一批工件都被處理完時(shí)，才會(huì)停止。我們只考慮一個(gè)機(jī)器的情況，即單機(jī)調(diào)度。機(jī)器最多一次同時(shí)加工b個(gè)工件，這b個(gè)工件稱為一批，批里的工件的開始時(shí)間與結(jié)束時(shí)間一樣，批的處理時(shí)間即為批中工件處理時(shí)間最大的那個(gè)。我們的目標(biāo)是求最小的被接收工件的完成時(shí)間之和加被拒絕的工件的懲罰值之和。工件的完成時(shí)

3、間即為工件的開始被處理的時(shí)間或者說(shuō)工件所在批的開始時(shí)間加上批的處理時(shí)間。
　　我們對(duì)于目標(biāo)函數(shù)設(shè)計(jì)了一個(gè)動(dòng)態(tài)規(guī)劃算法，但是這個(gè)動(dòng)態(tài)規(guī)劃并不能求得最優(yōu)解，而是最優(yōu)解的一個(gè)近似解。因?yàn)?，在算法中，我們要?duì)給定的一部分初始條件做出改變，比如工件的到達(dá)時(shí)間與工件的處理時(shí)間，將其規(guī)整為某個(gè)數(shù)的指數(shù)倍。無(wú)規(guī)律初始條件改變?yōu)橛幸欢ㄒ?guī)律的初始條件，使得我們后續(xù)的分析變得相對(duì)簡(jiǎn)單一些。我們將工件分成了長(zhǎng)短兩類工件，并將它們分開處理。對(duì)于短工件我們?nèi)?/p>