Improving the efficiency of scheduling jobs driven by a common limited energy source

摘要

We consider a problem of scheduling independent preemptable jobs on parallel identical machines to minimize a makespan. The processing rate of a job depends on a temporal allocation of limited power. Moreover, we assume that energy consumption is also constrained. Thus power/energy is treated as a doubly-constrained resource. In consequence the problem is to find a sequence of jobs on machines and simultaneously to determine an allocation of power to jobs that lead to a feasible schedule of minimal length. A complex non-linear mathematical programming problem has to be solved in a general case. In this paper we propose a solution procedure that utilizes an observation that usually only one limit for doubly-constrained resource is active in an optimal schedule.