由於分散式系統具有高速和可靠的優點，因此分散式系統已普遍被運用於日常生活中，例如電力控制系統、自動提款機系統。在分散式系統環境下可將軟體執行視為一個任務，而軟體是由數個模組所構成，當執行任務時會將模組分配到系統中的各個運算節點上執行，因此可將分散式系統的系統可靠度定義為系統能成功完成整個任務的機率。在設計分散式系統時，若系統硬體架構已固定，系統可靠度主要是受軟體設計影響，而任務配置是軟體設計的一個重要階段，因此本研究提出一適用於機率型分散式系統的任務配置決策模式，此模式的決策目標為系統可靠度最大化，而我們的系統可靠度函數是以Cheung所提出的馬可夫模式為發展基礎，由模組可靠度、節點的硬體可靠度、模組的執行轉移機率與模組配置策略所構成。此模式是以運算節點的儲存空間與運算負載量以及所能承擔的最大系統成本做為本模式的限制條件，使用限制規劃求解。最後，我們利用一案例說明此模式之應用，並針對模組可靠度與節點硬體可靠度進行敏感度分析。

With the advantages of high speed and high reliability, distributed systems, like power control system or ATM, have already been widely applied in daily lives. In a distributed system, a software application could be called a task and software is composed of a set of cooperating modules. Each module of a task will be executed on one of the processors of the distributed system. Then the system reliability of a distributed system could be defined as the probability that the system can run an entire task successfully. In designing a distributed system, if its hardware configuration is fixed, then its system reliability will depend mainly on the software design. Task allocation is an important step in distributed software design. This thesis aims to build a decision model of task allocation that is suitable for the stochastic distributed systems. Based on the Markov model proposed by Cheung, the objective function of the model is to maximize the system reliability, which is composed of module reliability, hardware reliability of processing nodes, transition probability between modules, and module allocation strategy. The model includes constraints about storage and load limitations at each processor and constraints about bounds of system cost, and solves the task allocation problem by Constraint Programming. Finally, we apply the decision model in an extended case, and perform sensitivity analysis for module reliability and hardware reliability.

目 錄
第1章 緒論	1
1.1 研究背景與動機	1
1.2 研究目的	3
1.3 論文架構	4
第2章 文獻探討	7
2.1 系統可靠度計算方式	7
2.2 分散式系統任務配置相關文獻	9
2.3 限制規劃	15
第3章 模式建構	18
3.1 問題定義	18
3.2 系統環境的假設與限制	18
3.3 變數說明	19
3.4 系統可靠度計算	22
3.5 模式限制式	24
3.6 任務配置決策模式	26
第4章 模式案例與敏感度分析	27
4.1 案例說明	27
4.2 敏感度分析	30
第5章 結論與未來研究方向	35
5.1 結論	35
5.2 未來研究方向	36
參考文獻	38
附錄一 敏感度分析數據	40
附錄二 模式程式碼	43

圖 目 錄
圖 1：研究流程圖	6
圖 2：模組的轉移執行機率	29
圖 3：各模組可靠度改變對系統可靠度的影響	32
圖 4：各節點硬體可靠度改變對系統可靠度的影響	33

表 目 錄
表1 節點的儲存負荷量、運算負載量及硬體可靠度	27
表2 模組的儲存需求量、運算需求量及可靠度	28
表3 節點間的通訊連結其單位資料量的傳輸成本(元/KB)	28
表4 模組在各個節點上的執行成本(/元)	28
表5 模組間的傳輸資料量(/KB)	28

附 表 目 錄
附表1  p1與各模組的可靠度改變對系統可靠度影響	40
附表2  p2與各模組的可靠度改變對系統可靠度影響	41
附表3  p4與各模組的可靠度改變對系統可靠度影響	42

1.Bannister, J.A and Trivedi, K.S, "Task allocation in fault-tolerant distributed systems", Acta Informatica, 1983, Vol. 20, pp. 261-181
2.Barta'k, R., "On-Line Guide to Constraint Programming," http://kti.mff.cuni.cz/~bartak/constraints/
3.Brailsford, S.C., Potts, C.N., Smith, B.M, "Constraint satisfaction problem: algorithms and application", European Journal of Operational Research, 1999, Vol. 119, pp. 557-581
4.Cheung, R.C. "A user-oriented software reliability model", IEEE Transactions on Software Engineering, 1980, Vol. SE-6, pp. 118-125
5.Hariri, S. and Raghavendra, C.S, " Distributed functions allocation for reliability and delay optimization", Proc. IEEE/ACM 1986 Fall Joint Computer conference, 1986, pp. 344-352
6.Hentenryck, P.V., "The OPL optimization programming language", Massachusetts Institute of Technology, 1999
7.Hsieh, C.C and Hsieh, Y.C., "Reliability and cost optimization in distributed computer systems", Computers & Operations Research, 2003, Vol. 30, pp. 1103-1119
8.Hsieh, C.C., " Optimal task allocation and hardware redundancy policies in distributed computing systems", European Journal of Operational Research, 2003, Vol. 147, pp. 430-447
9.Kartik, S. and Murthy, C.S.R., "Improved task-allocation algorithms to maximize reliability of redundant distributed computing systems", IEEE Transactions on Computers, 1995, Vol. 44, pp. 575-586
10.Kartik, S. and Murthy, C.S.R., "Task allocation algorithms for maximizing reliability of distributed computing systems", IEEE Transactions on Computers, 1997, Vol. 43, pp. 719-724
11.Rajgopal, J. and Mazumdar, M., "Modular operational test plans for inferences on software reliability based on a Markov model", IEEE Transactions on Software Engineering, 2002, Vol. 28, pp. 358-363
12.Reussner, R.H., Schmidt, H.W., Poernomo, I.H, "Reliability prediction for component-based software architectures", Journal of System and Software, 2003, Vol. 66, pp. 241-252
13.Shatz, S.M and Wang, J.P., "Models & algorithms for reliability-oriented task-allocation in redundant distributed-computer systems", IEEE Transactions on Reliability, 1989, Vol. 38, pp. 16-27
14.Shatz, S.M., Wang, J.P. and Goto, M., "Task allocation for maximizing reliability of distributed computer systems", IEEE Transactions on Computers, 1992, Vol. 41, pp. 1156-1168
15.Siegrist, K., "Reliability of systems with Markov transfer of control",  IEEE Transactions on Reliability, 1988, Vol. 14, pp. 1049-1053
16.Tom, P.A. and Murthy, C.S.R., " Algorithms for reliability-oriented module allocation in distributed computing systems", Journal of Systems and Software, 1998, Vol. 40, pp. 125-138
17.Tom, P.A. and Murthy, C.S.R., "An Improved algorithm for module allocation in distributed computing systems", Journal of Parallel and Distributed Computing, 1997, Vol. 42, pp. 82-90
18.Tsang, E., "Foundations of constraint satisfaction", ACADEMIC PRESS, 1993
19.Vidyarthi, D. P., Tripathi, A. K., "Maximizing reliability of distributed computing system with task allocation using simple genetic algorithm", Journal of Systems Architecture, 2001, Vol. 47, pp. 549-554
20.Wang, J.P. and Shatz, S.M, "Reliability-oriented task-allocation in redundant distributed systems", In Proc. 12th International Conference on Computer & Applications, 1988, Vol. 38, pp. 276-283
21.Wang, J.P. and Shatz, S.M., "Task allocation for optimized system reliability", Reliable Distributed Systems , Seventh Symposium on 10-12 Oct, 1988, pp. 82-90
22.林詩芹，"以限制規劃構建全年無休服務人員排班模式-以客服人員排班為例"，國立交通大學運輸科技與管理學系碩士論文，民國九十二年六月
23.陳彥良，"分散式系統中考量可靠度與執行時間之最佳任務配置"，國立成功大學工業管理研究所碩士論文，民國九十年六月