在平行運算環境中，可靠度是一項重要的議題。而在程序排程應用問題中，同時最佳化可靠度與最小化完成時間，是一個NP-Complete問題。為了增加平行運算中應用程序的可靠度，複製任務是一項很常用的技術[4, 38, 43]。本研究提出一個利用線性規劃的方法，找出最適合的任務複製數，而使得排程時可靠度可以滿足使用者需求，同時又可以有最短的完成時間。
本研究之可靠度評估，同時考慮處理機與通訊。其可靠度表示一個應用程序中各相依性的工作可以在此平行環境中成功執行的機率。最後經由實驗結果顯示，在某些情況之下，本研究提出演算法優於過去研究所提出的演算法。

In parallel computing environment, the reliability is an important issue in the scheduling problem. Optimizing both finish time and reliability in task scheduling problem is a NP-complete problem. In order to increase the reliability of task scheduling, duplicating task is a very common technique. In this thesis, we propose a method of linear programming to find the most suitable duplication number of each task as possible, such that there is fastest finish time in the scheduling. Otherwise, the reliability must meet the requirement specified by users or systems. In this study, the reliability evaluation considers both processor and communication link. The reliability is a probability representing successful implementation of an application in computer clusters. Finally, the experimental results show that the presented algorithm outperforms other ones proposed.

[1] T. L. Adam, K. M. Chandy, and J. Dickson, "A comparison of list schedules for parallel processing systems," Communications of the ACM, vol. 17, pp. 685-690, 1974.
[2] J. G. Barbosa and B. Moreira, "Dynamic scheduling of a batch of parallel task jobs on heterogeneous clusters," Parallel Computing, vol. 37, pp. 428-438, 8// 2011.
[3] L. F. Bittencourt, R. Sakellariou, and E. R. M. Madeira, "DAG Scheduling Using a Lookahead Variant of the Heterogeneous Earliest Finish Time Algorithm," in Parallel, Distributed and Network-Based Processing (PDP), 2010 18th Euromicro International Conference on, 2010, pp. 27-34.
[4] C. Boeres, I. M. Sardiña, and L. Drummond, "An efficient weighted bi-objective scheduling algorithm for heterogeneous systems," Parallel Computing, vol. 37, pp. 349-364, 2011.
[5] Y.-R. Chang, C.-Y. Huang, and S.-Y. Kuo, "Performance assessment and reliability analysis of dependable and distributed computing systems based on BDD and recursive merge," Applied Mathematics and Computation, vol. 217, pp. 403-413, 2010.
[6] D.-J. Chen, R.-S. Chen, and T.-H. Huang, "A heuristic approach to generating file spanning trees for reliability analysis of distributed computing systems," Computers & Mathematics with Applications, vol. 34, pp. 115-131, 1997.
[7] A. Doğan and F. Özgüner, "Biobjective scheduling algorithms for execution time–reliability trade-off in heterogeneous computing systems," The Computer Journal, vol. 48, pp. 300-314, 2005.
[8] J. J. Dongarra, E. Jeannot, E. Saule, and Z. Shi, "Bi-objective scheduling algorithms for optimizing makespan and reliability on heterogeneous systems," in Proceedings of the nineteenth annual ACM symposium on Parallel algorithms and architectures, 2007, pp. 280-288.
[9] H. Fan and X. Sun, "A multi-state reliability evaluation model for P2P networks," Reliability engineering & System safety, vol. 95, pp. 402-411, 2010.
[10] A. Gerasoulis and T. Yang, "A comparison of clustering heuristics for scheduling directed acyclic graphs on multiprocessors," Journal of Parallel and Distributed Computing, vol. 16, pp. 276-291, 1992.
[11] Y. He, Z. Shao, B. Xiao, Q. Zhuge, and E. Sha, "Reliability driven task scheduling for heterogeneous systems," in Fifteenth IASTED International Conference on Parallel and Distributed Computing and Systems, 2003, pp. 465-470.
[12] J. Hwang, Y. Chow, F. Anger, and C. Lee, "Scheduling Precedence Graphs in Systems with Interprocessor Communication Times," SIAM Journal on Computing, vol. 18, pp. 244-257, 1989.
[13] Q.-M. Kang, H. He, H.-M. Song, and R. Deng, "Task allocation for maximizing reliability of distributed computing systems using honeybee mating optimization," Journal of Systems and Software, vol. 83, pp. 2165-2174, 2010.
[14] S. Kartik and C. S. R. Murthy, "Improved task-allocation algorithms to maximize reliability of redundant distributed computing systems," Reliability, IEEE Transactions on, vol. 44, pp. 575-586, 1995.
[15] S. Kartik and C. S. R. Murthy, "Task allocation algorithms for maximizing reliability of distributed computing systems," IEEE Transactions on Computers, vol. 46, pp. 719-724, 1997.
[16] H. Kasahara and S. Narita, "Practical multiprocessor scheduling algorithms for efficient parallel processing," IEEE Transactions on Computers, vol. 33, pp. 1023-1029, 1984.
[17] M. A. Khan, "Scheduling for heterogeneous Systems using constrained critical paths," Parallel Computing, vol. 38, pp. 175-193, 2012.
[18] S. C. Kim, S. Lee, and J. Hahm, "Push-pull: Deterministic search-based dag scheduling for heterogeneous cluster systems," IEEE Transactions on Parallel and Distributed Systems, vol. 18, pp. 1489-1502, 2007.
[19] B. Kruatrachue and T. Lewis, "Grain size determination for parallel processing," Software, IEEE, vol. 5, pp. 23-32, 1988.
[20] Y.-K. Kwok and I. Ahmad, "Dynamic critical-path scheduling: An effective technique for allocating task graphs to multiprocessors," IEEE Transactions on Parallel and Distributed Systems, vol. 7, pp. 506-521, 1996.
[21] M.-S. Lin, M.-S. Chang, D.-J. Chen, and K.-L. Ku, "The distributed program reliability analysis on ring-type topologies," Computers & Operations Research, vol. 28, pp. 625-635, 2001.
[22] A. Litke, D. Skoutas, K. Tserpes, and T. Varvarigou, "Efficient task replication and management for adaptive fault tolerance in mobile grid environments," Future Generation Computer Systems, vol. 23, pp. 163-178, 2007.
[23] J. S. Plank and W. R. Elwasif, "Experimental assessment of workstation failures and their impact on checkpointing systems," in Fault-Tolerant Computing, 1998. Digest of Papers. Twenty-Eighth Annual International Symposium on, 1998, pp. 48-57.
[24] X. Qin and H. Jiang, "A dynamic and reliability-driven scheduling algorithm for parallel real-time jobs executing on heterogeneous clusters," Journal of Parallel and Distributed Computing, vol. 65, pp. 885-900, 2005.
[25] P. Rebreyend, F. Sandnes, and G. Megson, "Static multiprocessor task graph scheduling in the genetic paradigm: A comparison of genotype representations," 1998.
[26] B. S. Sabrina, H. Kalla, S. Kalla, and C. Arar, "A two-step bicriteria scheduling approach for distributed real time systems," in Electronics, Computer and Computation (ICECCO), 2013 International Conference on, 2013, pp. 314-317.
[27] V. Sarkar, Partitioning and scheduling parallel programs for multiprocessors: MIT press, 1989.
[28] G. C. Sih and E. A. Lee, "A compile-time scheduling heuristic for interconnection-constrained heterogeneous processor architectures," IEEE Transactions on Parallel and Distributed Systems, vol. 4, pp. 175-187, 1993.
[29] O. Sinnen and L. Sousa, "List scheduling: extension for contention awareness and evaluation of node priorities for heterogeneous cluster architectures," Parallel Computing, vol. 30, pp. 81-101, 2004.
[30] O. Sinnen, L. A. Sousa, and F. E. Sandnes, "Toward a realistic task scheduling model," IEEE Transactions on Parallel and Distributed Systems, vol. 17, pp. 263-275, 2006.
[31] O. Sinnen, A. To, and M. Kaur, "Contention-aware scheduling with task duplication," Journal of Parallel and Distributed Computing, vol. 71, pp. 77-86, 2011.
[32] S. Swaminathan and G. Manimaran, "A reliability-aware value-based scheduler for dynamic multiprocessor real-time systems," in Parallel and Distributed Processing Symposium, International, 2002, pp. 0098b-0098b.
[33] X. Tang, K. Li, R. Li, and B. Veeravalli, "Reliability-aware scheduling strategy for heterogeneous distributed computing systems," Journal of Parallel and Distributed Computing, vol. 70, pp. 941-952, 2010.
[34] X. Tang, K. Li, and G. Liao, "An effective reliability-driven technique of allocating tasks on heterogeneous cluster systems," Cluster Computing, pp. 1-13, 2014.
[35] X. Tang, K. Li, G. Liao, and R. Li, "List scheduling with duplication for heterogeneous computing systems," Journal of Parallel and Distributed Computing, vol. 70, pp. 323-329, 2010.
[36] X. Tang, K. Li, M. Qiu, and E. H.-M. Sha, "A hierarchical reliability-driven scheduling algorithm in grid systems," Journal of Parallel and Distributed Computing, vol. 72, pp. 525-535, 2012.
[37] H. Topcuoglu, S. Hariri, and W. Min-You, "Performance-effective and low-complexity task scheduling for heterogeneous computing," Parallel and Distributed Systems, IEEE Transactions on, vol. 13, pp. 260-274, 2002.
[38] S. Tosun, "Energy-and reliability-aware task scheduling onto heterogeneous MPSoC architectures," The Journal of Supercomputing, vol. 62, pp. 265-289, 2012.
[39] J. D. Ullman, "< i> NP</i>-complete scheduling problems," Journal of Computer and System sciences, vol. 10, pp. 384-393, 1975.
[40] M.-Y. Wu and D. D. Gajski, "Hypertool: A programming aid for message-passing systems," IEEE Transactions on Parallel and Distributed Systems, vol. 1, pp. 330-343, 1990.
[41] T. Yang and A. Gerasoulis, "PYRROS: static task scheduling and code generation for message passing multiprocessors," presented at the Proceedings of the 6th international conference on Supercomputing, Washington, D. C., USA, 1992.
[42] H. Zhao and R. Sakellariou, "An experimental investigation into the rank function of the heterogeneous earliest finish time scheduling algorithm," in Euro-Par 2003 Parallel Processing, ed: Springer, 2003, pp. 189-194.
[43] L. Zhao, Y. Ren, and K. Sakurai, "Reliable workflow scheduling with less resource redundancy," Parallel Computing, vol. 39, pp. 567-585, 2013.