Efficient algorithms for average completion time scheduling

DOI10.1007/978-3-642-13036-6_31MaRDI QIDQ3569835zbMATH OpenOpenAlexFDO

Authors René A. Sitters

Publication date 22 June 2010

Published in Integer Programming and Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL http://degree.ubvu.vu.nl/repec/vua/wpaper/pdf/20090058.pdf

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Deterministic scheduling theory in operations research (90B35)

Recommendations

• Approximation and Online Algorithms
• On-line scheduling to minimize average completion time revisited.
• Completion time scheduling and the WSRPT algorithm
• SRPT is 1.86-competitive for completion time scheduling
• Scheduling jobs that arrive over time

Cited in

(16)

• Approximation and Online Algorithms
• STACS 2004
• A new average case analysis for completion time scheduling
• A tight 2-approximation for preemptive stochastic scheduling
• Completion time scheduling and the WSRPT algorithm
• An improved analysis of SRPT scheduling algorithm on the basis of functional optimization
• Scheduling jobs that arrive over time
• Competitive analysis of preemptive single-machine scheduling
• A better online algorithm for the parallel machine scheduling to minimize the total weighted completion time
• A \(2.28\)-competitive algorithm for online scheduling on identical machines
• On-line scheduling to minimize average completion time revisited.
• Integrated Scheduling of Production and Two-Stage Delivery of Make-to-Order Products: Offline and Online Algorithms
• SRPT is 1.86-competitive for completion time scheduling
• Randomized selection algorithm for online stochastic unrelated machines scheduling
• An improved 2.11-competitive algorithm for online scheduling on parallel machines to minimize total weighted completion time
• Online parallel-machine scheduling in KRT environment to minimize total weighted completion time

This page was built for publication: Efficient algorithms for average completion time scheduling

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