## Abstract

We give a new efficient approximation algorithm for scheduling precedence constrained jobs on machines with different speeds. The setting is as follows. There are n jobs where job j requires p_{j} units of processing. The jobs are to be scheduled on a set of m machines. Machine i has a speed si; it takes p_{j}/s_{i} units of time for machine i to process job j. The precedence constraints on the jobs are given in the form of a partial order. If j≺k, processing of k cannot start until j’s execution if finished. Let C_{j} denote the completion time of job j. The objective is to find a schedule to minimize C_{max} = maxj C_{j}, conventionally called the makespan of the schedule. We consider non-preemptive schedules where each job is processed on a single machine with no preemptions. Recently Chudak and Shmoys [1] gave an algorithm with an approximation ratio of O(logm) significantly improving the earlier ratio of 0(√m) due to Jaffe [7]. Their algorithm is based on solving a linear programming relaxation of the problem. Building on some of their ideas, we present a combinatorial algorithm that achieves a similar approximation ratio but runs in O(n^{3}) time. In the process we also obtain a constant factor approximation algorithm for the special case of precedence constraints induced by a collection of chains. Our algorithm is based on a new lower bound which we believe is of independent interest. By a general result of Shmoys, Wein, and Williamson [10] our algorithm can be extended to obtain an O(log m) approximation ratio even if jobs have release dates.

Original language | English (US) |
---|---|

Title of host publication | Integer Programming and Combinatorial Optimization - 6th International IPCO Conference, 1998, Proceedings |

Editors | E. Andrew Boyd, Robert E. Bixby, Roger Z. Rios-Mercado |

Publisher | Springer |

Pages | 383-393 |

Number of pages | 11 |

ISBN (Print) | 354064590X, 9783540645900 |

DOIs | |

State | Published - 1998 |

Externally published | Yes |

Event | 6th International Integer Programming and Combinatorial Optimization Conference, IPCO 1998 - Houston, United States Duration: Jun 22 1998 → Jun 24 1998 |

### Publication series

Name | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
---|---|

Volume | 1412 |

ISSN (Print) | 0302-9743 |

ISSN (Electronic) | 1611-3349 |

### Other

Other | 6th International Integer Programming and Combinatorial Optimization Conference, IPCO 1998 |
---|---|

Country/Territory | United States |

City | Houston |

Period | 6/22/98 → 6/24/98 |

## ASJC Scopus subject areas

- Theoretical Computer Science
- Computer Science(all)