A best on-line algorithm for single machine scheduling with small delivery times

DOI10.1016/j.tcs.2007.11.006zbMath1136.68017MaRDI QIDQ2481972

Ji Tian, Jinjiang Yuan, Ruyan Fu

Publication date: 15 April 2008

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2007.11.006

zbMATH Keywords

scheduling; single machine; on-line algorithm; delivery time

Mathematics Subject Classification ID

68W05: Nonnumerical algorithms

68M20: Performance evaluation, queueing, and scheduling in the context of computer systems

Related Items

Optimal algorithms for online single machine scheduling with deteriorating jobs, An optimal online algorithm for single machine scheduling with bounded delivery times, Single-machine online scheduling of jobs with non-delayed processing constraint, An improved semi-online algorithm for scheduling on a single machine with unexpected breakdown, Online scheduling on two parallel machines with release dates and delivery times, Online NDP-constraint scheduling of jobs with delivery times or weights, Online Scheduling on Two Parallel Machines with Release Times and Delivery Times

Cites Work

• Unnamed Item
• Efficient approximation schemes for scheduling problems with release dates and delivery times
• PERFORMANCE ANALYSIS OF SIX APPROXIMATION ALGORITHMS FOR THE ONE-MACHINE MAXIMUM LATENESS SCHEDULING PROBLEM WITH READY TIMES
• Technical Note—Analysis of a Heuristic for One Machine Sequencing with Release Dates and Delivery Times
• Jackson's Rule for Single-Machine Scheduling: Making a Good Heuristic Better
• A Best Possible Deterministic On-Line Algorithm for Minimizing Maximum Delivery Time on a Single Machine