工作排程問題是一個被廣泛研究的問題，在異質計算環境之下的排程問題在一般情況下屬於NP-complete問題，通常會加入限制條件以減低問題複雜度，因此針對不同排程問題許多不同的演算法被提出。本研究提出了一個工作複製排程演算法類別的演算法DDC(Duplication-based scheduling algorithm with Different Capabilities)。在DDC演算法中，利用了串列式排程演算法及工作複製演算法的概念，可在較低的成本內取得較佳解，並且複製工作節點以縮短工作節點之間的通訊成本，其中我們採用複製最重要的父節點的方法以達到減少排程長度。在實驗分析中，利用隨機的方式產生工作圖，來分析提出方法之優劣，並和相關研究中所提及的演算法作比較，比較結果顯示本研究所提出之方法表現優於其他方法。

Task scheduling problem has been extensively studied. In heterogeneous computing environments, many scheduling problems have been shown to be NP-complete in general cases. In order to reduce the problem complexities, they usually added some constraints on the scheduling problems; therefore various algorithms have been proposed in the literature. In this thesis, we present a new duplication-based scheduling algorithm, called Duplication-based scheduling algorithm with Different Capabilities (DDC). In DDC algorithm, we use the concepts of list scheduling and duplication-based scheduling to obtain better scheduling results with lower time complexities. Moreover, we can duplicate the most critical parent in order to reduce the communication cost and thus reduce the longest schedule length. The experimental results based on randomly generated graphs reveal that our scheduling algorithm performs better than those of related work.

[1] M.C.L. Abeyasinghe, D.J. Greenwood, and D.E. Johansen, “An efficient method for scheduling construction projects with resource constraints”, International Journal of Project Management, Vol. 19, pp. 29-45, 2001.
[2] R. Bajaj, and D.P. Agrawal, “Improving Scheduling of Tasks in a Heterogeneous Environment”, IEEE Transactions Parallel and Distributed Systems, Vol. 15, No. 2, pp. 107-118, February 2004.
[3] S. Bansal, P. Kumar, and K. Singh, “An Improved Duplication Strategy for Scheduling Precedence Constrained Graphs in Multiprocessor Systems”, IEEE Transactions Parallel and Distributed Systems, Vol. 14, No. 6, pp. 533-544, June 2003.
[4] D. Bozdag, F. Ozguner, E. Ekici, and U. Catalyurek, “A Task Duplication Based Scheduling Algorithm Using Partial Schedules”, International Conference on Parallel Processing, 2005.
[5] P. Chaudhuri, and J. Elcock, “Task scheduling in multiprocessing systems using duplication”, Journal of Systems Architecture, Vol. 54, pp. 519-529, 2008.
[6] M.I. Daoud, and N. Kharma, “A high performance algorithm for static task scheduling in heterogeneous distributed computing systems”, Journal of Parallel Distributed Computing, Vol. 68, pp. 399-409, 2008.
[7] S. Darbha, and D.P. Agrawal, “A Task Duplication Based Scalable Scheduling Algorithm for Distributed Memory Systems”, Journal of Parallel Distributed Computing, Vol. 46, pp. 15-27, 1997.
[8] E.S.H. Hou, N. Ansari, and H. Ren, “A Genetic Algorithm for Multiprocessor Scheduling”, IEEE Transactions Parallel and Distributed Systems, Vol. 5, No. 2, pp. 113-120, February 1994
[9] Y. Kwok, and I. Ahmad, “Dynamic Critical-Path Scheduling: An Effective Technique for Allocating Task Graphs to Multi-processors”, IEEE Transactions Parallel and Distributed Systems, Vol. 7, No. 5, pp. 506-521, May 1996.
[10] J. Liou, and M.A. Palis, “An Efficient Clustering Heuristic for Scheduling DAGs on Multiprocessors”, Proc. Symp. Parallel and Distributed Processing, 1996.
[11] G. Liu, K. Poh, and M. Xie, “Iterative list scheduling for heterogeneous computing”, Journal of Parallel Distributed Computing, Vol. 65, No. 5, pp. 654-665, 2005.
[12] C.I. Park, and T.Y. Choe, “An Optimal Scheduling Algorithm Based on Task Duplication”, IEEE Transactions on Computers, Vol. 51, No. 4, pp. 444-448, April 2002.
[13] J.P. Sheu, and Z.F. Chiang, “Efficient Allocation of Chain-Like Task on Chain-Like Network Computers”, Information Processing Letters, Vol. 36, pp. 241-245, 1990.
[14] Z. Shi, and J.J. Dongarra, “Scheduling workflow applications on processors with different capabilities”, Future Generation Computer Systems, Vol. 22, pp. 665-675, 2006.
[15] K. Shin, M. Cha, M. Jang, J.H. Jung, W.O. Yoon, and S.B. Choi, “Task Scheduling Algorithm using Minimized Duplications in Homogeneous Systems”, Journal of Parallel Distributed Computing,, Vol. 68, Issue. 8, pp. 1146-1156, August 2008.
[16] H. Topcuoglu, S. Hariri, and M.Y. Wu, “Performance-Effective and Low-Complexity Task Scheduling for Heterogeneous Computing”, IEEE Transactions Parallel and Distributed Systems, Vol. 13, No. 3, pp. 260-274, March 2002.
[17] L. Wang, H.J. Siegel, and V.P. Roychowdhury, “A Genetic-Algorithm-Based Approach for Task Matching and Scheduling in Heterogeneous Computing Environments”, Proc. Heterogeneous Computing Workshop, 1996.
[18] T. Yang, and A. Gerasoulis, “DSC: Scheduling Parallel Tasks on an Unbounded Number of Processors”, IEEE Transactions Parallel and Distributed Systems, Vol. 5, No. 9, pp. 951-967, September 1994.
[19] H. Zhao, and R. Sakellariou, “An experimental investigation into the rank function of the heterogeneous earliest finish time scheduling algorithm”, Proceedings of 9th International Euro-Par Conference, Springer-Verlag, 2003.