Population Local Search for Single Processor Energy Efficient Scheduling Problem
摘要
Energy consumption of computing devices is an important question at this day. One effective method for reducing energy consumption is dynamic speed scaling. The speeds are dynamically assigned to processors minimizing the total energy consumption and guaranteeing the required quality of schedules. The NP-hard offline energy-efficient scheduling of jobs on the single speed-scalable processor is considered in this work. We propose a population local search algorithm with two types of neighbourhoods. The first one is constructed based on one solution and uses swap and insert strategies with problem-specific adaptation. The second one is defined for pairs of solutions and it is based on the inheritance of values in positions of solution permutations. Experimental evaluation of instances of various structures shows that the algorithm demonstrates competitive results.