Completion time scheduling and the WSRPT algorithm

DOI10.1007/978-3-642-32147-4_37MaRDI QIDQ3167644zbMATH OpenOpenAlexFDO

Authors Bo Xiong, Christine Chung

Publication date 2 November 2012

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://digitalcommons.conncoll.edu/comscifacpub/9

Mathematics Subject Classification ID

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

Recommendations

• Online Scheduling of a Single Machine to Minimize Total Weighted Completion Time
• Efficient algorithms for average completion time scheduling
• scientific article; zbMATH DE number 2119710
• SRPT is 1.86-competitive for completion time scheduling
• Online scheduling on \(m\) uniform machines to minimize total (weighted) completion time

Cited in

(9)

• The expected competitive ratio for weighted completion time scheduling
• Online heuristic for the preemptive single machine scheduling problem of minimizing the total weighted completion time
• Efficient algorithms for average completion time scheduling
• scientific article; zbMATH DE number 4027157 (Why is no real title available?)
• Online parallel-machine scheduling in KRT environment to minimize total weighted completion time
• A tight 2-approximation for preemptive stochastic scheduling
• STACS 2004
• SRPT is 1.86-competitive for completion time scheduling
• Competitive kill-and-restart and preemptive strategies for non-clairvoyant scheduling

This page was built for publication: Completion time scheduling and the WSRPT algorithm

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