APPROXIMATION SCHEMES FOR SCHEDULING JOBS WITH CHAIN PRECEDENCE CONSTRAINTS

DOI10.1142/S0129054110007118zbMath1186.68067OpenAlexW1999219034MaRDI QIDQ5187850

Roberto Solis-Oba, Klaus Jansen

Publication date: 9 March 2010

Published in: International Journal of Foundations of Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1142/s0129054110007118

zbMATH Keywords

schedulingapproximation algorithmprecedence constraints

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Approximation algorithms (68W25)

Cites Work

• Scheduling multiprocessor tasks with chain constraints
• Scheduling chain-structured tasks to minimize makespan and mean flow time
• Scheduling chains on uniform processors with communication delays
• A comment on scheduling on uniform machines under chain-type precedence constraints
• An Efficient Approximation Algorithm for Minimizing Makespan on Uniformly Related Machines
• Nonpreemptive LP-Scheduling on Homogeneous Multiprocessor Systems
• Preemptive Scheduling of Uniform Processor Systems
• Complexity of Scheduling under Precedence Constraints
• Approximation Algorithms for Precedence-Constrained Scheduling Problems on Parallel Machines that Run at Different Speeds
• Short Shop Schedules
• Makespan Minimization in Job Shops: A Linear Time Approximation Scheme
• Scheduling independent multiprocessor tasks

This page was built for publication: APPROXIMATION SCHEMES FOR SCHEDULING JOBS WITH CHAIN PRECEDENCE CONSTRAINTS