An Efficient Approximation Algorithm for Minimizing Makespan on Uniformly Related Machines

No abstract is available for this paper.

• Publication year

  1998

• Venue

  Conference on Integer Programming and Combinatorial Optimization

• Publication date

  1998-06-22

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1007/3-540-69346-7_29
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Approximation algorithms for precedence-constrained scheduling problems on parallel machines that run at different speeds

  1997cited by this paper
• Scheduling parallel machines on-line

  1991influential reference
• Matrix multiplication via arithmetic progressions

  1987cited by this paper
• The NP-Completeness Column: An Ongoing Guide

  1982cited by this paper
• Efficient Scheduling of Tasks without Full Use of Processor Resources

  1980cited by this paper
• Johnson: computers and intractability: a guide to the theory of np- completeness (freeman

  1979cited by this paper
• Complexity of Scheduling under Precedence Constraints

  1978cited by this paper
• Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey

  1977cited by this paper
• A Level Algorithm for Preemptive Scheduling

  1977influential reference
• Bounds on Scheduling Algorithms for Heterogeneous Comnputing Systems

  1974cited by this paper
• Bounds for certain multiprocessing anomalies

  1966cited by this paper

• Approximation Algorithms for Scheduling under Non-Uniform Machine-Dependent Delays

  2022cites this paper
• Scheduling Under Non-Uniform Job and Machine Delays

  2022cites this paper
• On the Hardness of Scheduling With Non-Uniform Communication Delays

  2021cites this paper
• Task scheduling with precedence and placement constraints for resource utilization improvement in multi-user MEC environment

  2020cites this paper
• On Optimality Conditions for Job Scheduling on Uniform Parallel Machines

  2019cites this paper
• Scheduling on Hybrid Platforms: Improved Approximability Window

  2019cites this paper
• Wide-area analytics with multiple resources

  2018cites this paper
• Fast approximation algorithms for task‐based runtime systems

  2018cites this paper
• Developing Offloading-enabled Application Development Frameworks for Android Mobile Devices

  2018cites this paper
• Developing Offloading-Enabled Application Development Frameworks for Android Mobile Devices

  2018cites this paper
• Strengths and Limitations of Linear Programming Relaxations

  2017cites this paper
• Generic algorithms for scheduling applications on heterogeneous multi-core platforms

  2017cites this paper
• A Taxonomy of Workflow Scheduling Algorithms

  2016cites this paper
• Offload Decision Models and the Price of Anarchy in Mobile Cloud Application Ecosystems

  2015cites this paper
• Scheduling Tasks with Precedence Constraints on Hybrid Multi-core Machines

  2015cites this paper
• On the DAG Decomposition

  2015influential citation
• On the DAG Decomposition 2 3 1

  2015influential citation
• Precedence-Constrained Scheduling of Malleable Jobs with Preemption

  2014cites this paper
• A note on multiprocessor speed scaling with precedence constraints

  2014cites this paper
• Fault-tolerant scheduling on parallel systems with non-memoryless failure distributions

  2014cites this paper
• On the Graph Decomposition

  2014cites this paper
• Tractability and Approximability for Subclasses of the Makespan Problem on Unrelated Parallel Machines

  2014influential citation
• A Framework for Approximate Optimization of BoT Application Deployment in Hybrid Cloud Environment

  2014cites this paper
• JOBS SCHEDULING USING GENETIC ALGORITHM

  2013cites this paper
• On the Decomposition of Posets into Minimum Set Node-Disjoint Chains

  2013cites this paper
• Orchestrating an Ensemble of MapReduce Jobs for Minimizing Their Makespan

  2013cites this paper
• Load Information Based Priority Dependant Heuristic for Manpower Scheduling Problem in Remanufacturing

  2013cites this paper
• Deadline-based workload management for MapReduce environments: Pieces of the performance puzzle

  2012cites this paper
• Tolérance aux pannes dans des environnements de calcul parallèle et distribué : optimisation des stratégies de sauvegarde/reprise et ordonnancement. (Fault tolerance in the parallel and distributed environments : optimizing the checkpoint restart strategy and scheduling)

  2012cites this paper
• Two Sides of a Coin: Optimizing the Schedule of MapReduce Jobs to Minimize Their Makespan and Improve Cluster Performance

  2012influential citation
• Optimizing performance and reliability on heterogeneous parallel systems: Approximation algorithms and heuristics

  2012cites this paper
• On the Decomposition of Posets

  2012cites this paper
• Les riches heures de l'ordonnancement

  2012cites this paper
• Two Sides of a Coin : Optimizing the Schedule of MapReduce Jobs to Minimize Their Makespan and Improve Cluster Performance

  2012cites this paper
• Scheduling under Precedence, Communication, and Energy Constraints

  2011cites this paper
• An improved monotone algorithm for scheduling related machines with precedence constraints

  2011cites this paper
• Scheduling of uniform parallel machines with s-precedence constraints

  2011cites this paper
• The Design of Approximation Algorithms

  2011cites this paper
• Run-time performance optimization and job management in a data protection solution

  2011cites this paper
• Simulated Annealing Algorithm to Minimize Makespan in Single Machine Scheduling Problem with Uniform Parallel Machines

  2011influential citation
• Minimising makespan on parallel machines with precedence constraints and machine eligibility restrictions

  2010cites this paper
• Literature Review of Single Machine Scheduling Problem with Uniform Parallel Machines

  2010influential citation
• Approximation Schemes for Scheduling Jobs with Chain Precedence Constraints

  2010cites this paper
• List Scheduling: The Price of Distribution

  2010cites this paper
• DP+IP = design of efficient backup scheduling

  2010cites this paper
• Design of Efficient Backup Scheduling

  2010cites this paper
• Enhancing and optimizing a data protection solution

  2009cites this paper
• A genetic algorithm for minimizing makespan of block erection in shipbuilding

  2009cites this paper
• A monotone approximation algorithm for scheduling with precedence constraints

  2008cites this paper
• On Non-Approximability of Coarse-Grained Workflow Grid Scheduling

  2008cites this paper
• Scheduling Tasks with Dependencies on Asymmetric Multiprocessors: Energy & Time Efficiency

  2008influential citation
• Provably efficient adaptive scheduling of parallel jobs on multiprocessors

  2008cites this paper
• Efficient Scheduling of DAGs and Sets of Chains on a Simple Asymmetric Multicore Model

  2008influential citation
• CAREER: Approximation Algorithms – New Directions and Techniques

  2008cites this paper
• Aspects of Online Routing and Scheduling

  2007cites this paper
• Scheduling DAGs on asynchronous processors

  2007cites this paper
• Adaptive Scheduling of Parallel Jobs on Functionally Heterogeneous Resources

  2007cites this paper
• A survey on task scheduling for heterogeneous parallel computing environments

  2007cites this paper
• Solving a large-scale precedence constrained scheduling problem with elastic jobs using tabu search

  2007cites this paper
• Scheduling Algorithms for Grid Computing: State of the Art and Open Problems

  2006cites this paper
• Power-aware scheduling for makespan and flow

  2006cites this paper
• Scheduling and Admission Control

  2006cites this paper
• Optimization - and Related Topics

  2006cites this paper
• Speed Scaling of Tasks with Precedence Constraints

  2005influential citation
• Value-maximizing deadline scheduling and its application to animation rendering

  2005cites this paper
• Scheduling on Unrelated Machines under Tree-Like Precedence Constraints

  2005cites this paper
• Scheduling Jobs with Chain Precedence Constraints

  2003influential citation
• Optimization Techniques for Task Allocation and Scheduling in Distributed Multi-Agent Operations

  2003cites this paper
• Approximation Algorithms for Scheduling Jobs with Chain Precedence Constraints

  2003cites this paper
• Task scheduling in distributed systems by work stealing and mugging - a simulation study

  2002cites this paper
• Scheduling Cilk multithreaded parallel programs on processors of different speeds

  2000influential citation
• A comment on scheduling on uniform machines under chain-type precedence constraints

  2000influential citation
• Polynomial time approximation algorithms for machine scheduling: ten open problems

  1999influential citation
• An E cient Approximation Algorithm for Minimizing Makespanon Uniformly Related Machines

  1999cites this paper