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

DOI10.1007/s10878-018-0309-3zbMath1400.90166OpenAlexW2803566534WikidataQ129815539 ScholiaQ129815539MaRDI 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 ratiomakespanonline algorithmchain precedence constraints

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35)

Related Items (1)

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

This page was built for publication: Online scheduling with chain precedence constraints of equal-length jobs on parallel machines to minimize makespan