A best possible online algorithm for scheduling equal-length jobs on two machines with chain precedence constraints
DOI10.1016/J.TCS.2012.07.009zbMath1252.68052OpenAlexW1998658360MaRDI QIDQ714856
Wenhua Li, Junling Yuan, 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
competitive ratioonline algorithmparallel-machine schedulingequal-length jobschain precedence constraints
Deterministic scheduling theory in operations research (90B35) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Online algorithms; streaming algorithms (68W27)
Related Items (1)
Cites Work
- Unnamed Item
- Scheduling a batch-processing machine subject to precedence constraints, release dates and identical processing times
- Online scheduling of equal-processing-time task systems
- Online scheduling on unbounded parallel-batch machines to minimize the makespan
- Scheduling three chains on two parallel machines
- Scheduling on identical machines: How good is LPT in an on-line setting?
- Scheduling chain-structured tasks to minimize makespan and mean flow time
- Scheduling identical jobs with chain precedence constraints on two uniform machines
- A best possible deterministic on-line algorithm for minimizing makespan on parallel batch machines
- Optimal scheduling for two-processor systems
- Online Scheduling of Precedence Constrained Tasks
- An optimal online algorithm for scheduling two machines with release times
This page was built for publication: A best possible online algorithm for scheduling equal-length jobs on two machines with chain precedence constraints