Authors : Hadi Shahamfar and Sohrab khanmohamadi
Abstract: Task scheduling is a crucial and complex problem in Multiprocessor systems and is defined NP-complete problem. Nowadays, with increasing size of programs and information. The multiprocessor Systems are widely used in parallel computing. In Many cases we can divide a huge problem into some small portions and assign these small problems to processors. This would result in a considerable reduction in the execution time of programs. Previous Algorithms have various restrictions in their assumptions such as tasks considered independent, task graph produced randomly or the zero considered communication delay. On the other hand the complexity of algorithms has been ignored. This is important since there should be a balance between the quality of solutions and execution time of algorithm. Comparison studies with realistic assumptions on scheduling algorithms have shown that some algorithms prefer quality of solutions to execution time of algorithms. This has caused them not to be applicable in realistic situations. In this study we present a new genetic algorithm that employs neighborhood search and tabu list for performing task scheduling (GTNS). This newly proposed algorithm has solved the mentioned problem, as well as having a reasonable execution time versus the makespan.
Hadi Shahamfar and Sohrab khanmohamadi , 2008. A New Genetic Algorithm Based on Neighborhood Search and Tabu List (GTNS) for Task Scheduling in Multiprocessor. International Journal of Soft Computing, 3: 254-259.