The Scientific World JOURNAL · 2014 · 38 citations · 22 references
ComputingComputer ScienceHeterogeneous ComputingOptimizationSchedulingHeuristic SearchResource SchedulingSchedule OptimizationScheduling OptimizationTask SchedulingHeterogeneous SchedulingHeterogeneous Task SchedulingHeuristic AlgorithmsMulti-resource SchedulingScheduling HeuristicsScheduling With Heterogeneous ResourcesStatic Task SchedulingTask Graphs
Aiming at the static task scheduling problems in heterogeneous environment, a heuristic task scheduling algorithm named HCPPEFT is proposed. In task prioritizing phase, there are three levels of priority in the algorithm to choose task. First, the critical tasks have the highest priority, secondly the tasks with longer path to exit task will be selected, and then algorithm will choose tasks with less predecessors to schedule. In resource selection phase, the algorithm is selected task duplication to reduce the interresource communication cost, besides forecasting the impact of an assignment for all children of the current task permits better decisions to be made in selecting resources. The algorithm proposed is compared with STDH, PEFT, and HEFT algorithms through randomly generated graphs and sets of task graphs. The experimental results show that the new algorithm can achieve better scheduling performance.
22
NP-complete scheduling problems
Jeffrey D. Ullman · Journal of Computer and System Sciences · 1975 · 1.4K citations