Award Date

8-1-2014

Degree Type

Thesis

Degree Name

Master of Science in Computer Science

Department

Computer Science

First Committee Member

Bein Wolfgang

Second Committee Member

K. Ajoy Datta

Third Committee Member

L. Lawrence Larmore

Fourth Committee Member

Venkatesan Muthukumar

Number of Pages

78

Abstract

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.

Keywords

Computer scheduling

Disciplines

Computer Sciences | Theory and Algorithms

File Format

pdf

Degree Grantor

University of Nevada, Las Vegas

Language

English

Rights

IN COPYRIGHT. For more information about this rights statement, please visit http://rightsstatements.org/vocab/InC/1.0/

Download


Share

COinS