Algorithms for Scheduling and Network Problems
Abstract
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.
Document Details
- Document Type
- Technical Report
- Publication Date
- Sep 01, 1991
- Accession Number
- ADA241225
Entities
People
- Joel M. Wein
Organizations
- Massachusetts Institute of Technology