現今，工作排程問題已被廣泛地研究，但是有關不同能力限制之處理器工作排程研究卻非常有限。而在探討處理器有不同能力限制之研究中，大部分皆是使用靜態方法，例如：Scheduling workflow applications on processors with Different Capabilities (SDC)演算法及Duplication-based scheduling algorithm with Different Capabilities (DDC)演算法，其優先權串列是不會變動的，可能會喪失找到較佳優先權串列之機會。
因此，本研究提出了在不同能力下的動態串列式排程演算法 (Dynamic List scheduling algorithm with Different Capabilities, DLDC)，利用Heterogeneous Earliest-Finish-Time (HEFT)演算法及Longest Dynamic Critical Path (LDCP)演算法所提出的權重計算公式及動態關鍵路徑之方法來更動優先權串列，以取得較佳的優先權串列。並且在處理器的選擇方面，考慮到後繼任務節點是否能在同個處理器上執行，進而決定適合的處理器。
最後，透過實驗結果可以發現，處理器數量越多、不可用的處理器比率 (PIP)越低、CCR越接近1，則DLDC的效果越好。

Until now, task scheduling problem has been extensively studied, but the studies about processors with different capabilities are limited. In the studies about processors with different capabilities, most of them are using static methods, such as Scheduling workflow applications on processors with Different Capabilities (SDC) algorithm and Duplication-based scheduling algorithm with Different Capabilities (DDC) algorithm. The schedule lists of static methods cannot be changed, we may lose the opportunity of finding the better schedule lists.
Therefore, in this thesis, we present a new list scheduling algorithm, called Dynamic List scheduling algorithm with Different Capabilities (DLDC). In DLDC algorithm, we use the concepts of Heterogeneous Earliest-Finish-Time (HEFT) algorithm and Longest Dynamic Critical Path (LDCP) algorithm to obtain better scheduling list. And, in the select processor phase, we consider whether or not successors can be scheduled in the same processor, and then a suitable processor will be chose. Finally, experimental results reveal that DLDC algorithm outperforms those of the others.

[1] H.Arabnejad, and J.G.Barbosa, “List Scheduling Algorithm for Heterogeneous Systems by an Optimistic Cost Table”, IEEE Transactions Parallel and Distributed Systems, Vol. PP, Issue.99, March 2013.
[2] 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.
[3] 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.
[4] 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.
[5] F. Dong and S. G. Akl, “Scheduling Algorithms for Grid Computing: State of the Art and Open Problems”, Technical Report2006-504, School of Computing, Queen’s University, Kingston, Ontario, January 2006.
[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] B. Hamidzadeh, L.Y. Kit, and D.J. Lilja, “Dynamic task scheduling using online optimization”, IEEE Transactions Parallel and Distributed Systems, Vol. 11,No. 11, pp. 1151–1163, 2000.
[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] M. A. Khan, “Scheduling for heterogeneous systems using constrained critical paths." Parallel Computing, Vol. 38, Issues 4,pp. 175-193, April 2012.
[10] 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.
[11] W. M. Lin, and Q.Gu, “An efficient clustering-based task scheduling algorithm for parallel programs with task duplication”, Journal of information science and engineering, Vol. 23 No. 2, pp. 589-604, March 2007.
[12] J. Liou, and M.A. Palis, “An Efficient Clustering Heuristic for Scheduling DAGs on Multiprocessors”, Proc. Symp. Parallel and Distributed Processing, 1996.
[13] 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.
[14] 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.
[15] Z. Shi, and J.J. Dongarra, “Scheduling workflow applications on processors with different capabilities”, Future Generation Computer Systems, Vol. 22, pp. 665-675, 2006.
[16] 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.
[17] 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.
[18] X. Tang, K. Li, G. Liao, and R. Li, “List scheduling with duplication for heterogeneous computing systems”, Journal of Parallel Distributed Computing, Vol. 70, Issue 4, pp. 323-329, April 2010.
[19] H. M. Wang, and F. D. Chou, “Solving the parallel batch-processing machines with different release times, job sizes, and capacity limits by metaheuristics”, Expert Systems with Applications, Vol. 37, pp. 1510-1521, 2010.
[20] 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.
[21] 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.
[22] C. H. Yang, P. Lee, and Y. C. Chung, “Improving Static Task Scheduling in Heterogeneous and Homogeneous Computing Systems”, International Conference on Parallel Processing, pp. 45, September 2007.
[23] 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.

[24] 洪偉翔，「在不同能力下的工作複製排程演算法研究」，碩士論文，國立臺灣科技大學資訊管理系，臺北市，民國九十八年。