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 (9)

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

• 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

This page was built for publication: An optimal online algorithm for single machine scheduling with bounded delivery times