پیوندهای مفید
آمار
| تعداد نشریات | 31 |
| تعداد شماره‌ها | 777 |
| تعداد مقالات | 7,394 |
| تعداد مشاهده مقاله | 15,902,004 |
| تعداد دریافت فایل اصل مقاله | 7,447,960 |
An Enhanced Genetic Algorithm for Task Scheduling in Heterogeneous Systems | ||
| Computational Sciences and Engineering | ||
| مقاله 1، دوره 3، شماره 2، آذر 2023، صفحه 177-188 اصل مقاله (445.55 K) | ||
| نوع مقاله: Original Article | ||
| شناسه دیجیتال (DOI): 10.22124/cse.2024.26504.1072 | ||
| نویسندگان | ||
| Saeed Mirpour Marzuni1؛ Javad Vahidi* 2 | ||
| 1Department of Electrical and Computer Engineering, University of Science and Technology of Mazandaran, Behshahr, Iran | ||
| 2Department of Computer Science, Iran University of Science and Technology, Tehran, Iran | ||
| چکیده | ||
| Generally, jobs are divided into smaller portions, in parallel and according to distributed processing, and each portion is called a task. Each task can execute dependently or independently. When introducing heterogeneous systems, it is desirable that tasks can run on these systems. Since it is advantageous that tasks running on heterogeneous systems are completed faster, the optimization of task scheduling is of great importance. Actually, task scheduling problems in heterogeneous systems are NP-hard and it is a crucial issue. In such problems, Directed Acyclic Graphs (DAGs) can be used as task graphs to be scheduled on heterogeneous systems. The proposed method presents a genetic algorithm with new operators and final scheduler to be scheduled on heterogeneous systems. The practicality and convergence of the algorithm are proved by Markov’s chain theory. The findings reveal that the currently proposed algorithm is more efficient in comparison to previously presented ones and also has a better make span. Moreover, it is concluded that the Enhanced Genetic Algorithm (EGA) achieves the solution faster in early generations. | ||
| کلیدواژه‌ها | ||
| Genetic Algorithm؛ Distributed Processing؛ Task Scheduling | ||
| مراجع | ||
|
[1] Xu, Y., Li, K., Hu, J., & Li, K. (2014). A genetic algorithm for task scheduling on heterogeneous computing systems using multiple priority queues. Information Sciences, 270, 255-287. [2] Arabnejad, H., & Barbosa, J. G. (2013). List scheduling algorithm for heterogeneous systems by an optimistic cost table. IEEE transactions on parallel and distributed systems, 25(3), 682-694. [3] Panwar, P., Sachdeva, S., & Rana, S. (2016). A genetic algorithm based scheduling algorithm for grid computing environments. In Proceedings of Fifth International Conference on Soft Computing for Problem Solving: SocProS 2015,1,165-173 Springer Singapore. [4] Coffman, E. G., & Bruno, J. L. (1976). Computer and job-shop scheduling theory. John Wiley & Sons. [5] Gary, M. R., & Johnson, D. S. (1979). Computers and Intractability: A Guide to the Theory of NP-completeness. [6] Ullman, J. D. (1975). NP-complete scheduling problems. Journal of Computer and System sciences, 10(3), 384-393. [7] Zomaya, A. Y., Ward, C., & Macey, B. (1999). Genetic scheduling for parallel processor systems: comparative studies and performance issues. IEEE Transactions on Parallel and Distributed systems, 10(8), 795-812. [8] Kwok, Y.K., Ahmad, I. (1999). Static scheduling algorithms for allocating directed task graphs to multiprocessors. ACM Comput. Surv. (CSUR) 31(4). [9] Topcuoglu, H., Hariri, S., & Wu, M. (2002). Performance-Effective and Low-Complexity Task Scheduling for Heterogeneous Computing. IEEE Trans. Parallel and Distributed Systems, 13(3), 260-274. [10] Canon, L.C., Jeannot, E., Sakellariou, R., & Zheng, W. (2008), Comparative Evaluation of the Robustness of Dag Scheduling Heuristics. Grid Computing: Achievements and Prospects, S.Gorlatch, P. Fragopoulou, and T. Priol, eds., Springer, 73-84. [11] Boeres, C., Filho, J.V., & Rebello, V. E. F. (2004). A Cluster-Based Strategy for Scheduling Task on Heterogeneous Processors. 16th Symp. Computer Architecture and High Performance Computing, 214-221. [12] Cirou, B., & Jeannot, E. (2001). Triplet: A Clustering Scheduling Algorithm for Heterogeneous Systems. Int’l Conf. Parallel Processing Workshops, 231-236. [13] Jiang, Y. S., & Chen, W. M. (2015). Task scheduling for grid computing systems using a genetic algorithm. The Journal of Supercomputing, 71(4), 1357-1377. [14] Holland, J. (1975). Adaptation in Natural and Artificial Systems. University of Michigan Press, Ann Arbor, MI, USA. [15] Agustı, L. E., Salcedo-Sanz, S., Jiménez-Fernández, S., Carro-Calvo, L., Del Ser, J., & Portilla-Figueras, J. A. (2012). A new grouping genetic algorithm for clustering problems. Expert Systems with Applications, 39(10), 9695-9703. [16] Mitchell, (1999). An Introduction to Genetic Algorithms. Cambridge, Massachusetts London, England: Massachusetts Institute of Technolog. [17] Li, F., Da Xu, L., Jin, C., & Wang, H. (2012). Random assignment method based on genetic algorithms and its application in resource allocation. Expert Systems with Applications, 39(15), 12213-12219. [18] Gebali, F. (2015). Analysis of Computer Networks. Cham Heidelberg New York Dordrecht London: Springer. [19] Panwar, P., Lal, A.K., & Singh, J. (2012). A Genetic algorithm based technique for efficient scheduling of tasks on multiprocessor system. In: Proceedings of the International Conference on Soft Computing for Problem Solving (SocProS 2011), 911–919. Springer India. | ||
|
آمار تعداد مشاهده مقاله: 259 تعداد دریافت فایل اصل مقاله: 17 |
||