Accession Number:

ADA241225

Title:

Algorithms for Scheduling and Network Problems

Descriptive Note:

Doctoral thesis

Corporate Author:

MASSACHUSETTS INST OF TECH CAMBRIDGE LAB FOR COMPUTER SCIENCE

Personal Author(s):

Report Date:

1991-09-01

Pagination or Media Count:

131.0

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.

Subject Categories:

  • Theoretical Mathematics

Distribution Statement:

APPROVED FOR PUBLIC RELEASE