A best online algorithm for scheduling on two parallel batch machines

DOI10.1016/j.tcs.2009.02.011zbMath1166.90341OpenAlexW2087683329MaRDI QIDQ1019748

Ruyan Fu, Ji Tian, Jinjiang Yuan

Publication date: 28 May 2009

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

Full work available at URL: https://doi.org/10.1016/j.tcs.2009.02.011

zbMATH Keywords

competitive ratioonline schedulingparallel batch machines

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Deterministic scheduling theory in operations research (90B35)

Related Items (9)

Online scheduling of equal length jobs on unbounded parallel batch processing machines with limited restart ⋮ A best possible on-line algorithm for scheduling on uniform parallel-batch machines ⋮ Optimal Semi-Online Algorithm for Scheduling on Two Parallel Batch Processing Machines ⋮ Online algorithms for scheduling unit length jobs on parallel-batch machines with lookahead ⋮ Online scheduling on unbounded parallel-batch machines to minimize maximum flow-time ⋮ A best possible deterministic on-line algorithm for minimizing makespan on parallel batch machines ⋮ Online over time scheduling on parallel-batch machines: a survey ⋮ Online scheduling on unbounded parallel-batch machines to minimize the makespan ⋮ Online scheduling on two uniform unbounded parallel-batch machines to minimize makespan

Cites Work

• An improved on-line algorithm for scheduling on two unrestrictive parallel batch processing machines
• Scheduling on identical machines: How good is LPT in an on-line setting?
• A flexible on-line scheduling algorithm for batch machine with infinite capacity
• MINIMIZING TOTAL WEIGHTED COMPLETION TIME ON IDENTICAL PARALLEL BATCH MACHINES
• An optimal online algorithm for scheduling two machines with release times

This page was built for publication: A best online algorithm for scheduling on two parallel batch machines