Report Number: CS-TR-98-1611
Institution: Stanford University, Department of Computer Science
Title: Approximation Algorithms for Scheduling Problems
Author: Chekuri, Chandra
Date: September 1998
Abstract: This thesis describes efficient approximation algorithms for
some NP-Hard deterministic machine scheduling and related
problems. We study the objective functions of minimizing
makespan (the time to complete all jobs) and minimizing
average completion time in a variety of settings described
1. Minimizing average completion time and its weighted
generalization for single and parallel machine problems. We
introduce new techniques that either improve earlier results
and/or result in simple and efficient approximation
algorithms. In addition to improved results for specific
problems, we give a general algorithm that converts an x
approximate single machine schedule into a (2x + 2)
approximate parallel machine schedule.
2. Minimizing makespan on machines with different speeds when
jobs have precedence constraints. We obtain an O(log m)
approximation (m is the number of machines) in O(n^3) time.
3. We introduce a class of new scheduling problems that arise
from query optimization in parallel databases. The novel
aspect consists of modeling communication costs in query
execution. We devise algorithms for pipelined operator
scheduling. We obtain a PTAS and also simpler O(n log n) time
algorithms with ratios of 3.56 and 2.58.
4. Multi-dimensional generalizations of three well known
problems in combinatorial optimization: multi-processor
scheduling, bin packing, and the knapsack problems. We obtain
several approximability and inapproximability results.