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

DOI10.1016/S0167-6377(99)00076-0zbMATH Open0955.90036OpenAlexW2117694648MaRDI QIDQ1977643FDOQ1977643

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

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

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)

Cites Work

• Scheduling Parallel Machines On-Line
• Title not available (Why is that?)
• Approximation algorithms for scheduling unrelated parallel machines
• Bounds for LPT Schedules on Uniform Processors
• Title not available (Why is that?)
• Title not available (Why is that?)

Cited In (17)

• Parametric analysis of the quality of single preemption schedules on three uniform parallel machines
• Title not available (Why is that?)
• Optimal preemptive on-line scheduling on uniform processors with non-decreasing speed ratios
• 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
• 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
• Randomized on-line scheduling on two uniform machines
• Schedules with a single preemption on uniform parallel 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
• Title not available (Why is that?)

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)