We consider Lagrangian duality based approaches to design and analyze algorithms for online energy-efficient scheduling. First, we present a primal-dual framework. Our approach makes use of the Lagrangian weak duality and convexity to derive dual programs for problems which could be formulated as convex assignment problems. The duals have intuitive structures as the ones in linear programming. The constraints of the duals explicitly indicate the online decisions and naturally lead to competitive algorithms. Second, we use a dual-fitting approach, which also based on the weak duality, to study problems which are unlikely to admit convex relaxations. Through the analysis, we show an interesting feature in which primal-dual gives idea for designing algorithms while the analysis is done by dual-fitting. We illustrate the advantages and the flexibility of the approaches through problems in different setting: from single machine to unrelated machine environments, from typical competitive analysis to the one with resource augmentation, from convex relaxations to non-convex relaxations.
was the first who proposed studying online scheduling by linear (convex) programming and dual fitting. By this approach, they gave simple algorithms and simple analyses with improved performance for problems where the analyses based on potential functions are complex or it is unclear how to design such functions. Subsequently, Nguyen @cite_6 generalized the approach in @cite_1 and proposed to study online scheduling by non-convex programming and the weak Lagrangian duality. Using that technique, @cite_6 derive competitive algorithms for problems related to weighted flow-time.
@cite_1 @cite_6
165387623 435588996
We propose a general dual-fitting technique for analyzing online scheduling algorithms in the unrelated machines setting where the objective function involves weighted flow-time, and we allow the machines of the on-line algorithm to have (1 + e)-extra speed than the offline optimum (the so-called speed augmentation model). Typically, such algorithms are analyzed using non-trivial potential functions which yield little insight into the proof technique. We propose that one can often analyze such algorithms by looking at the dual (or Lagrangian dual) of the linear (or convex) program for the corresponding scheduling problem, and finding a feasible dual solution as the on-line algorithm proceeds. As representative cases, we get the following results: • For the problem of minimizing weighted flow-time, we give an O (1 e)-competitive greedy algorithm. This is an improvement by a factor of 1 e on the competitive ratio of the greedy algorithm of Chadha-Garg-Kumar-Muralidhara. • For the problem of minimizing weighted lk norm of flow-time, we show that a greedy algorithm gives an O (1 e)-competitive ratio. This marginally improves the result of Im and Moseley. • For the problem of minimizing weighted flow-time plus energy, and when the energy function f(s) is equal to sγ, γ > 1, we show that a natural greedy algorithm is O(γ2)-competitive. Prior to our work, such a result was known for the related machines setting only (Gupta-Krishnaswamy-Pruhs). We present an unified approach to study online scheduling problems in the resource augmentation speed scaling models. Potential function method is extensively used for analyzing algorithms in these models; however, they yields little insight on how to construct potential functions and how to design algorithms for related problems. In the paper, we generalize and strengthen the dual-fitting technique proposed by [1]. The approach consists of considering a possibly non-convex relaxation and its Lagrangian dual; then constructing dual variables such that the Lagrangian dual has objective value within a desired factor of the primal optimum. The competitive ratio follows by the standard Lagrangian weak duality. This approach is simple yet powerful and it is seemingly a right tool to study problems with resource augmentation or speed scaling. We illustrate the approach through the following results. 1 We revisit algorithms EQUI and LAPS in Non-clairvoyant Scheduling to minimize total flow-time. We give simple analyses to prove known facts on the competitiveness of such algorithms. Not only are the analyses much simpler than the previous ones, they also explain why LAPS is a natural extension of EQUI to design a scalable algorithm for the problem. 2 We consider the online scheduling problem to minimize total weighted flow-time plus energy where the energy power f(s) is a function of speed s and is given by s α for α ≥ 1. For a single machine, we showed an improved competitive ratio for a non-clairvoyant memoryless algorithm. For unrelated machines, we give an O(α logα)-competitive algorithm. The currently best algorithm for unrelated machines is O(α 2)-competitive. 3 We consider the online scheduling problem on unrelated machines with the objective of minimizing ∑ i,j w ij f(F j ) where F j is the flow-time of job j and f is an arbitrary non-decreasing cost function with some nice properties. We present an algorithm which is ( 1 1-3 )-speed, ( 2K( ) )-competitive where K(e) is a function depending on f and e. The algorithm does not need to know the speed (1 + e) a priori. A corollary is a (1 + e)-speed, ( k ^ 1+1 k )-competitive algorithm (which does not know e a priori) for the objective of minimizing the weighted l k -norm of flow-time.