An optimal online algorithm for single machine scheduling with bounded delivery times

DOI10.1016/j.ejor.2009.03.028zbMath1177.90173WikidataQ57185721 ScholiaQ57185721MaRDI QIDQ1038322

Chengbin Chu, Ming Liu, Feifeng Zheng, Yin-Feng Xu

Publication date: 17 November 2009

Published in: European Journal of Operational Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ejor.2009.03.028

zbMATH Keywords

single machine; competitive analysis; online scheduling; delivery times

Mathematics Subject Classification ID

90B35: Deterministic scheduling theory in operations research

Related Items

Integrated Scheduling of Production and Two-Stage Delivery of Make-to-Order Products: Offline and Online Algorithms, Competitive analysis of the online financial lease problem, Online scheduling on a single machine with grouped processing times, Single-machine online scheduling of jobs with non-delayed processing constraint, Online economic ordering problem for deteriorating items with limited price information, 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

• A best on-line algorithm for single machine scheduling with small delivery times
• PERFORMANCE ANALYSIS OF SIX APPROXIMATION ALGORITHMS FOR THE ONE-MACHINE MAXIMUM LATENESS SCHEDULING PROBLEM WITH READY TIMES
• A Best Possible Deterministic On-Line Algorithm for Minimizing Maximum Delivery Time on a Single Machine
• Unnamed Item
• Unnamed Item
• Unnamed Item