【摘要】：從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)度也稱為在線批處理調(diào)度，是現(xiàn)代調(diào)度模型領(lǐng)域中發(fā)展較為快速的一類調(diào)度模型。調(diào)度的隨機(jī)性是指工件在到達(dá)系統(tǒng)之前，工件的信息例如工件的到達(dá)時(shí)間、到達(dá)數(shù)目、工期、權(quán)重和后續(xù)是否還有新的工件到達(dá)等情況，事先是未知的。批處理調(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)度算法目標(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ī)，目標(biāo)函數(shù)為最小化總的權(quán)重完工時(shí)間和最小化總的權(quán)重延遲的隨機(jī)批處理調(diào)度模型，提出了競(jìng)爭(zhēng)比小于1+α的算法。其中α=β_m通過(guò)(1+β_m)~(m+1）=β_m+2求得，m為機(jī)器的數(shù)量。 (3)最后通過(guò)概率相關(guān)知識(shí)，研究了m=2的并行機(jī)且有兩個(gè)不同的作業(yè)族的模型，目標(biāo)函數(shù)為最小化最大完工時(shí)間，得到了競(jìng)爭(zhēng)比小于1+α的算法。 (4)利用泊松過(guò)程模擬工件的隨機(jī)到達(dá)，對(duì)具體的算法利用仿真數(shù)據(jù)進(jìn)行了驗(yàn)證。
文內(nèi)圖片：
圖片說(shuō)明： 這類模型研究的比較少。本文采用傳統(tǒng)的隨機(jī)調(diào)度的角度去建立模型進(jìn)行相關(guān)研究和討論。2.3.1 模型背景在物流系統(tǒng)中批處理調(diào)度經(jīng)常出現(xiàn)在，當(dāng)用戶的訂單為同一個(gè)地方的時(shí)候企業(yè)不可能對(duì)于收到的每個(gè)訂單立即進(jìn)行投遞，而是要等到相同目的地的用戶訂單達(dá)到一定條件的時(shí)候才考慮投遞。每次批處理的貨物太少企業(yè)的成本太高但是若投遞的時(shí)間過(guò)長(zhǎng)（即批處理的形成時(shí)間過(guò)長(zhǎng)），用戶體驗(yàn)就會(huì)不佳，同時(shí)利于企業(yè)的長(zhǎng)久發(fā)展。本文在批處理調(diào)度的時(shí)候從企業(yè)利潤(rùn)和用戶體驗(yàn)兩個(gè)角去考慮。文中的隨機(jī)性主要是指用戶的訂單的中貨物的數(shù)量，訂單到達(dá)時(shí)間，望的貨物到達(dá)時(shí)間（工期或者交貨期），訂單的權(quán)重等信息，，在用戶訂單到達(dá)之這些信息都未知。模型示意圖如下所示：
文內(nèi)圖片：
圖片說(shuō)明： 29圖 3-2 批處理能力無(wú)限算法流程圖3.3.3 算法仿真3.3.3.1 仿真數(shù)據(jù)對(duì)于隨機(jī)到達(dá)的工件我們使用泊松過(guò)程對(duì)它的每個(gè)工件序列的到達(dá)時(shí)間和到達(dá)工件個(gè)數(shù)進(jìn)行仿真，每個(gè)工件序列的權(quán)重使用一個(gè)隨機(jī)函數(shù)進(jìn)行仿真。仿真過(guò)程如下：假設(shè)工件的到達(dá)服從 =2 的泊松過(guò)程，并行機(jī)的批處理能力無(wú)限，即B ，機(jī)器的數(shù)量為 3 臺(tái)，每批工件的加工時(shí)間為 3.0 秒。由于仿真過(guò)程中涉及的參數(shù)較多，我們將它們的標(biāo)記在表 3-1 中進(jìn)行統(tǒng)一說(shuō)明，仿真數(shù)據(jù)結(jié)果在表 3-2 中。
【學(xué)位授予單位】：電子科技大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位授予年份】：2012
【分類號(hào)】：TH186

【參考文獻(xiàn)】

相關(guān)期刊論文 前8條

1 喬佩利;張宏芳;李小平;高祥;;FLOW SHOP調(diào)度問(wèn)題的啟發(fā)式算法[J];電機(jī)與控制學(xué)報(bào);2008年01期

2 張麗華;涂?jī)錾?;一個(gè)批處理機(jī)隨機(jī)調(diào)度模型[J];系統(tǒng)工程;2006年03期

3 鐘海嫣;霍佳震;;鋼管冷區(qū)生產(chǎn)調(diào)度的一種啟發(fā)式算法[J];工業(yè)工程與管理;2008年02期

4 余建軍;張定超;周銘新;;生產(chǎn)調(diào)度研究綜述[J];中國(guó)制造業(yè)信息化;2009年17期

5 張玉忠,苗翠霞;復(fù)制法及其在分批排序問(wèn)題中的應(yīng)用[J];曲阜師范大學(xué)學(xué)報(bào)(自然科學(xué)版);2004年02期

6 張玉忠;曹志剛;;并行分批排序問(wèn)題綜述[J];數(shù)學(xué)進(jìn)展;2008年04期

7 張召生,劉家壯;大規(guī)模集成電路預(yù)燒作業(yè)中分批排序問(wèn)題的數(shù)學(xué)模型[J];中國(guó)管理科學(xué);2003年04期

8 曹全軍;初紅艷;費(fèi)仁元;;啟發(fā)式算法和遺傳算法在生產(chǎn)調(diào)度中的應(yīng)用[J];中國(guó)機(jī)械工程;2006年S2期

相關(guān)博士學(xué)位論文 前1條

1 鄭睿;鋼鐵生產(chǎn)中的批處理機(jī)作業(yè)排序問(wèn)題算法研究[D];復(fù)旦大學(xué);2009年

相關(guān)碩士學(xué)位論文 前1條

1 李敏;資源約束下多項(xiàng)目調(diào)度問(wèn)題遺傳算法研究[D];浙江大學(xué);2008年

本文編號(hào)：2513360