Heuristics with grouping of jobs for power-aware scheduling problems
[ 1 ] Instytut Informatyki, Wydział Informatyki, Politechnika Poznańska | [ P ] employee
2015
paper
english
EN We consider a problem of scheduling independent preemptable jobs on parallel identical machines with the schedule length criterion. The processing rate of a job at a given moment depends on the temporal amount of power allocated to this job. Available power and energy are treated as a doubly-constrained resource, thus the problem is to find the schedule with the minimal length which respects the given limits of all resources. A known method for finding an optimal solution assumes that a particular non-linear mathematical programming problem is formulated and solved. Unfortunately, the number of variables in the problem grows exponentially with the size of an instance. Thus we propose heuristic approach for the considered problem. The heuristics utilizes the concept of grouping jobs with the same processing characteristics. The effectiveness of the algorithm with different settings is tested basing on a computational experiment.
47 - 51
WoS (15)