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

DOI10.1016/j.ejor.2009.03.028zbMath1177.90173OpenAlexW2077224639WikidataQ57185721 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 machinecompetitive analysisonline schedulingdelivery times

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35)

Related Items

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