發(fā)布時間：2019-07-11 17:59

【摘要】：從20世紀(jì)初期開始，由于在制造業(yè)的大量應(yīng)用，調(diào)度問題日益受到人們的重視。調(diào)度問題研究的是將有限的資源在一定時間內(nèi)進(jìn)行合理的分配，以期做到盡可能高效率的完成不同的任務(wù)。它是一個決策過程，目標(biāo)是優(yōu)化一個或者多個目標(biāo)函數(shù)。隨機(jī)批處理調(diào)度也稱為在線批處理調(diào)度，是現(xiàn)代調(diào)度模型領(lǐng)域中發(fā)展較為快速的一類調(diào)度模型。調(diào)度的隨機(jī)性是指工件在到達(dá)系統(tǒng)之前，工件的信息例如工件的到達(dá)時間、到達(dá)數(shù)目、工期、權(quán)重和后續(xù)是否還有新的工件到達(dá)等情況，事先是未知的。批處理調(diào)度是相對于傳統(tǒng)的單個工件加工的調(diào)度問題而言，它是指把要加工的工件結(jié)成一批共同進(jìn)行加工處理。由于批處理調(diào)度有利于提高企業(yè)的生產(chǎn)效率和節(jié)約資源，因此它受到來自運籌學(xué)，管理學(xué)和工程學(xué)等領(lǐng)域?qū)W者的日益重視。 因為隨機(jī)批處理調(diào)度模型對于大多數(shù)機(jī)器環(huán)境和目標(biāo)函數(shù)來說是NP-難問題，所以基于近似思想產(chǎn)生的競爭比，用在線算法與離線算法的接近程度來衡量算法性能，成為研究隨機(jī)批處理調(diào)度算法的有力工具，并且得到大多數(shù)學(xué)者的認(rèn)可。它通常指隨機(jī)調(diào)度算法目標(biāo)函數(shù)值在最壞情況下，和離線算法接近程度，是二者比值的下確界。本論文利用基于啟發(fā)式算法的相關(guān)規(guī)則，去處理工件在到達(dá)系統(tǒng)之前所有信息未知的隨機(jī)批處理調(diào)度模型，最后通過競爭比和數(shù)據(jù)的仿真過程來說明算法是具有競爭性的。論文考慮的機(jī)器環(huán)境為并行機(jī)，工件隨機(jī)到達(dá)的隨機(jī)批處理調(diào)度模型。論文的具體工作如下所示： (1)介紹了不同的調(diào)度模型和競爭比的相關(guān)知識,批處理調(diào)度模型的主要研究方法和相關(guān)模型的研究現(xiàn)狀。 (2)針對并行機(jī)，目標(biāo)函數(shù)為最小化總的權(quán)重完工時間和最小化總的權(quán)重延遲的隨機(jī)批處理調(diào)度模型，提出了競爭比小于1+α的算法。其中α=β_m通過(1+β_m)~(m+1）=β_m+2求得，m為機(jī)器的數(shù)量。 (3)最后通過概率相關(guān)知識，研究了m=2的并行機(jī)且有兩個不同的作業(yè)族的模型，目標(biāo)函數(shù)為最小化最大完工時間，得到了競爭比小于1+α的算法。 (4)利用泊松過程模擬工件的隨機(jī)到達(dá)，對具體的算法利用仿真數(shù)據(jù)進(jìn)行了驗證。
文內(nèi)圖片：
圖片說明： 這類模型研究的比較少。本文采用傳統(tǒng)的隨機(jī)調(diào)度的角度去建立模型進(jìn)行相關(guān)研究和討論。2.3.1 模型背景在物流系統(tǒng)中批處理調(diào)度經(jīng)常出現(xiàn)在，當(dāng)用戶的訂單為同一個地方的時候企業(yè)不可能對于收到的每個訂單立即進(jìn)行投遞，而是要等到相同目的地的用戶訂單達(dá)到一定條件的時候才考慮投遞。每次批處理的貨物太少企業(yè)的成本太高但是若投遞的時間過長（即批處理的形成時間過長），用戶體驗就會不佳，同時利于企業(yè)的長久發(fā)展。本文在批處理調(diào)度的時候從企業(yè)利潤和用戶體驗兩個角去考慮。文中的隨機(jī)性主要是指用戶的訂單的中貨物的數(shù)量，訂單到達(dá)時間，望的貨物到達(dá)時間（工期或者交貨期），訂單的權(quán)重等信息，，在用戶訂單到達(dá)之這些信息都未知。模型示意圖如下所示：
文內(nèi)圖片：
圖片說明： 29圖 3-2 批處理能力無限算法流程圖3.3.3 算法仿真3.3.3.1 仿真數(shù)據(jù)對于隨機(jī)到達(dá)的工件我們使用泊松過程對它的每個工件序列的到達(dá)時間和到達(dá)工件個數(shù)進(jìn)行仿真，每個工件序列的權(quán)重使用一個隨機(jī)函數(shù)進(jìn)行仿真。仿真過程如下：假設(shè)工件的到達(dá)服從 =2 的泊松過程，并行機(jī)的批處理能力無限，即B ，機(jī)器的數(shù)量為 3 臺，每批工件的加工時間為 3.0 秒。由于仿真過程中涉及的參數(shù)較多，我們將它們的標(biāo)記在表 3-1 中進(jìn)行統(tǒng)一說明，仿真數(shù)據(jù)結(jié)果在表 3-2 中。
【學(xué)位授予單位】：電子科技大學(xué)
【學(xué)位級別】：碩士
【學(xué)位授予年份】：2012
【分類號】：TH186

【參考文獻(xiàn)】

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

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

2 張麗華;涂凍生;;一個批處理機(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];中國制造業(yè)信息化;2009年17期

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

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

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

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

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

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

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

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

本文編號：2513360