الفهرس 
CHAPTER 1 INTRODUCTIONOnly 14 pages are availabe for public view
 |  | from | 97 |  |  |
| | | from | 97 | | |
Abstract
In the last decades, parallel processing systems are used in most applications. In these systems, task scheduling problems are considered as an important issue in managing multiprocessors. The challenge in task scheduling problems is to find the best schedule that achieves the best efficiency and the minimum make span in a reasonable amount of time. The classical methods used for solving these problems consume more time in this computing environment. In this thesis, a new hybrid meta-heuristic algorithm called Greedy Randomized Adaptive Search Procedure based Genetic Algorithm (GRASP-GA) is proposed to handle such problems.
In the proposed algorithm, the greedy randomized adaptive search procedure is adopted to construct a population of high-quality solutions. Then, the genetic algorithm is applied on the constructed population to improve these solutions. Two heuristic functions are adopted to guide GRASP, bottom-level and top-level. The proposed GRASP-GA is verified against a set of the state-of-the-art algorithms using some test problems that considered as benchmarks. The experimental results indicated the superiority of the proposed GRASP-GA over all the tested algorithms. Since, it can achieve the best performance in all test problems used in this experiment. Although the experimental results ensure the GRASP-GA is a good competitor and can be considered as a viable alternative. It is observed that GRASP-GA consumes more running time to find the best solution. To overcome this problem, a new hybrid metaheuristic algorithm called Greedy Randomized Adaptive Search Procedure based Simulated Annealing (GRASP-SA) is proposed to handle such problems.
In this proposal, GRASP algorithm is modified by adopting Simulated Annealing procedure instead of classical local search procedure used in GRASP. This leads to improve the classical GRASP through adding more capabilities to escape local optima. To identify the influence of the proposed modifications, the proposed GRASP-SA is verified against the original GRASP, the original SA and the recently developed GRASP-GA using the same set of bench-mark problems. The results indicate the proposed GRASP-SA has two-fold superiority over its competitors. It can achieve the schedule with the minimum make span for most test problems through the minimum running time for most test problems.