سال انتشار: ۱۳۸۵

محل انتشار: دوازدهمین کنفرانس سالانه انجمن کامپیوتر ایران

تعداد صفحات: ۸

نویسنده(ها):

Saeed Parsa – Faculty of Computer Engineering, Iran University of Science and Technology, Tehran, Iran
Shahriar Lotfi – Faculty of Computer Engineering, Iran University of Science and Technology, Tehran, Iran
Naser Lotfi – Department of Computer Engineering, Shabestar Islamic Azad University, Shabestar, Iran

چکیده:

Effective scheduling is of great importance to parallel programming environments. The aim is to minimize the completion time of task graphs. The completion time of a task graph is directly affected by the length of its critical path. Hence, the trend of an evolutionary approach for task graph scheduling can be biased towards reduction of the critical path. Task graph scheduling is a NP-hard problem. Deterministic approaches are not
applicable in this context. Thereof, application of evolutionary processing and especially genetic algorithms are effective for solving scheduling problems. In this paper, a new genetic scheduling algorithm is presented. The algorithm, in the first priority, minimizes the critical path length of the parallel program task graph and in the second priority minimizes the inter-processor communication time. Thereby, it achieves a better scheduling in comparison with the existing approaches such as BCGA, CGL, MCP.