A best online algorithm for scheduling on two parallel batch machines

DOI10.1016/J.TCS.2009.02.011MaRDI QIDQ1019748zbMATH OpenOpenAlexFDO

Authors Ji Tian, Ruyan Fu, 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)

Recommendations

• An improved on-line algorithm for scheduling on two unrestrictive parallel batch processing machines
• A best possible deterministic on-line algorithm for minimizing makespan on parallel batch machines
• A note on an on-line algorithm for the parallel-batching scheduling to minimize makespan
• On-line scheduling on an unbounded parallel batch machine to minimize makespan of two families of jobs
• A best possible on-line algorithm for scheduling on uniform parallel-batch machines

Cites work

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

Cited in

(21)

• A best possible online algorithm for scheduling to minimize maximum flow-time on bounded batch machines
• A flexible on-line scheduling algorithm for batch machine with infinite capacity
• An improved on-line algorithm for scheduling on two unrestrictive parallel batch processing machines
• An algorithm for on-line batch scheduling with nonidentical job sizes
• Online scheduling on unbounded parallel-batch machines to minimize maximum flow-time
• Best semi-online algorithms for unbounded parallel batch scheduling
• An optimal online algorithm for scheduling two machines with release times
• Online scheduling of equal length jobs on unbounded parallel batch processing machines with limited restart
• Online scheduling on unbounded parallel-batch machines to minimize the makespan
• A 2-competitive largest job on least loaded machine online algorithm based on the multi list scheduling model
• Online algorithms for scheduling unit length jobs on parallel-batch machines with lookahead
• A best possible deterministic on-line algorithm for minimizing makespan on parallel batch machines
• A note on an on-line algorithm for the parallel-batching scheduling to minimize makespan
• On-line scheduling on partial batch parallel machines with chains precedence constraints
• A best possible on-line algorithm for scheduling on uniform parallel-batch machines
• On-line batch scheduling with real time on two parallel machines
• On-line scheduling on a batch processing machine with unbounded batch size to minimize the makespan
• Online over time scheduling on parallel-batch machines: a survey
• A best possible on-line algorithm for two-machine flow shop scheduling to minimize makespan
• Optimal semi-online algorithm for scheduling on two parallel batch processing machines
• Online scheduling on two uniform unbounded parallel-batch machines to minimize makespan

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

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