Approximation algorithms for scheduling problems

This thesis describes efficient approximation algorithms for some NP-Hard deterministic machine scheduling and related problems. An approximation algorithm for an NP-Hard optimization problem is a polynomial time algorithm which, given any instance of the problem, returns a solution whose value is within some guaranteed multiplicative factor of the optimal solution value for that instance. The factor is called the approximation ratio of the algorithm. A typical problem in machine scheduling consists of a set of jobs that are to be executed on a set of available machines subject to a variety of constraints. Two common objectives are minimizing makespan (the time to complete all jobs) and minimizing average completion time. Constraints that we study include precedence constraints and release dates. Brief descriptions of the problems we study and highlights of our results follow.;(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. For single machine scheduling we obtain an e/;(2) Minimizing makespan on machines with different speeds when jobs have precedence constraints. We obtain an ;(3) Scheduling pipelined operator trees. This belongs to a class of new scheduling problems that arise from query optimization in parallel databases. The novel aspect consists of modeling communication costs between operators in a task system representing a query execution plan. We obtain a PTAS for this problem. We also obtain simpler ;(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 that include a PTAS for vector scheduling when the dimension is fixed.