在異質處理器分散式計算環境中，傳統的工作排程(task scheduling) 考慮的主要目標為最短完成時間(makespan) 與演算法複雜度的最小化。近年來，節省能源的意識日漸升高，能源消耗因子在工作排程中漸漸被納入考量，由於這樣原因，動態電壓頻率擴增(DVFS) 技術已逐漸發展並運用在處理器[11, 39]。在處理器運行時，處理器能調節其電壓而達到省能的目的，而將電壓調降會讓能源消耗減低，但卻導致工作執行時間上升，所以，能源消耗最小化與完成時間最短化是一個折衷(trade-off) 議題。

先前研究在處理降低能源消耗與最短完成時間排程方法是在排程後在保持完成時間不變的情況下，運用動態電壓頻率擴增(DVFS) 技術降低電壓，或是在排程中用局部(local) 最佳解的方式考慮能源與時間的平衡。本論文研究提出在排程前考慮全域性(global) 工作的能源耗費與執行時間平衡，並以線性編碼(linear programming) 解出適當的執行時間與相對應能源消耗。在工作排程演算法中，本論文提出的演算法是改良於Topcuouglu et al. [33] 所提出的方法。在排程之後，我們再運用Rizvandi et al. [27] 提出的線性組合方法來使能源消耗更加降低。實驗證實，在考慮能源與完成時間雙目標之情況下，本論文所提出的方法較先前研究有更好的結果，特別是在同質處理器環境中。

The objective of traditional task scheduling in heterogeneous distributed computing environment considers both makespan and time complexity. In recent years, the energy saving is an important issue; therefore a factor of energy consumption is also taken into account in task scheduling. Because of this reason, the dynamic voltage frequency scaling technology (DVFS) is developed and applied in processors that can reduce the energy consumption [11,39]. While the processor scales down the voltage to reduce energy consumption, the processing capability will be lower to increase the completion time of task, therefore, it is a trade-off problem between energy consumption and makespan.
In previous studies, many methods use DVFS to reduce energy consumption without increasing the makespan after scheduling, or develop local optimum algorithms that consider locally both the energy consumption and makespan during scheduling. In this thesis, we propose a global approach that considers both the energy consumption and makespan before scheduling, and use linear programming to solve execution time and corresponding energy consumption of each task. Afterwards, tasks are scheduled according to our proposed algorithm improved from the traditional method proposed by Topcuouglu et al. [33]. After scheduling, in order to reduce more energy consumption, we apply linear combination proposed by Rizvandi et al. [27]. In the experiments, our method have a good performance compared with previous studies particularly in homogeneous environment when energy consumption and makespan are both taken into account.

[1] I. Ahmad and Y. Kwok, ``On exploiting task duplication in parallel program scheduling,' Parallel and Distributed systems, IEEE Transactions on, Vol. 9, pp. 872--892, 1998.
[2] S. Bansal, P. Kumar, and K. Singh, ``Dealing with heterogeneity through limited duplication for scheduling precedence constrained task graphs,' Journal of Parallel and Distributed Computing, Vol. 65, pp. 479--491, 2005.
[3] R. Bianchini and R. Rajamony, ``Power and energy management for server systems,' Computer, Vol. 37, pp. 68--76, 2004.
[4] A. Chandrakasan, S. Sheng, and R. Brodersen, ``Lower-power cmos digital design,' Solid-State Circuits, IEEE Journal of, Vol. 27, pp. 491--484, 1992.
[5] Y.-C. Chung and S. Ranka, ``Applications and performance analysis of a compile-time optimization approach for list scheduling algorithms on distributed memory multiprocessors,' in Supercomputing '92., Proceedings, 1992, pp. 512--521.
[6] T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, ``Introduction to algorithms.' 2001.
[7] M. Daoud and N. Kharma, ``A high performance algorithm for static task scheduling in heterogeneous distributed computing systems,' Journal of Parallel and Distributed Computing, Vol. 68, pp. 399--409, 2008.
[8] S. Darbha and D. Agrawal, ``Optimal scheduling algorithm for distributed-memory machines,' Parallel and Distributed Systems, IEEE Transactions on, Vol. 9, pp. 87--95, 1998.
[9] C. Diaz, M. Guzek, J. Pecero, P. Bouvry, and S. Khan, ``Scalable and energy-efficient scheduling techniques for large-scale systems,' in Computer and Information Technology (CIT), 2011 IEEE 11th International Conference on, 2011, pp. 641--647.
[10] C. Diaz, M. Guzek, J. Pecero, G. Danoy, P. Bouvry, and S. Khan, ``Energy-aware fast scheduling heuristics in heterogeneous computing systems,' in High Performance Computing and Simulation (HPCS), 2011 International Conference on, 2011, pp. 478--484.
[11] M. Fleischmann, ``LongRunTM power management,' 2001.
[12] M. R. Garey and D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness. Macmillan Higher Education, 1979.
[13] L. K. Goh, B. Veeravalli, and S. Viswanathan, ``Design of fast and efficient energy-aware gradient-based scheduling algorithms for heterogeneous embedded multiprocessor systems,' Parallel and Distributed Systems, IEEE Transactions on, Vol. 20, pp. 1--12, 2009.
[14] T. Hagras and J. Janecek, ``A high performance, low complexity algorithm for compile-time task scheduling in heterogeneous systems,' Parallel Computing, Vol. 31, pp. 653--670, 2005.
[15] J.E.Pecero, H. Huacuja, P. Bouvry, A. Pineda, M. Loces, and J. Barbosa, ``On the energy optimization for precedence constrained applications using local search algorithms,' in High Performance Computing and Simulation (HPCS), 2012 International Conference on, 2012, pp. 133--139.
[16] H. Kimura, M. Sato, Y. Hotta, T. Boku, and D. Takahashi, ``Emprical study on reducing energy of parallel programs using slack reclamation by dvfs in a
power-scalable high performance cluster,' in Cluster Computing, 2006 IEEE International Conference on, 2006, pp. 1--10.
[17] K. Lai and C. Yang, ``A dominant predecessor duplication scheduling algorithm for heterogeneous systems,' The Journal of Supercomputing, Vol. 44, pp. 126--145, 2008.
[18] Y. Lee and A. Zomaya, ``Minimizing energy consumption for precedence-constrained applications using dynamic voltage scaling,' in Cluster Computing and the Grid, 2009. CCGRID '09. 9th IEEE/ACM International Symposium on, 2009, pp. 92--99.
[19] Y. Lee and A. Zomaya, ``Energy conscious scheduling for distributed computing systems under different operating conditions,' Parallel and Distributed Systems, IEEE Transactions on, Vol. 22, pp. 1374--1381, 2011.
[20] G. Liu, K. Poh, and M. Xie, ``Iterative list scheduling for heterogeneous computing,' Journal of Parallel and Distributed Computing, Vol. 65, pp. 654--665, 2005.
[21] J. Mei and K. Li, ``Energy-aware scheduling algorithm with duplication on heterogeneous computing systems,' in Grid Computing (GRID), 2012 ACM/IEEE 13th International Conference on, 2012, pp. 122--129.
[22] J. Mei, K. Li, and K. Li, ``Energy-aware task scheduling in heterogeneous computing environments,' Cluster Computing, Vol. 17, pp. 537--550, 2014.
[23] M.Mezmaz, N.Melab, Y.Kessaci, Y.C.Lee, E.G.Talbi, A.Y.Zomaya, and D.Tuyttens, ``A parallel bi-objective hybrid metaheuristic for energy-aware scheduling for cloud computing systems,' Journal of Parallel and Distributed Computing, Vol. 71, pp. 1497--1508, 2011.
[24] F. Omara and M. Arafa, ``Genetic algorithms for task scheduling problem,' Journal of Parallel and Distributed Computing, Vol. 70, pp. 13--22, 2010.
[25] H. Park and B. Kim, ``An optimal scheduling algorithm for minimizing the computing period of cyclic synchronous tasks on multiprocessors,' Journal of Systems and Software, Vol. 56, pp. 213--229, 2001.
[26] A. Radulescu and A. van Gemund, ``Low-cost task scheduling for distributed-memory machines,' Parallel and Distributed Systems, IEEE Transactions on, Vol. 13, pp. 648--658, 2002.
[27] N. Rizvandi, J. Taheri, and A. Zomaya, ``Some observations on optimal frequency selection in dvfs-based energy consumption minimization,' Journal of Parallel and Distributed Computing, Vol. 71, pp. 1154--1164, 2011.
[28] N. Rizvandi, J. Taheri, A. Zomaya, and Y. C. Lee, ``Linear combinations of dvfs-enabled processor frequencies to modify the energy-aware scheduling algorithms,' in Cluster, Cloud and Grid Computing (CCGrid), 2010 10th IEEE/ACM International Conference on, 2010, pp. 388--397.
[29] W. Shieh and C. Pong, ``Energy and transition-aware runtime task scheduling for multicore processors,' Journal of Parallel and Distributed Computing, Vol. 73, pp. 1225--1238, 2013.
[30] 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.
[31] M. Skutella, ``Approximation algorithms for the discrete time-cost tradeoff problem,' Mathematics of Operations Research, Vol. 23, pp. 909--929, 1998.
[32] 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.
[33] H. Topcuoglu, S. Hariri, and M.-Y. Wu, ``Performance-effective and low-complexity task scheduling for heterogeneous computing,' Parallel and Distributed Systems, IEEE Transactions on, Vol. 13, pp. 260--274, 2002.
[34] T.Thanavanich and P.Uthayopas, ``Efficient energy aware task scheduling for parallel workflow tasks on hybrids cloud environment,' in Computer Science and Engineering Conference (ICSEC), 2013 International, 2013, pp. 37--42.
[35] J. Ullman, ``Np-complete scheduling problems,' Journal of Computer and System Sciences, Vol. 10, pp. 384--393, 1975.
[36] L. Wang, S. U. Khan, D. Chen, J. Ko?odziej, R. Ranjan, C. zhong Xu, and A. Zomaya, ``Energy-aware parallel task scheduling in a cluster,' Future Generation Computer Systems, Vol. 29, pp. 1661--1670, 2013.
[37] L. Wang, G. von Laszewski, J. Dayal, and F. Wang, ``Towards energy aware scheduling for precedence constrained parallel tasks in a cluster with dvfs,' in Cluster, Cloud and Grid Computing (CCGrid), 2010 10th IEEE/ACM International Conference on, 2010, pp. 368--377.
[38] M. Weiser, B. Welch, A. Demers, and S. Shenker, ``Scheduling for reduced cpu energy,' Mobile Computing, Vol. 353, pp. 449--471, 1996.
[39] C. Xian, Y.-H. Lu, and Z. Li, ``Dynamic voltage scaling for multitasking real-time systems with uncertain execution time,' Computer-Aided Design of Integrated Circuits and Systems, IEEE Transactions on, Vol. 27, pp. 1467--1478, 2008.
[40] B. Xu, C. Zhao, and B. H. E. Hu, ``Job scheduling algorithm based on berger model in cloud environment,' Advances in Engineering Software, Vol. 42, pp. 419--425, 2011.
[41] C.-Y. Yang, J.-J. Chen, and T.-W. Kuo, ``An approximation algorithm for energy-efficient scheduling on a chip multiprocessor,' in Design, Automation and Test in Europe, 2005. Proceedings, 2005, pp. 468--473.
[42] L. M. Zhang, K. Li, D. C.-T. Lob, and Y. Zhang, ``Energy-efficient task scheduling algorithms on heterogeneous computers with continuous and discrete speeds,' Sustainable Computing: Informatics and Systems, Vol. 3, pp. 109--118, 2013.
[43] L. M. Zhang, K. Li, and Y.-Q. Zhang, ``Green task scheduling algorithms with energy reduction on heterogeneous computers,' in Progress in Informatics and Computing (PIC), 2010 IEEE International Conference on, 2010, pp. 560--563.
[44] L. M. Zhang, K. Li, and Y.-Q. Zhang, ``Green task scheduling algorithms with speeds optimization on heterogeneous cloud servers,' in Green Computing and Communications (GreenCom), 2010 IEEE/ACM Int'l Conference on & Int'l Conference on Cyber, Physical and Social Computing (CPSCom), 2010, pp. 76--80.
[45] X. Zhu, C. He, K. Li, and X. Qin, ``Adaptive energy-efficient scheduling for real-time tasks on dvs-enabled heterogeneous clusters,' Journal of Parallel and Distributed Computing, Vol. 72, pp. 751--763, 2012.
[46] Z. Zong, A. Manzanares, X. Ruan, and X. Qin, ``EAD and PEBD: Two energy-aware duplication scheduling algorithms for parallel tasks on homogeneous clusters,' Computers, IEEE Transactions on, Vol. 60, pp. 360--374, 2011.