A best possible online algorithm for scheduling equal-length jobs on two machines with chain precedence constraints
DOI10.1016/J.TCS.2012.07.009zbMATH Open1252.68052OpenAlexW1998658360MaRDI QIDQ714856FDOQ714856
Authors: Junling Yuan, Wenhua Li, Jinjiang Yuan 
Publication date: 11 October 2012
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2012.07.009
Recommendations
- Online scheduling with chain precedence constraints of equal-length jobs on parallel machines to minimize makespan
- On-line scheduling on partial batch parallel machines with chains precedence constraints
- Online scheduling of equal-processing-time task systems
- A note on on-line scheduling with precedence constraints on identical machines
- On-line scheduling with precedence constraints
competitive ratioonline algorithmparallel-machine schedulingequal-length jobschain precedence constraints
Online algorithms; streaming algorithms (68W27) Deterministic scheduling theory in operations research (90B35) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20)
Cites Work
- Online scheduling of equal-processing-time task systems
- Title not available (Why is that?)
- A best possible deterministic on-line algorithm for minimizing makespan on parallel batch machines
- Online scheduling on unbounded parallel-batch machines to minimize the makespan
- Optimal scheduling for two-processor systems
- Scheduling chain-structured tasks to minimize makespan and mean flow time
- Scheduling a batch-processing machine subject to precedence constraints, release dates and identical processing times
- Scheduling on identical machines: How good is LPT in an on-line setting?
- An optimal online algorithm for scheduling two machines with release times
- Scheduling three chains on two parallel machines
- Scheduling identical jobs with chain precedence constraints on two uniform machines
- Online Scheduling of Precedence Constrained Tasks
Cited In (3)
- On-line scheduling on partial batch parallel machines with chains precedence constraints
- Online scheduling with chain precedence constraints of equal-length jobs on parallel machines to minimize makespan
- A 2-competitive largest job on least loaded machine online algorithm based on the multi list scheduling model
This page was built for publication: A best possible online algorithm for scheduling equal-length jobs on two machines with chain precedence constraints
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q714856)
