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

DOI10.1016/J.TCS.2007.11.006MaRDI QIDQ2481972zbMATH OpenOpenAlexFDO

Authors Ji Tian, Ruyan Fu, Jinjiang Yuan

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 machinedelivery timeon-line algorithm

Mathematics Subject Classification ID

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

Recommendations

• A best on-line algorithm for the single machine parallel-batch scheduling with restricted delivery times
• A Best Possible Deterministic On-Line Algorithm for Minimizing Maximum Delivery Time on a Single Machine
• An optimal online algorithm for single machine scheduling with bounded delivery times
• Online algorithms for batch machines scheduling with delivery times
• An improved on-line algorithm for single parallel-batch machine scheduling with delivery times

Cites work

• scientific article; zbMATH DE number 44978 (Why is no real title available?)
• A Best Possible Deterministic On-Line Algorithm for Minimizing Maximum Delivery Time on a Single Machine
• Efficient approximation schemes for scheduling problems with release dates and delivery times
• Jackson's Rule for Single-Machine Scheduling: Making a Good Heuristic Better
• 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

Cited in

(12)

• Single-machine online scheduling of jobs with non-delayed processing constraint
• A Best Possible Deterministic On-Line Algorithm for Minimizing Maximum Delivery Time on a Single Machine
• Optimal algorithms for online single machine scheduling with deteriorating jobs
• On-line supply chain scheduling for single-machine and parallel-machine configurations with a single customer: minimizing the makespan and delivery cost
• On-line integrated production and outbound distribution scheduling to minimize the maximum delivery completion time
• A best possible online algorithm for minimizing the total completion time and the total soft penalty cost
• Online scheduling on two parallel machines with release times and delivery times
• A best on-line algorithm for the single machine parallel-batch scheduling with restricted delivery times
• An optimal online algorithm for single machine scheduling with bounded delivery times
• 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 two parallel machines with release dates and delivery times

This page was built for publication: A best on-line algorithm for single machine scheduling with small delivery times

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2481972)