A comment on scheduling on uniform machines under chain-type precedence constraints

DOI10.1016/S0167-6377(99)00076-0MaRDI QIDQ1977643zbMATH OpenOpenAlexFDO

Authors Gerhard J. Woeginger

Publication date 5 March 2001

Published in Operations Research Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/s0167-6377(99)00076-0

zbMATH Keywords

approximation algorithmschedulingmakespanworst-case analysisprecedence constraintsuniform machines

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59) Analysis of algorithms and problem complexity (68Q25) Deterministic scheduling theory in operations research (90B35) Abstract computational complexity for mathematical programming problems (90C60)

Recommendations

• A new approximation algorithm for UET-scheduling with chain-type precedence constraints.
• Scheduling identical jobs with chain precedence constraints on two uniform machines
• Parallel Processing and Applied Mathematics
• scientific article; zbMATH DE number 1187166

Cites work

• scientific article; zbMATH DE number 1187166 (Why is no real title available?)
• scientific article; zbMATH DE number 44978 (Why is no real title available?)
• scientific article; zbMATH DE number 6472635 (Why is no real title available?)
• Approximation algorithms for scheduling unrelated parallel machines
• Bounds for LPT Schedules on Uniform Processors
• Scheduling Parallel Machines On-Line

Cited in

(17)

• Parametric analysis of the quality of single preemption schedules on three uniform parallel machines
• scientific article; zbMATH DE number 5669900 (Why is no real title available?)
• A new approximation algorithm for UET-scheduling with chain-type precedence constraints.
• Optimal preemptive on-line scheduling on uniform processors with non-decreasing speed ratios
• The benefit of preemption for single machine scheduling so as to minimize total weighted completion time
• Approximation schemes for scheduling jobs with chain precedence constraints
• Preemptive and non-preemptive scheduling on two unrelated parallel machines
• Parallel machine covering with limited number of preemptions
• Schedules with a single preemption on uniform parallel machines
• Randomized on-line scheduling on two uniform machines
• Optimal and online preemptive scheduling on uniformly related machines
• Non-identical parallel-machine scheduling research with minimizing total weighted completion times: models, relaxations and algorithms
• Scheduling of uniform parallel machines with s-precedence constraints
• The benefit of preemption with respect to the \(\ell_p\) norm
• Power of preemption for minimizing total completion time on uniform parallel machines
• Algorithms with limited number of preemptions for scheduling on parallel machines
• scientific article; zbMATH DE number 7764095 (Why is no real title available?)

This page was built for publication: A comment on scheduling on uniform machines under chain-type precedence constraints

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