• Energy Research
• computer and information sciences close
• University of Hong Kong close

We consider the setting of a device that obtains its energy from a battery and some regenerative source such as a solar cell. We consider the speed scaling problem of scheduling a collection of tasks with release times, deadlines, and sizes, so as to minimize the energy recharge rate of the regenerative source. This is the first theoretical investigation of speed scaling for devices with a regenerative energy source. We show that the problem can be expressed as a polynomial sized convex program. We show that, using the KKT conditions, one can obtain an efficient algorithm to verify the optimality of a schedule. We show that the energy optimal YDS schedule is 2-approximate with respect to the recharge rate. We show that the online algorithm BKP is O(1)-competitive with respect to recharge rate.

Cascading failure causes a major risk to society currently. To effectively mitigate the risk, dynamic thermal rating (DTR) technique can be applied as a cost-effective strategy to exploit potential transmission capability. From the perspectives of service life and Braess paradox, it is important and challenging to jointly optimize the DTR placement and operation schedule for changing system state, which is a two-stage combinatorial problem with only discrete variables, suffering from no approximation guarantee and dimension curse only based on traditional models. Thus, the present work proposes a novel two-stage submodular optimization (TSSO) of DTR for risk mitigation considering placement and operation schedule. Specifically, it optimizes DTR placement with proper redundancy in first stage, and then determines the corresponding DTR operation for each system state in second stage. Under the condition of the Markov and submodular features in sub-function of risk mitigation, the submodularity of total objective function of TSSO can be proven for the first time. Based on this, a state-of-the-art efficient solving algorithm is developed that can provide a better approximation guarantee than previous studies by coordinating the separate curvature and error form. The performance of the proposed algorithms is verified by case results.

Energy usage has been an important concern in recent research on online scheduling. In this paper, we study the tradeoff between flow time and energy (Albers and Fujiwara in ACM Trans. Algorithms 3(4), 2007; Bansal et al. in Proceedings of ACM-SIAM Symposium on Discrete Algorithms, pp. 805---813, 2007b, Bansal et al. in Proceedings of International Colloquium on Automata, Languages and Programming, pp. 409---420, 2008; Lam et al. in Proceedings of European Symposium on Algorithms, pp. 647---659, 2008b) in the multi-processor setting. Our main result is an enhanced analysis of a simple non-migratory online algorithm called CRR (classified round robin) on m?2 processors, showing that its flow time plus energy is within O(1) times of the optimal non-migratory offline algorithm, when the maximum allowable speed is slightly relaxed. The result still holds even if the comparison is made against the optimal migratory offline algorithm. This improves previous analysis that CRR is O(log?P)-competitive where P is the ratio of the maximum job size to the minimum job size.

This paper is concerned with online scheduling algorithms that aim at minimizing the total flow time plus energy usage. The results are divided into two parts. First, we consider the well-studied "simple" speed scaling model and show how to analyze a speed scaling algorithm (called AJC) that changes speed discretely. This is in contrast to the previous algorithms which change the speed continuously. More interestingly, AJC admits a better competitive ratio, and without using extra speed. In the second part, we extend the study to a more general speed scaling model where the processor can enter a sleep state to further save energy. A new sleep management algorithm called IdleLonger is presented. This algorithm, when coupled with AJC, gives the first competitive algorithm for minimizing total flow time plus energy in the general model.

AbstractIn this paper we consider online deadline scheduling on a processor that can manage its energy usage by scaling the speed dynamically or entering a sleep state. A new online scheduling algorithm called SOA is presented. Assuming speed can be scaled arbitrarily high (the infinite speed model), SOA can complete all jobs with reduced energy usage, improving the competitive ratio for energy from 22α−2αα+2α−1+2 (Irani et al. (2007) [17]) to αα+2, where α is the constant involved in the speed-to-power function, commonly believed to be 2 or 3. More importantly, SOA is the first algorithm that works well even if the processor has a fixed maximum speed and the system is overloaded. In this case, SOA is 4-competitive for throughput and (αα+α24α+2)-competitive for energy. Note that the throughput ratio cannot be better than 4 even if energy is not a concern.

In this paper we study the Minimum Range Assignment problem in static ad-hoc networks with arbitrary structure, where the transmission distances can violate triangle inequality. We consider two versions of the Minimum Range Assignment problem, where the communication graph has to fulfill either the h-strong connectivity condition (Min-Range(h-SC)) or the h-broadcast condition (Min-Range(h-B)). Both homogeneous and non-homogeneous cases are studied. By approximating arbitrary edge-weighted graphs by paths, we present probabilistic O(log n)-approximation algorithms for Min-Range(h-SC) and Min-Range(h-B), which improves the previous best ratios O(log n loglog n) and O(n2log n loglog n), respectively [21]. The result for Min-Range(h-B) matches the lower bound [20] for the case that triangle inequality for transmission distance holds (which is a special case of our model). Furthermore, we show that if the network fulfils certain property and the distance power gradient α is sufficiently small, the approximation ratio is improved to O((loglog n)α).