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) : Wein, Joel M


Full Text : https://apps.dtic.mil/dtic/tr/fulltext/u2/a241225.pdf


Report Date : Sep 1991


Pagination or Media Count : 131


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.


Descriptors :   *ALGORITHMS , ENVIRONMENTS , NETWORKS , THESES , SHOPS(WORK AREAS) , SCHEDULING , APPROXIMATION(MATHEMATICS) , COMBINATORIAL ANALYSIS , ONLINE SYSTEMS , OPTIMIZATION , PARALLEL PROCESSING


Subject Categories : Theoretical Mathematics


Distribution Statement : APPROVED FOR PUBLIC RELEASE