A METAHEURISTIC APPROACH FOR STATIC SCHEDULING BASED ON CHEMICAL REACTION OPTIMIZER

摘要

Over the past several decades, scheduling has emerged as an area of critical research, thereby constituting a requisite process for myriad applications in real life. In this regard, many researchers have experimented and utilized various optimization algorithms to obtain optimized schedules. It is also noteworthy that the concepts of some optimization algorithms are essentially derived from nature. This paper aims to augment a compiler using a chemical reaction optimizer in order to identify an optimized instructions static schedule capable of being used within both single and multicore computer systems. This scheduling algorithm, which is denoted as SS-CRO (static scheduling using chemical reaction optimizer), is unique in that it provides alternative schedules involving different costs. Subsequently, SS-CRO tests the schedules in accordance with different types of instructions dependencies before making an appropriate selection. SS-CRO demonstrates that it can not only provide different schedule orders, but also make a competent selection of accepted solutions, whilst dismissing the inappropriate ones in a reasonable span of time. So, this paper presents SS-CRO algorithm that is used to obtain an optimized static scheduling, where SS-CRO has been implemented and evaluated analytically and experimentally. As analytical results, the number of steps for the SS-CRO approximately is O(Num_iteration?CROFun), where CROFun is the number of steps of the selected function. In the experiments results, SS-CRO achieved better execution time and higher accepted solutions in comparison with other optimization algorithms such as; SS-DA (static scheduling using duelist algorithm) and SS-GA (static scheduling using genetic algorithm). Furthermore, SS-CRO achieved the maximum percentage of number of solutions with respect to the execution time of all experiments for all proposed input cases, which is ranged as (10%-30%).