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

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

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

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