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

DOI10.1016/j.tcs.2007.11.006zbMath1136.68017OpenAlexW2005453958MaRDI 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

schedulingsingle machineon-line algorithmdelivery time

Mathematics Subject Classification ID

Nonnumerical algorithms (68W05) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20)

Related Items

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