An Efficient Approximation Algorithm for Minimizing Makespan on Uniformly Related Machines

Chandra Chekuri, Michael Bender

Research output: Contribution to journalArticlepeer-review


We give a new and efficient approximation algorithm for scheduling precedence-constrained jobs on machines with different speeds. The problem is as follows. We are given n jobs to be scheduled on a set of m machines. Jobs have processing times and machines have speeds. It takes pj/si units of time for machine i with speed si to process job j with processing requirement pj. Precedence constraints between jobs are given in the form of a partial order. If j <≺ k, processing of job k cannot start until job j's execution is completed. The objective is to find a non-preemptive schedule to minimize the makespan of the schedule. Chudak and Shmoys (1997, "Proceedings of the Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)," pp. 581-590) gave an algorithm with an approximation ratio of O(log m), significantly improving the earlier ratio of O(√m) due to Jaffe (1980, Theoret. Comput. Sci. 26, 1-17). Their algorithm is based on solving a linear programming relaxation. Building on some of their ideas, we present a combinatorial algorithm that achieves a similar approximation ratio but runs in O(n3) time. Our algorithm is based on a new and simple lower bound which we believe is of independent interest.

Original languageEnglish (US)
Pages (from-to)212-224
Number of pages13
JournalJournal of Algorithms
Issue number2
StatePublished - Nov 2001
Externally publishedYes

ASJC Scopus subject areas

  • Control and Optimization
  • Computational Mathematics
  • Computational Theory and Mathematics


Dive into the research topics of 'An Efficient Approximation Algorithm for Minimizing Makespan on Uniformly Related Machines'. Together they form a unique fingerprint.

Cite this