跳到主要內容

臺灣博碩士論文加值系統

(100.28.132.102) 您好!臺灣時間:2024/06/25 15:37
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

我願授權國圖
: 
twitterline
研究生:楊雅茵
研究生(外文):Ya-Yin Yang
論文名稱:封閉式不可分馬可夫等候網路之流量下限及HW猜測之正確性
論文名稱(外文):Lower Bound of Network Throughput and Validity of HW Conjectures for Irreducible Closed Markovian Queueing Network
指導教授:黎廣福黎廣福引用關係
指導教授(外文):Kwang-Fu Li
學位類別:碩士
校院名稱:東海大學
系所名稱:數學系
學門:數學及統計學門
學類:數學學類
論文種類:學術論文
論文出版年:1999
畢業學年度:87
語文別:英文
論文頁數:31
中文關鍵詞:輸出量封閉式網路等候網路漸進損失漸進最佳有效性不可分系統
外文關鍵詞:ThroughputClosed networkQueueing networkAsymptotic lossAsymptotic optimalityEfficiencyIrreducible system
相關次數:
  • 被引用被引用:0
  • 點閱點閱:294
  • 評分評分:
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:0
考慮系統人數為N之封閉式不可分馬可夫等候網路。於1997年,就固定人數之網路系統,Jin、Ou和Kumar可藉由解出兩個線性規劃■和■的解,來獲得網路流量的上、下限。另外他們也藉由解出兩種類型的線性規劃(■、■、■和■)來獲得函數形式(N的函數)之流量上、下限。為了方便起見,假如T是一個線性規劃,VT則代表此線性規劃之最佳值。本文中我們證明了■ 。另一方面,若從函數形式的下限來看,當網路人數逐漸增加時,函數形式的下限也會跟著趨近■。因此當網路人數非常多時,藉由只解出■之最佳值,我們就可以獲得網路流量之下限。如果將這個特殊的線性規劃■擴充至一般的線性規劃,稱為■,我們猜測假如■是有界的,則會存在另一個線性規劃■,使得■。而這個線性規劃■可用簡單之方式,改變原來的線性規劃■來獲得。
1990年,Harrison和Wein(HW)對於兩個站台的Brownian系統提出了一個策略。我們證實該策略能用在所有兩個站台且封閉式不可分之馬可夫等候網路。HW猜測該策略是漸進最佳策略。HW也猜測該策略之漸進損失是有限的,並且提出了漸進損失的公式。1997年,Jin、Ou和Kumar只證明出HW的策略在兩個站台的系統是有效的,他們並猜測假如另外加上一特殊條件,對於任何兩個站台之平衡系統,HW的猜測是對的。但是到目前為止,關於HW策略之漸進最佳化還是沒有被證明出來。在本文中,我們可以導出有關漸進損失和這個附加條件之間的關係。對於一個特別設計的系統,我們可以證明所有非閒置的策略都是漸進最佳化。假如這樣的系統剛好又是平衡且迴歸線性的系統,那麼所有非閒置策略的漸進損失值是1。

For an irreducible closed Markovian network with N customers, Jin, Ou, and Kumar (1997) obtained pointwise bounds of the network throughput for any fixed integer N by solving linear programs ■ and ■. They also obtained other two linear programs ■ and ■ that can be used to develop the corresponding linear programs ■ and ■. Then the functional upper bound and lower bound of the network throughput can be derived from the objective values of the linear programs ■ and ■, and the optimal values of the linear programs ■ and ■ respectively. For convenience, if T is a given linear program, denote its optimum objective value by VT. We prove that ■. On the other hand, the limit of the functional lower bound as N approaches to infinity is also equal to ■. Thus the lower bound, in heavy traffic, can be obtained by solving ■ only. Extend this special linear program ■ to a general linear program, say ■, where N can be viewed as a variable. We conjecture that if ■ is bounded then there exists a limiting program ■ such that ■. This limiting program ■ can be easily obtained from modifying the original linear program ■.
Harrison and Wein (HW) (1990) proposed a buffer priority policy for two-station Brownian networks. We prove that it is indeed applicable to all two-station irreducible Markovian closed networks. HW conjectured that buffer priority policy is asymptotically optimal, and the asymptotic loss always has a finite value expression. Jin, Ou, and Kumar (1997) proved that the HW-policy is efficient for all two-station systems. They conjectured that under the ''additional condition'', all of the conjectures of HW are true for balanced two-station systems. However, a proof of its asymptotic optimality has so far been unavailable. We are able to develop a relation between asymptotic loss and the ''additional condition''. For a specially constructed system, we can also prove that all non-idling policies are asymptotically optimal. In this specially constructed system, if it is a balanced re-entrant line two-station system, the value of the asymptotic loss is 1.

1 Introduction 1
2 System Descriptions 3
3 Lower Bound of the Throughput with Infinite Population 6
4 Analyses of the HW Conjectures 18
5 Conclusions 30

1. Blackwell, D. Discrete dynamic programming. Ann. of Math.
Statist., 33, 719-726, 1962.
2. Dantzig, George B. and Mukund N. Thapa. Linear
Programming. Springer-verlag New York Berlin Heidelberg,
1997.
3. Harrison, J. M. and L. M. Wein. Scheduling networks of
queues : Heavy traffic analysis of a two-station closed
network. Operations Research, 41(4), 743-757, July-August
1993.
4. Harrison, J. M. and V. Nguyen. Some badly behaved closed
queueing networks. In Frank P. Kelly and Ruth Williams,
editors, Stochastic Networks, volume 71, pages 117-124.
Springer-verlag, New York, NY, 1995.
5. Jin, H., J. Ou, and P. R. Kumar. The throughput of
irreducible close Markovian queueing networks: Functional
bounds, asymptotic loss, efficiency, and the Harrison-Wein
conjectures. Mathematics of operations research, Vol. 22.
NO. 4, November 1997.
6. Kumar, S. and P. R. Kumar. Performance bounds for queueing
networks and scheduling policies. IEEE Transactions on
Automatic Control, AC-39 : 1600-1611, August 1994.
7. Lavenberg, Stephen, Editor. Computer Performance Modeling
Handbook, Academic Press, New York, 1983.
8. Lippman, S. Applying a new device in the optimization of
exponential queueing systems. Operations Reserch, 23:687-
713, 1975.
9. Murty, K. G. Linear Programming. John Wiley and Sons,
New York, NY, 1983.
10. Robinson, Stephen M. Analysis of sample-path optimization.
Mathematics of operations research, Vol. 21, No. 3, August
1996.
11. Walrand, J. Communication Networks-A first course, Aksen
Associates, Boston, 1991.
12. Wein, L. M. Scheduling semiconductor wafer fabrication.
IEEE Transactions on Semiconductor Manufacturing, 1(3),
115-130, August 1988.

連結至畢業學校之論文網頁點我開啟連結
註: 此連結為研究生畢業學校所提供,不一定有電子全文可供下載,若連結有誤,請點選上方之〝勘誤回報〞功能,我們會盡快修正,謝謝!
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top