An accurate parallel genetic algorithm to schedule tasks on a cluster

✍ Scribed by Michelle Moore

• Publisher: Elsevier Science
• Year: 2004
• Tongue: English
• Weight: 234 KB
• Volume: 30
• Category: Article
• ISSN: 0167-8191
• DOI: 10.1016/j.parco.2003.12.005

✦ Synopsis

Recent breakthroughs in the mathematical estimation of parallel genetic algorithm parameters are applied to the NP-complete problem of scheduling multiple tasks on a cluster of computers connected by a shared bus. Numerous adjustments to the original method of parameter estimation were made in order to accurately reflect differences in the problem model. The parallel scheduler used m-ary encoding and included a shared communication bus constraint. Fitness was an indirect computation requiring an evaluation of the meaning and implications (i.e., effect on communication time) of the encoding. The degree of correctness was defined as the ''nearness'' to the optimal schedule that could be obtained in a limited amount of time. Experiments reveal that the parallel scheduling algorithm developed very accurate schedules when the modified parameter guidelines were used. This article describes the scheduling problem, the parallel genetic scheduler, the adjustments made to the mathematical estimations, the quality of the schedules that were obtained, and the accuracy of the schedules compared to mathematically predicted expected values.