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 below. 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.
http://i.stanford.edu/pub/cstr/reports/cs/tr/98/1611/CS-TR-98-1611.pdf