Online scheduling with chain precedence constraints of equal-length jobs on parallel machines to minimize makespan

DOI10.1007/s10878-018-0309-3zbMath1400.90166MaRDI QIDQ721932

Xing Chai, Wenhua Li

Publication date: 20 July 2018

Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10878-018-0309-3

zbMATH Keywords

competitive ratio; makespan; online algorithm; chain precedence constraints

Mathematics Subject Classification ID

90B35: Deterministic scheduling theory in operations research

Related Items

Competitive analysis of online machine rental and online parallel machine scheduling problems with workload fence

Cites Work

• Scheduling a batch-processing machine subject to precedence constraints, release dates and identical processing times
• A best possible online algorithm for scheduling equal-length jobs on two machines with chain precedence constraints
• Online scheduling of equal-processing-time task systems
• 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
• Optimal scheduling for two-processor systems
• Online Scheduling of Precedence Constrained Tasks
• An optimal online algorithm for scheduling two machines with release times