帶拒絕和釋放時間的單機批調(diào)度問題.pdf

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

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

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