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 algorithmmakespanprecedence constraintsschedulinguniform machinesworst-case analysis

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Deterministic scheduling theory in operations research (90B35) Approximation methods and heuristics in mathematical programming (90C59) 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

• Approximation algorithms for scheduling unrelated parallel machines
• Bounds for LPT Schedules on Uniform Processors
• 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?)
• Scheduling Parallel Machines On-Line

Cited in

(21)

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

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)