在帶中斷的單機(jī)上的隨機(jī)調(diào)度

《在帶中斷的單機(jī)上的隨機(jī)調(diào)度》由會員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在學(xué)術(shù)論文-天天文庫。

1、王秀軍碩士學(xué)位論文答辯委員會成員名單姓名職稱單位備注韓天雄教授華東師范大學(xué)主席汪榮明教授華東師范大學(xué)吳述金副教授華東師范大學(xué)第一章緒論弗一旱三百比§1．1調(diào)度方面的背景介紹1．1．1與本文有關(guān)的調(diào)度問題介紹本文調(diào)度問題研究：有一批無先后處理順序的工作任務(wù)(jobs)需要在一個單處理器(single—machine)中處理，不妨有禮個工作任務(wù)，每個任務(wù)需要的初始處理時間為五，i=1，2，3，?，n(其中工作任務(wù)的初始處理時間X是指每個工作任務(wù)第一個在單處理器中處理所需的時間)，這扎個任務(wù)沒有先后順序，隨時可以接受處理器的處理，但在每個時點(diǎn)該處理器只能處理一個工作任務(wù)。將n個工作任

2、務(wù)用1，2，3，4，?，n標(biāo)記，那么調(diào)度問題主要關(guān)心的是怎樣安排工作任務(wù)的處理順序，使的整個任務(wù)的完成時間最短或最優(yōu)其他的目標(biāo)函數(shù)，可以數(shù)學(xué)描述為怎樣安排策略7r={il，i2，ia，?，如)，其中7r為{1，2，3，4，?，禮)的一個排列，7r(后)=ik。1．1．2熱點(diǎn)調(diào)度問題介紹在主流調(diào)度理論研究中，通常假定每個工作任務(wù)需要處理時間是time-invariant，即這個工作任務(wù)需要的處理時間與時間t無關(guān)，具體可以參考文獻(xiàn)f19】。但是在許多實(shí)際情況中，工作任務(wù)的所需處理時間是time-varying，即與時間t有關(guān)，可以假設(shè)在t時刻，它的處理時間是時間t的函數(shù)，記為x(t

3、)。雖然與時間無關(guān)的工作在某些情況中可能反映或近似反映現(xiàn)實(shí)生活(其實(shí)很多時候這樣假設(shè)只是為了計(jì)算的方便)，但它的結(jié)果精度遠(yuǎn)遠(yuǎn)不夠，所以在對精度要求更高的今天，很難廣泛的運(yùn)用。但與時間有關(guān)的隨機(jī)調(diào)度在現(xiàn)實(shí)中有廣泛應(yīng)用，主要體現(xiàn)在消防、金融管理、食品處理和儲存、資源分配、軍隊(duì)目標(biāo)搜索、國家防衛(wèi)、計(jì)算機(jī)科學(xué)、人工智能和冶金等等領(lǐng)域，所以本文將研究工作任務(wù)需要處理時間與時間亡有關(guān)的隨機(jī)調(diào)度，顯得很有意義和必要。在現(xiàn)實(shí)例子中任何推遲工作任務(wù)的處理都將影響整個任務(wù)的完工狀況(從時間、成本或生命財產(chǎn)等等方面)。在最近的二十多年來，往隨機(jī)調(diào)度模型中引入工作任務(wù)與時間t有關(guān)，越來越受到關(guān)注并且在

4、這個領(lǐng)域也有了很多研究成果。在本文的研究模型中，工作任務(wù)在時刻t需要的處理時間假設(shè)與時間t是線性的(關(guān)于時間t是遞增的或者遞減的，因?yàn)榈却龑⒃黾踊蛘邷p少工作需要處第一章緒論華東師范大學(xué)碩士論文2理的時間或成本)，更多的細(xì)節(jié)討論和有關(guān)隨機(jī)調(diào)度的研究請參考Cheng，DingandLin(2004)$1Womer(1999)這兩篇文章。另外為了處理的方便，經(jīng)典的調(diào)度模型常常假設(shè)處理器是不間斷的處理完n個工作任務(wù)，然而在現(xiàn)實(shí)中我們經(jīng)常發(fā)現(xiàn)在某個時刻處理器可能會出現(xiàn)故障(machine-breakdown)，這樣會導(dǎo)致處理器處理工作的間斷；例如在計(jì)算機(jī)、制造業(yè)、工程提煉中，處理器發(fā)生中

5、斷是很正常的。最近二十年研究中考慮機(jī)器中斷的隨機(jī)調(diào)度模型主要分兩個方向：(1)第一個是preemptive-resumemodel，即當(dāng)機(jī)器中斷恢復(fù)以后，整個先前處理好的任務(wù)已經(jīng)被保存，機(jī)器繼續(xù)從中斷工作時開始處理。有關(guān)研究請參考文獻(xiàn)[6]年fl[23】，Glazebrooke(1984，1987)，Li，BraunaandZhao(1998)，Mittenthaland兄n夕^o秒nc^07．z(1993)，PinedoandRammouz(1988)，以及Qt，YinandBirge(2000a，2000b)等等文章：(2)第二個是preemptive-repeatmode

6、l，即當(dāng)機(jī)器中斷恢復(fù)以后，機(jī)器對剛剛處理過的工作沒有保存，需要重新開始處理工作；我們用計(jì)算機(jī)下載網(wǎng)絡(luò)資源為例，當(dāng)網(wǎng)絡(luò)資源下載一半時，突然計(jì)算機(jī)死機(jī)了(即計(jì)算機(jī)處理器中斷)，您需要重新啟動計(jì)算機(jī)進(jìn)行資源下載，如果繼續(xù)前面的一半進(jìn)行下載，那么它就符合第一個方向(preemptive-resumemodel)；如果我們需要重新從零開始下載，那么它就是第二個方向(preemptive-repeatmodel)：有關(guān)方向二的隨機(jī)調(diào)度文章請參考Cai，ZhouandSun(2003，2004)，Cai，WuandZhou(2005，2009)，F(xiàn)rostig(1991)，Glazebroo

7、ke(1991)以及Cheng，T．C．E．，Ding，Q．a(chǎn)ndLin，B．M．T．等等。上面兩個方向都是處理器中斷(machine-breakdown)影響工作任務(wù)的處理時間，但當(dāng)同時考慮處理器中斷和工作任務(wù)的需要處理時間與時間t有關(guān)的雙重影響時，可能會導(dǎo)致很難找到最優(yōu)的調(diào)度策略。下面舉幾個在現(xiàn)實(shí)生活中受處理器中斷和工作任務(wù)與時間有關(guān)的雙重影響的例子；在鋼鐵廠，煉鋼機(jī)器可能隨時出現(xiàn)故障，在排除故障期間(處理器中斷)，鑄鐵塊的溫度會下降(-v作任務(wù)需要處理時間與時間有關(guān))，它需要機(jī)器修理好