隨機需求約束下的批處理資源調度模型與算法.pdf

1、從20世紀初期開始，由于在制造業(yè)的大量應用，調度問題日益受到人們的重視。調度問題研究的是將有限的資源在一定時間內進行合理的分配，以期做到盡可能高效率的完成不同的任務。它是一個決策過程，目標是優(yōu)化一個或者多個目標函數(shù)。隨機批處理調度也稱為在線批處理調度，是現(xiàn)代調度模型領域中發(fā)展較為快速的一類調度模型。調度的隨機性是指工件在到達系統(tǒng)之前，工件的信息例如工件的到達時間、到達數(shù)目、工期、權重和后續(xù)是否還有新的工件到達等情況，事先是未知的。批處理

2、調度是相對于傳統(tǒng)的單個工件加工的調度問題而言，它是指把要加工的工件結成一批共同進行加工處理。由于批處理調度有利于提高企業(yè)的生產效率和節(jié)約資源，因此它受到來自運籌學，管理學和工程學等領域學者的日益重視。
　　因為隨機批處理調度模型對于大多數(shù)機器環(huán)境和目標函數(shù)來說是NP-難問題，所以基于近似思想產生的競爭比，用在線算法與離線算法的接近程度來衡量算法性能，成為研究隨機批處理調度算法的有力工具，并且得到大多數(shù)學者的認可。它通常指隨機調度算

3、法目標函數(shù)值在最壞情況下，和離線算法接近程度，是二者比值的下確界。本論文利用基于啟發(fā)式算法的相關規(guī)則，去處理工件在到達系統(tǒng)之前所有信息未知的隨機批處理調度模型，最后通過競爭比和數(shù)據(jù)的仿真過程來說明算法是具有競爭性的。論文考慮的機器環(huán)境為并行機，工件隨機到達的隨機批處理調度模型。論文的具體工作如下所示：
　　(1)介紹了不同的調度模型和競爭比的相關知識,批處理調度模型的主要研究方法和相關模型的研究現(xiàn)狀。
　　(2)針對并行機，