Online Non-preemptive Scheduling in a Resource Augmentation Model based on Duality

DOI10.4230/LIPICS.ESA.2016.63MaRDI QIDQ4606335zbMATH OpenOpenAlexFDO

Authors G. Lucarelli, Nguyen Kim Thang, Abhinav Srivastav, Denis Trystram

Publication date 2 March 2018

Full work available at URL https://hal.univ-grenoble-alpes.fr/hal-01334219

zbMATH Keywords

non-preemptive schedulingonline algorithmsprimal-dualresource augmentation

Mathematics Subject Classification ID

Online algorithms; streaming algorithms (68W27) Deterministic scheduling theory in operations research (90B35)

Recommendations

• Lagrangian duality in online scheduling with resource augmentation and speed scaling
• Online scheduling on multiple resources under stochastic conditions
• Optimal non-preemptive semi-online scheduling on two related machines
• scientific article; zbMATH DE number 1929942
• Online non-preemptive scheduling to optimize max stretch on a single machine
• Optimal preemptive semi-online scheduling on two uniform processors
• An optimal algorithm for preemptive on-line scheduling
• Nonmigratory Online Deadline Scheduling on Multiprocessors
• Optimal preemptive online scheduling to minimize \(l_p\) norm on two processors
• Semi-online preemptive scheduling: study of special cases

Cited in

(15)

• Competitive analysis of online machine rental and online parallel machine scheduling problems with workload fence
• Lagrangian duality in online scheduling with resource augmentation and speed scaling
• Dual representation and its online scheduling method for event-varying DESs with capacity constraints
• Simple paths with exact and forbidden lengths
• Non-preemptive flow-time minimization via rejections
• Online Non-Preemptive Scheduling to Minimize Weighted Flow-time on Unrelated Machines
• An Optimal Control Framework for Online Job Scheduling with General Cost Functions
• Game efficiency through linear programming duality
• A dynamic programming framework for non-preemptive scheduling problems on multiple machines
• Resource augmentation for weighted flow-time explained by dual fitting
• Approximating \(k\)-forest with resource augmentation: a primal-dual approach
• An on-line \textit{seru} scheduling algorithm with proactive waiting considering resource conflicts
• Minimizing the maximum flow time in the online food delivery problem
• A best possible online algorithm for minimizing the total completion time and the total soft penalty cost
• Two-Agent Scheduling with Resource Augmentation on Multiple Machines

This page was built for publication: Online Non-preemptive Scheduling in a Resource Augmentation Model based on Duality

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4606335)