An optimal online algorithm for scheduling two machines with release times

DOI10.1016/S0304-3975(00)00264-4zbMath0984.68014OpenAlexW2092227404MaRDI QIDQ5958718

Steve Seiden, John Noga

Publication date: 3 March 2002

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0304-3975(00)00264-4

zbMATH Keywords

schedulinglower boundscompetitive online algorithms

Mathematics Subject Classification ID

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

Related Items (20)

A best possible on-line algorithm for scheduling on uniform parallel-batch machines ⋮ On-line scheduling on parallel machines to minimize the makespan ⋮ Online algorithms for scheduling with machine activation cost on two uniform machines ⋮ Well-behaved online load balancing against strategic jobs ⋮ Online scheduling on two parallel identical machines under a grade of service provision ⋮ Unnamed Item ⋮ Online scheduling on an unbounded parallel-batch machine and a standard machine to minimize makespan ⋮ Online scheduling on two parallel-batching machines with limited restarts to minimize the makespan ⋮ Makespan minimization in online scheduling with machine eligibility ⋮ Makespan minimization in online scheduling with machine eligibility ⋮ An optimal online algorithm for scheduling on two parallel machines with GoS eligibility constraints ⋮ A best possible online algorithm for scheduling equal-length jobs on two machines with chain precedence constraints ⋮ Online scheduling with chain precedence constraints of equal-length jobs on parallel machines to minimize makespan ⋮ LPT online strategy for parallel-machine scheduling with kind release times ⋮ Multi-Priority Online Scheduling with Cancellations ⋮ A best online algorithm for scheduling on two parallel batch machines ⋮ Online scheduling on two uniform unbounded parallel-batch machines to minimize makespan ⋮ Heuristics for online scheduling on identical parallel machines with two GoS levels ⋮ 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
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A lower bound for randomized on-line multiprocessor scheduling
• New algorithms for an ancient scheduling problem.
• Competitive snoopy caching
• Randomized competitive algorithms for the list update problem
• A better lower bound for on-line scheduling
• A lower bound for randomized on-line scheduling algorithms
• Scheduling on identical machines: How good is LPT in an on-line setting?
• Randomized algorithms for on-line scheduling problems: How low can't you go?
• New lower and upper bounds for on-line scheduling
• An On-Line Scheduling Heuristic with Better Worst-Case Ratio Than Graham’s List Scheduling
• A Better Algorithm for an Ancient Scheduling Problem
• Randomized algorithms for that ancient scheduling problem
• Bounds for Certain Multiprocessing Anomalies

This page was built for publication: An optimal online algorithm for scheduling two machines with release times