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

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

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

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