A genetic algorithm for tasks scheduling in parallel multiprocessor systems

被引:14
作者
Zhong, YW [1 ]
Yang, JG [1 ]
机构
[1] Zhejiang Univ, Coll Comp Sci & Technol, Hangzhou 310027, Peoples R China
来源
2003 INTERNATIONAL CONFERENCE ON MACHINE LEARNING AND CYBERNETICS, VOLS 1-5, PROCEEDINGS | 2003年
关键词
task scheduling; genetic algorithm; parallel multiprocessor systems; task execution order list; sequence list;
D O I
10.1109/ICMLC.2003.1259786
中图分类号
TP18 [人工智能理论];
学科分类号
081104 ; 0812 ; 0835 ; 1405 ;
摘要
The tasks scheduling problem is a key factor for a parallel multiprocessor system to gain better performance. Because a task can be partitioned into a group of subtasks and represented as a DAG (Directed Acyclic Graph), so the problem can be stated as finding a schedule for a DAG to be executed in a parallel multiprocessor system so that the schedule length can be minimized. The tasks scheduling problem is NP-hard in general, except in a few simplified situations. In order to obtain optimal or suboptimal solutions, a large number of scheduling heuristics have been presented in the literature. The most studied heuristics are based on list heuristic. Recently, genetic algorithm has received much attention as a class of heuristic. This paper presents a new genetic algorithm called TEOL (Task Execution Order List based genetic algorithm) to solve the scheduling problem in parallel multiprocessor systems. It guarantees that all feasible schedules can be reached with some probability, and because the TEOL is based on the restrain of predecessor relationship of the DAG only, so other heuristics can be combined into it to improve the performance. Simulation results comparing with two genetic algorithms and a list algorithm, both from the literature, show that TEOL produces encouraging results in terms of quality of solution and execution speed.
引用
收藏
页码:1785 / 1790
页数:6
相关论文
共 50 条
[11]   Scheduling of Tasks in Multiprocessor System Using Hybrid Genetic Algorithms [J].
Varghes, Betzy ;
Hossain, Alamgir ;
Dahal, Keshav .
APPLICATIONS OF SOFT COMPUTING, 2009, 52 :65-74
[12]   Research on Scheduling Algorithm Based on Genetic Algorithm for Grid Tasks [J].
Liu, Hongzhi ;
Zhang, Wenyue ;
Hao, Jianqiang ;
Sun, Jianzhi ;
Li, Yuehui .
2010 2ND INTERNATIONAL CONFERENCE ON E-BUSINESS AND INFORMATION SYSTEM SECURITY (EBISS 2010), 2010, :418-421
[13]   A novel intelligent method for task scheduling in multiprocessor systems using genetic algorithm [J].
Shenassa, Mohammad Hassan ;
Mahmoodi, Mahdi .
JOURNAL OF THE FRANKLIN INSTITUTE-ENGINEERING AND APPLIED MATHEMATICS, 2006, 343 (4-5) :361-371
[14]   A Multi-Population Based Parallel Genetic Algorithm for Multiprocessor Task Scheduling with Communication Costs [J].
Morady, Rashid ;
Dal, Deniz .
2016 IEEE SYMPOSIUM ON COMPUTERS AND COMMUNICATION (ISCC), 2016, :766-772
[15]   Genetic Algorithm Solution for Scheduling Jobs in Multiprocessor Environment [J].
Kaur, Ravreet ;
Singh, Gurvinder .
2012 ANNUAL IEEE INDIA CONFERENCE (INDICON), 2012, :968-973
[16]   An ordered-deme genetic algorithm for multiprocessor scheduling [J].
Jung, BJ ;
Park, KI ;
Park, KH .
IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS, 2000, E83D (06) :1207-1215
[17]   Fault tolerant scheduling of hard real-time tasks on multiprocessor system using a hybrid genetic algorithm [J].
Samal, Abhaya Kumar ;
Mall, Rajib ;
Tripathy, Chittaranjan .
SWARM AND EVOLUTIONARY COMPUTATION, 2014, 14 :92-105
[18]   Energy-Aware Real-Time Task Scheduling in Multiprocessor Systems Using a Hybrid Genetic Algorithm [J].
Mahmood, Amjad ;
Khan, Salman A. ;
Albalooshi, Fawzi ;
Awwad, Noor .
ELECTRONICS, 2017, 6 (02)
[19]   Bayesian optimization algorithm for multi-objective scheduling of time and precedence constrained tasks in heterogeneous multiprocessor systems [J].
Muhuri, Pranab K. ;
Biswas, Sajib K. .
APPLIED SOFT COMPUTING, 2020, 92 (92)
[20]   A Parallel Genetic Simulated Annealing Hybrid Algorithm for Task Scheduling [J].
SHU Wanneng ZHENG Shijue Department of Computer Science Huazhong Normal University Wuhan Hubei China .
WuhanUniversityJournalofNaturalSciences, 2006, (05) :1378-1382