Master of Science in Computer Science
First Committee Member
Second Committee Member
K. Ajoy Datta
Third Committee Member
L. Lawrence Larmore
Fourth Committee Member
Number of Pages
Open shop scheduling problems are combinatorial problems where jobs with certain processing requirements on a number of different machines must be arranged in such a way that objectives related to completion time are optimized. Such problems have applications over a wide spectrum including such as communications, routing and manufacturing.
Many open shop problems are NP-hard but there are a number of special cases which possess polynomial solutions in the case of few machines or few jobs or when preemption of jobs is permitted. Many such solutions are based in the theory of matching or Hall's theorem, or more generally network flow. The primary focus of this thesis is to describe a number of polynomial-time solutions which are constructed using these related concepts and methods.
Computer Sciences | Theory and Algorithms
Chitti, Arunasri, "A Characterization of Open Shop Scheduling Problems using the Hall Theorem and Network Flow" (2014). UNLV Theses, Dissertations, Professional Papers, and Capstones. 2171.