Approximation algorithms for problems in scheduling with set-ups

The problem of scheduling with set-ups occurs naturally in systems that involve processing jobs of different types on common facilities where a set-up time is incurred when there is a switch from processing a job of one type to a job of another type. The set-up time may depend on the type of the previously processed job as well as the type of the job that is currently processed. For example, in high volume flexible manufacturing systems, several types of products are produced on the same machine and a set-up is required to configure or rearrange the machine when there is a switch in the type of product that is produced.; In this thesis, we give some new approximation results on the problem of single machine scheduling with set-ups for various optimality criteria. For the weighted completion time and maximum flow time criterion, we present the first known constant approximation algorithms. For the maximum lateness criterion, we present an algorithm that obtains an optimal solution in a relaxed framework where the algorithm is given more resources than the optimal algorithm to which it is compared.