Document Open Access Logo

Online Non-Preemptive Scheduling in a Resource Augmentation Model Based on Duality

Authors Giorgio Lucarelli, Nguyen Kim Thang, Abhinav Srivastav, Denis Trystram

PDF
Thumbnail PDF

File

LIPIcs.ESA.2016.63.pdf
  • Filesize: 478 kB
  • 17 pages

Document Identifiers

Author Details

Giorgio Lucarelli
Nguyen Kim Thang
Abhinav Srivastav
Denis Trystram

Cite As Get BibTex

Giorgio Lucarelli, Nguyen Kim Thang, Abhinav Srivastav, and Denis Trystram. Online Non-Preemptive Scheduling in a Resource Augmentation Model Based on Duality. In 24th Annual European Symposium on Algorithms (ESA 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 57, pp. 63:1-63:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016) https://doi.org/10.4230/LIPIcs.ESA.2016.63

Abstract

Resource augmentation is a well-established model for analyzing algorithms, particularly in the online setting. It has been successfully used for providing theoretical evidence for several heuristics in scheduling with good performance in practice. According to this model, the algorithm is applied to a more powerful environment than that of the adversary. Several types of resource augmentation for scheduling problems have been proposed up to now, including speed augmentation, machine augmentation and more recently rejection. In this paper, we present a framework that unifies the various types of resource augmentation. Moreover, it allows generalize the notion of resource augmentation for other types of resources. Our framework is based on mathematical programming and it consists of extending the domain of feasible solutions for the algorithm with respect to the domain of the adversary. This, in turn allows the natural concept of duality for mathematical programming to be used as a tool for the analysis of the algorithm's performance. As an illustration of the above ideas, we apply this framework and we propose a primal-dual algorithm for the online scheduling problem of minimizing the total weighted flow time of jobs on unrelated machines when the preemption of jobs is not allowed. This is a well representative problem for which no online algorithm with performance guarantee is known. Specifically, a strong lower bound of Omega(sqrt{n}) exists even for the offline unweighted version of the problem on a single machine. In this paper, we first show a strong negative result even when speed augmentation is used in the online setting. Then, using the generalized framework for resource augmentation and by combining speed augmentation and rejection, we present an (1+epsilon_s)-speed O(1/(epsilon_s epsilon_r))-competitive algorithm if we are allowed to reject jobs whose total weight is an epsilon_r-fraction of the weights of all jobs, for any epsilon_s > 0 and epsilon_r in (0,1). Furthermore, we extend the idea for analysis of the above problem and we propose an (1+\epsilon_s)-speed epsilon_r-rejection O({k^{(k+3)/k}}/{epsilon_{r}^{1/k}*epsilon_{s}^{(k+2)/k}})-competitive algorithm for the more general objective of minimizing the weighted l_k-norm of the flow times of jobs.

Subject Classification

Keywords
  • Online algorithms
  • Non-preemptive scheduling
  • Resource augmentation
  • Primal-dual

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Susanne Albers, Lene M. Favrholdt, and Oliver Giel. On paging with locality of reference. J. Comput. Syst. Sci., 70(2):145-175, 2005. Google Scholar
  2. S. Anand, Naveen Garg, and Amit Kumar. Resource augmentation for weighted flow-time explained by dual fitting. In Symposium on Discrete Algorithms, pages 1228-1241, 2012. Google Scholar
  3. Spyros Angelopoulos, Reza Dorrigiv, and Alejandro López-Ortiz. On the separation and equivalence of paging strategies. In Proc. Symposium on Discrete Algorithms, pages 229-237, 2007. Google Scholar
  4. Nikhil Bansal, Ho-Leung Chan, Rohit Khandekar, Kirk Pruhs, B Schicber, and Cliff Stein. Non-preemptive min-sum scheduling with resource augmentation. In Proc. 48th Symposium on Foundations of Computer Science, pages 614-624, 2007. Google Scholar
  5. Allan Borodin, Sandy Irani, Prabhakar Raghavan, and Baruch Schieber. Competitive paging with locality of reference. J. Comput. Syst. Sci., 50(2):244-258, 1995. Google Scholar
  6. Niv Buchbinder and Joseph Naor. The design of competitive online algorithms via a primal-dual approach. Foundations and Trends in Theoretical Computer Science, 3(2-3):93-263, 2009. Google Scholar
  7. Chandra Chekuri, Sanjeev Khanna, and An Zhu. Algorithms for minimizing weighted flow time. In Proceedings of the thirty-third annual ACM symposium on Theory of computing, pages 84-93, 2001. Google Scholar
  8. Anamitra Roy Choudhury, Syamantak Das, Naveen Garg, and Amit Kumar. Rejecting jobs to minimize load and maximum flow-time. In Proc. Symposium on Discrete Algorithms, pages 1114-1133, 2015. Google Scholar
  9. Anamitra Roy Choudhury, Syamantak Das, and Amit Kumar. Minimizing weighted 𝓁_p-norm of flow-time in the rejection model. In Proc. 35th Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2015), volume 45, pages 25-37, 2015. Google Scholar
  10. Peter J. Denning. The working set model for program behavior. Commun. ACM, 11(5):323-333, 1968. Google Scholar
  11. Nikhil R. Devanur and Zhiyi Huang. Primal dual gives almost optimal energy efficient online algorithms. In Proc. 25th ACM-SIAM Symposium on Discrete Algorithms, 2014. Google Scholar
  12. Stefan Dobrev, Rastislav Kralovic, and Dana Pardubská. How much information about the future is needed? In Proc. 34th Conference on Current Trends in Theory and Practice of Computer Science, pages 247-258, 2008. Google Scholar
  13. Yuval Emek, Pierre Fraigniaud, Amos Korman, and Adi Rosén. Online computation with advice. Theor. Comput. Sci., 412(24):2642-2656, 2011. Google Scholar
  14. Leah Epstein and Rob van Stee. Optimal on-line flow time with resource augmentation. Discrete Applied Mathematics, 154(4):611-621, 2006. Google Scholar
  15. Anupam Gupta, Ravishankar Krishnaswamy, and Kirk Pruhs. Online primal-dual for non-linear optimization with applications to speed scaling. In Proc. 10th Workshop on Approximation and Online Algorithms, pages 173-186, 2012. Google Scholar
  16. Sungjin Im, Janardhan Kulkarni, and Kamesh Munagala. Competitive algorithms from competitive equilibria: Non-clairvoyant scheduling under polyhedral constraints. In STOC, 2014. Google Scholar
  17. Sungjin Im, Janardhan Kulkarni, and Kamesh Munagala. Competitive flow time algorithms for polyhedral scheduling. In Proc. 56th Symposium on Foundations of Computer Science, pages 506-524, 2015. Google Scholar
  18. Sungjin Im, Janardhan Kulkarni, Kamesh Munagala, and Kirk Pruhs. Selfishmigrate: A scalable algorithm for non-clairvoyantly scheduling heterogeneous processors. In Proc. 55th Symposium on Foundations of Computer Science, 2014. Google Scholar
  19. Sungjin Im, Shi Li, Benjamin Moseley, and Eric Torng. A dynamic programming framework for non-preemptive scheduling problems on multiple machines [extended abstract]. In Proc. 26th ACM-SIAM Symposium on Discrete Algorithms, pages 1070-1086, 2015. Google Scholar
  20. Bala Kalyanasundaram and Kirk Pruhs. Speed is as powerful as clairvoyance. J. ACM, 47(4):617-643, 2000. Google Scholar
  21. Hans Kellerer, Thomas Tautenhahn, and Gerhard J. Woeginger. Approximability and nonapproximability results for minimizing total flow time on a single machine. SIAM J. Comput., 28(4):1155-1166, 1999. Google Scholar
  22. Elias Koutsoupias and Christos H. Papadimitriou. Beyond competitive analysis. SIAM J. Comput., 30(1):300-317, 2000. Google Scholar
  23. Benjamin Moseley, Kirk Pruhs, and Cliff Stein. The complexity of scheduling for p-norms of flow and stretch - (extended abstract). In Proc. Integer Programming and Combinatorial Optimization, pages 278-289, 2013. Google Scholar
  24. Cynthia A Phillips, Clifford Stein, Eric Torng, and Joel Wein. Optimal time-critical scheduling via resource augmentation. Algorithmica, 32(2):163-200, 2002. Google Scholar
  25. Prabhakar Raghavan. A statistical adversary for on-line algorithms. DIMACS Series in Discrete Mathematics and Theoretical Computer Science, 7:79-83, 1992. Google Scholar
  26. Nguyen Kim Thang. Lagrangian duality in online scheduling with resource augmentation and speed scaling. In Proc. 21st European Symposium on Algorithms, pages 755-766, 2013. Google Scholar
  27. David P Williamson and David B Shmoys. The design of approximation algorithms. Cambridge University Press, 2011. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact