簡易檢索 / 詳目顯示

回結果列表
研究生： 林明憲
Lin, Ming-Hsien
論文名稱： 流量限制網路中求可靠度導向之多重型態資源分配之研究
Reliability-oriented Multi-resource Allocation in a Capacitated-flow Network
指導教授： 謝中奇
Hsieh, Chung-Chi
學位類別： 碩士
Master
系所名稱： 管理學院 - 工業管理科學系
Department of Industrial Management Science
論文出版年： 2003
畢業學年度： 91
語文別： 英文
論文頁數： 59
中文關鍵詞： 最小路徑 、多重型態資源分配 、網路可靠度
外文關鍵詞： Network reliability, Minimal path, Multi-resource allocation
相關次數： 點閱：97  下載：1 
分享至:
查詢本校圖書館目錄 查詢臺灣博碩士論文知識加值系統 勘誤回報

    • The objective of this study is to obtain the optimal multi-resource allocation in a multi-source multi-sink capacitated-flow network by maximizing the network reliability. The multi-source multi-sink capacitated-flow network contains a set of nodes, including source nodes and sink nodes, and a collection of arcs whose capacities have multiple operational states. Source nodes supply different resources that will be transmitted through the arcs to sink nodes where all resource demands must be satisfied. The network reliability is defined as the probability that the required resources can be transmitted from source nodes successfully. The evaluation methods of network reliability in capacitated-flow networks have been widely studied, but how to use a reliable means to allocate multiple resources at source nodes remains unanswered. A multi-resource allocation problem is formulated that aims to obtain the optimal multi-resource allocation policy. A procedure for solving the optimal multi-resource allocation that incorporates the principle of minimal path vectors is proposed. When demands at sink nodes change, the optimal multi-resource allocation will also be changed. Two algorithms are developed for updating, rather than re-computing, the optimal multi-resource allocation when demands encounter a positive or negative unit change.

    ACKNOWLEDGEMENTS : : : : : : : : : : : : : : : : : : : : : : : : : : : ii LIST OF TABLES : : : : : : : : : : : : : : : : : : : : : : : : : : : : v LIST OF FIGURES : : : : : : : : : : : : : : : : : : : : : : : : : : : vii LIST OF APPENDICES : : : : : : : : : : : : : : : : : : : : : : : : : viii CHAPTER I. INTRODUCTION . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.2 Objectives . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.3 Organization of This Thesis . . . . . . . . . . . . . . . . . . . . 3 II. LITERATURE REVIEW . . . . . . . . . . . . . . . . . . . . . . . . . 5 2.1 Single-Source Single-Sink Capacitated-Flow Network . . . . . . . . 5 2.2 Multi-Source Multi-Sink Capacitated-Flow Network . . . . . . . . . 9 2.3 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 III. MODEL OF A CAPACITATED-FLOW NETWORK . . . . . . . . . . . . . . . 11 3.1 Model of a Multi-source Multi-sink Capacitated-Flow Network . . . . 12 3.2 D-minimal Path Vectors . . . . . . . . . . . . . . . . . . . . . . 13 3.3 Network Reliability . . . . . . . . . . . . . . . . . . . . . . . . 15 3.4 Problem Formulation . . . . . . . . . . . . . . . . . . . . . . . . 16 IV. OPTIMAL RESOURCE ALLOCATION . . . . . . . . . . . . . . . . . . . . 17 4.1 Optimization . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 4.2 Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 4.2.1 Acyclic capacitated-flow network . . . . . . . . . . .. . . . . . 22 4.2.2 Cyclic capacitated-flow network . . . . . .. . . . . .. . . . . . 26 V. UPDATING OPTIMAL RESOURCE ALLOCATIONS FOR VARYING DEMAND . . . . . . 33 5.1 Updating Optimal Resource Allocation from D to D1 . . . . . . . . . 35 5.1.1 Comparison between Algorithm 1 and Algorithm 2 . . . . . . . . . 37 5.2 Updating Optimal Resource Allocation from D to D2 . . . . . . . . . 39 5.2.1 Comparison between Algorithm 1 and Algorithm 3 . . . . . . . . . 40 5.3 Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42 5.3.1 An Example from D to D1 . . . . . . . . . . . . . . . . . . . . . 42 5.3.2 An Example from D to D2 . . . . . ... . . . . . . . . . . . . . . 43 VI. CONCLUSION AND FUTURE DIRECTIONS . . . . . . . . .. . . . . . . . . 45 6.1 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45 6.2 Future Directions . . . . . . . . . . . . . . . . . . . . . . . . . 46 REFERENCES : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 47 APPENDICES : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 50 LIST OF TABLES Table 4.1 Probability mass functions of capacities of arcs in the capacitated-flow network in Figure 4.1 . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 4.2 Illustration of the sets of the D-MPs with respect to various multi- resource allocations . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 4.3 The corresponding D-MP sets and state vector sets for various multi- resource allocations . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 4.4 Network reliabilities for various multi-resource allocations with respect to Table 4.2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 4.5 Probability mass functions of capacities of arcs in the capacitated-flow network in Figure 4.2 . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 4.6 The corresponding D-MP sets for various multi-resource allocations . . . 30 4.7 The corresponding state vector sets for various multi-resource allocations 31 4.8 Network reliabilities for various multi-resource allocations with respect to Table A.2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 A.1 Illustration of the sets of the D-MP candidates with respect to various multi-resource allocations . . . . . . . . . . . . . . . . . . . . . . . . . 51 A.1 Illustration of the sets of the D-MP candidates with respect to various multi-resource allocations(Cont.) . . . . . . . . . . . . . . . . . . . . . 52 A.1 Illustration of the sets of the D-MP candidates with respect to various multi-resource allocations(Cont.) . . . . . . . . . . . . . . . . . . . . . 53 A.1 Illustration of the sets of the D-MP candidates with respect to various multi-resource allocations(Cont.) . . . . . . . . . . . . . . . . . . . . . 54 A.1 Illustration of the sets of the D-MP candidates with respect to various multi-resource allocations(Cont.) . . . . . . . . . . . . . . . . . . . . . 55 A.2 Illustration of the sets of the D-MPs with respect to various multi- resource allocations . . . . . . . . . . . . . . . . . . . . . . . . . . . 56 A.2 Illustration of the sets of the D-MPs with respect to various multi- resource allocations(Cont.) . . . . . . . . . . . . . . . . . . . . . . . . 57 A.2 Illustration of the sets of the D-MPs with respect to various multi- resource allocations(Cont.) . . . . . . . . . . . . . . . . . . . . . . . . 58 A.2 Illustration of the sets of the D-MPs with respect to various multi- resource allocations(Cont.) . . . . . . . . . . . . . . . . . . . . . . . . 59 LIST OF FIGURES Figure 4.1 A acyclic two-source two-sink capacitated-flow network . . . . . . . . . 23 4.2 A cyclic two-source two-sink capacitated-flow network . . . . . . . . . . 27 4.3 The path vector x1 illustration . . . . . . . . . . . . . . . . . . . . 29 4.4 The path vector x28 illustration . . . . . . . . . . . . . . . . . . . . 30 LIST OF APPENDICES Appendix A. Tables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51

    Abraham, J. A. An improved algorithm for network reliability. IEEE Transactions on Reliability, 29, 58-61, 1979.
    Ahuja, R. K., Magnanti, T. L. and Orlin, J. B. Prentice-hall. Network Flows-Theory, Algorithms, Applications, 1993.
    Aven, T. Reliability evaluation of multistate systems with multistate components.
    IEEE Transactions on Reliability, 34(5), 473-479, 1985.
    Barlow, R. E. and Wu, A. S. Coherent system with multi-state components. Mathematics of Operations Research, 3(4), 275-281, 1978.
    Bulter, D. A. Bounding the reliability of multistate systems. Operations Research, 30, 530-544, 1982.
    Doulliez, P. and Jamoulle, J. Transporation networks with random arc capacities.
    RAIRO, Recherche Operationnelle Operations Research, 3, 45-60, 1972.
    Griffith, W. S. Multistate reliability models. Journal of Applied Probability, 17, 735-744, 1980.
    Hsieh, C. C. and Huang, K. C. Optimal resource allocation on reliability maximization of a multi-source multi-sink flow network. Working Paper, 2001.
    Hudson, J. C. and Kapur, K. C. Reliability analysiis for multistate systems with
    multistate components. IIE Transactions, 15(2), 127-135, 1983.
    Hudson, J. C. and Kapur, K. C. Reliability bounds for multistate systems with multi-state components. Operations Research, 33(1), 153-160, 1985.
    Jane, C. C., Lin, J. and Yuan, J. Reliability evaluation of a limited-flow network in terms of minimal cutsets. IEEE Transactions on Reliability, 42(3), 354-361, 1993.
    Lee, S. H. Reliability evaluation of a flow network. IEEE Transactions on Reliability, 29(1), 24-26, 1980.
    Lin, J. S. Reliability evaluation of capacitated-flow networks with budget constraints. IIE Transactions, 30, 1175-1180, 1998.
    Lin, J. S., Jane, C. C. and Yuan, J. On reliability evaluation of a capacitated-flow network in terms of minimal pathsets. Networks, 25, 131-138, 1995.
    Lin, Y. K. Study on the multicommodity reliability of a capacitated-flow network.
    Computers and Mathematics with Application, 42, 255-264, 2001a.
    Lin, Y. K. A simple algorithm for reliability evaluation of a stochastic-flow network with node failure. Computers & Operations Research, 28, 1277-1285, 2001b.
    Lin, Y. K. Study on the system capacity for a multicommodity stochastic-flow network with node failure. Reliability Engineering and System Safety, 78, 57-62, 2002a.
    Lin, Y. K. Two-commodity reliability evaluation for a stochastic-flow network with node failure. Computers & Operations Research, 29, 1927-1939, 2002b.
    Lin, Y. K. Using minimal cuts to evaluate the system reliability of a stochastic-flow network with failures at nodes and arcs. Reliability Engineering and System Safety, 75, 41-46, 2002c.
    Locks, M. O. Recursive disjoint products, inclusion-exclusion and min-cut approximations. IEEE Transactions on Reliability, 29, 368-371, 1980.
    Singh, C. and Asgarpoor, S. Reliability evaluation of °ow networks using delta-star transformations. IEEE Transactions on Reliability, 35, 473-477, 1986.
    Xue, J. On multistate system analysis. IEEE Transactions on Reliability, 34(4), 329-337, 1985.
    Yeh, W. C. A simple algorithm to search for all d-MPs with unreliable nodes. Reliability Engineering and Systems Safety, 73, 49-54, 2001a.
    Yeh, W. C. A simple approach to search for all d-MCs of a limited-flow network.
    Reliability Engineering and Systems Safety, 71, 15-19, 2001b.
    Yeh, W. C. A simple method to verify all d-minimal path cardidates of a limited-flow network and its reliability. The International Journal of Advanced Manufacturing Technology, 20, 77-81, 2002.

    下載圖示 校內：立即公開
    校外：2003-07-04公開
    QR CODE