Optimal allocation of power - graphical interpretation of some scheduling problem
[ 1 ] Instytut Informatyki, Wydział Informatyki, Politechnika Poznańska | [ P ] employee
2016
paper
english
- optimal power allocation
- variable speed processor
EN We consider a practical makespan minimization problem that arises in a multiprocessor computer system where some processors may be shut down during computation to save an amount of shared power. The system consists of m processors driven by a common power source. The processors are modeled as a set of identical parallel machines. Moreover, we consider a set of n independent, nonpreemptive jobs which model a given set of computational tasks. Each job requires a machine and an amount of power for its processing. A processing time of a jobs is unknown a priori. Instead of this, each job is characterized by a size determined by a number of CPU cycles necessary to complete this job. The processing rate of a job depends on an amount of power allotted to this job at a moment. This relation is expressed by a non-decreasing processing rate function. Power is treated as a renewable continuous resource available in a constant amount. Each machine may be in one of two states: “power on”, and “power off”. In the “power on” state an idle machine uses a constant amount of power. A machine uses no power in the power off state. We assume that time of switch between states may be neglected and brings no additional costs. We identify some cases of optimal solutions for the simplest situation of two machines and jobs characterized by the same processing rate function.
975 - 980