非標準隨機調度模型的最優動態策略

《非標準隨機調度模型的最優動態策略》是依託華東師範大學，由吳賢毅擔任項目負責人的面上項目。

基本介紹

• 中文名：非標準隨機調度模型的最優動態策略
• 項目類別：面上項目
• 項目負責人：吳賢毅
• 依託單位：華東師範大學

項目摘要

相對於確定性調度，隨機環境下的調度除了調度的參數如就緒時間、處理時間、到期時間等具有隨機的不確定性以外，另一個本質的特點是其調度計畫具有動態的特性（這是由於，調度者對於未實現的隨機變數的分布信息會在加工和調度過程中隨著隨機變數或其部分的實現而發生改變，信息的改變自然要求調整調度計畫來保證策略的最優性），然而，隨機調度的主流卻是在靜態策略類中尋找最優。另外，在標準的隨機調度問題中總是假定機器處於良好狀態，被加工工件或者產品不會腐壞，工件上累計的加工信息在機器中斷時要么完全損失、要么完全保留，各個隨機變數的分布已知，但是往往現實並非如此。因此本項目擬研究在機器帶隨機中斷、產品可能腐壞、中斷會造成工件加工信息的部分損失、或者關於隨機變數的信息可能不完全等非標準條件下隨機調度的動態最優策略及其相關的問題。

結題摘要

調度理論的基石是確定性調度理論，其一個顯著顯著特點是，到達時間、處理時間、到期時間等相關數據都是事先知道的。然而，在現實問題中，這些參數往往在實現了之後才會知道，對於這種問題的處理，發展了隨機調度(stochastic scheduling)的理論。在隨機調度中，根據技術條件的不同，策略有靜態(static or permutation policies) 與動態(dynamic, adaptive or progressive policies)之分，而後者又可以分為完全動態策略(unrestricted dynamic policies)和不完全動態策略 (restricted dynamic policies) 。隨機調度的重點應該是尋找最優動態策略。然而，文獻中隨機調度研究的絕大部分是將其轉化為確定性調度問題進行研究並得到最優靜態策略。標準的隨機調度問題總是假定機器一直處於良好狀態、無論工件在何時開始加工其加工時間的分布都與加工起始時間無關，各個參數隨機變數的機率分布已知等。但是現實問題經常不滿足這樣的標準條件。 本項目組及其合作者在國家自然科學基金委項目《非標準隨機調度模型的最優動態策略》資助下取得了如下的研究成果和進展： (a) 帶學習效果和隨機中斷的調度問題（time－varing隨機調度問題）；(b) 具有不確定性工作損失的隨機調度的一個統一方法；(c) 具有不可數狀態和時間可迴轉的廣義Bandit過程的最優決策方法；(d) 決策受限的最優停時問題。除了這些研究型的成果外，項目組成員在項目資助下還取得了如下的學術成果：（e）基本完成一部隨機調度領域的專著《optimal stochastic scheduling》，以及一篇關於隨機調度方面的綜述性論文。