Document Open Access Logo

Non-Preemptive Flow-Time Minimization via Rejections

Authors Anupam Gupta, Amit Kumar, Jason Li

PDF

File

Thumbnail PDF
PDF
LIPIcs.ICALP.2018.70.pdf
  • Filesize: 442 kB
  • 13 pages

Document Identifiers

Related Versions

Subject Classification

ACM Subject Classification
  • Theory of computation → Scheduling algorithms
Keywords
  • Scheduling
  • Rejection
  • Unrelated Machines
  • Non-Preemptive

Metrics

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

Abstract

We consider the online problem of minimizing weighted flow-time on unrelated machines. Although much is known about this problem in the resource-augmentation setting, these results assume that jobs can be preempted. We give the first constant-competitive algorithm for the non-preemptive setting in the rejection model. In this rejection model, we are allowed to reject an epsilon-fraction of the total weight of jobs, and compare the resulting flow-time to that of the offline optimum which is required to schedule all jobs. This is arguably the weakest assumption in which such a result is known for weighted flow-time on unrelated machines. While our algorithms are simple, we need a delicate argument to bound the flow-time. Indeed, we use the dual-fitting framework, with considerable more machinery to certify that the cost of our algorithm is within a constant of the optimum while only a small fraction of the jobs are rejected.

Cite As Get BibTex

Anupam Gupta, Amit Kumar, and Jason Li. Non-Preemptive Flow-Time Minimization via Rejections. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 107, pp. 70:1-70:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018) https://doi.org/10.4230/LIPIcs.ICALP.2018.70

Author Details

Anupam Gupta
  • Carnegie Mellon University
Amit Kumar
  • IIT Delhi
Jason Li
  • Carnegie Mellon University

References

  1. S Anand. Algorithms for flow time scheduling. PhD thesis, Indian Institute of Technology, Delhi, 2013. Google Scholar
  2. S. Anand, Naveen Garg, and Amit Kumar. Resource augmentation for weighted flow-time explained by dual fitting. In SODA'12, pages 1228-1241. ACM, New York, 2012. Google Scholar
  3. Nir Avrahami and Yossi Azar. Minimizing total flow time and total completion time with immediate dispatching. In SPAA, pages 11-18, 2003. Google Scholar
  4. Nikhil Bansal, Avrim Blum, Shuchi Chawla, and Kedar Dhamdhere. Scheduling for flow-time with admission control. In Proc. ESA, 2003, pages 43-54. Springer, 2003. Google Scholar
  5. Nikhil Bansal and Ho-Leung Chan. Weighted flow time does not admit o(1)-competitive algorithms. In SODA, pages 1238-1244, 2009. Google Scholar
  6. Yair Bartal, Stefano Leonardi, Alberto Marchetti-Spaccamela, Jiri Sgall, and Leen Stougie. Multiprocessor scheduling with rejection. SIAM J. Discrete Math., 13(1):64-78, 2000. Google Scholar
  7. Jivitej S. Chadha, Naveen Garg, Amit Kumar, and V. N. Muralidhara. A competitive algorithm for minimizing weighted flow time on unrelated machines with speed augmentation. In STOC'09, pages 679-683. ACM, New York, 2009. Google Scholar
  8. Anamitra Roy Choudhury, Syamantak Das, Naveen Garg, and Amit Kumar. Rejecting jobs to minimize load and maximum flow-time. J. Comput. System Sci., 91:42-68, 2018. Google Scholar
  9. Leah Epstein and Hanan Zebedat-Haider. Preemptive online scheduling with rejection of unit jobs on two uniformly related machines. J. Scheduling, 17(1):87-93, 2014. Google Scholar
  10. Naveen Garg and Amit Kumar. Better algorithms for minimizing average flow-time on related machines. In ICALP, volume 4051, pages 181-190, 2006. Google Scholar
  11. Naveen Garg and Amit Kumar. Minimizing average flow-time : Upper and lower bounds. In 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2007), October 20-23, 2007, Providence, RI, USA, Proceedings, pages 603-613, 2007. Google Scholar
  12. Sungjin Im, Janardhan Kulkarni, Kamesh Munagala, and Kirk Pruhs. Selfishmigrate: A scalable algorithm for non-clairvoyantly scheduling heterogeneous processors. In 55th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2014, Philadelphia, PA, USA, October 18-21, 2014, pages 531-540, 2014. Google Scholar
  13. Bala Kalyanasundaram and Kirk Pruhs. Speed is as powerful as clairvoyance. J. ACM, 47(4):617-643, 2000. Google Scholar
  14. 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
  15. Stefano Leonardi and Danny Raz. Approximating total flow time on parallel machines. Journal of Computer and Systems Sciences, 73(6):875-891, 2007. Google Scholar
  16. 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, August 22-24, 2016, Aarhus, Denmark, pages 63:1-63:17, 2016. Google Scholar
  17. Giorgio Lucarelli, Nguyen Kim Thang, Abhinav Srivastav, and Denis Trystram. Online min-sum flow scheduling with rejections. In In 13th Workshop on Models and Algorithms for Planning and Scheduling Problems (MAPSP 2017), 2017, 2017. 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-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact