Algorithms for scheduling and network problems
Joel M. Wein · Defense Technical Information Center (DTIC) · 1992
In this thesis we develop algorithms for two basic classes of problems in combinatorial optimization: deterministic machine scheduling and network optimization. In the first part of the thesis we consider approximation algorithms for two basic scheduling environments: shop scheduling and parallel machine scheduling. We give approximation algorithms for shop scheduling that significantly improve upon the performance of previous algorithms. We then study on-line approximation algorithms for parallel machine scheduling. In the second part of the thesis we present several theoretical and practical results about parallel algorithms for network optimization problems.