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

Ajoy K Datta

Third Committee Member

Laxmi Gewali

Number of Pages

92

Abstract

Among shop scheduling problems, job shop and mixed shop are one of the most general models encompassing open shop and flow shop. Many job shop problems are NP hard, but there are numerous cases, which possess polynomial solutions when the number of jobs or the number of machines (or both) is limited.

This thesis gives an overview of methods and algorithms for solving - in polynomial time - such special shop problems, including open, flow, job shop and mixed shop. The tools used include Monge interchange, dynamic programming, greedy techniques and sweep line algorithms and the primary focus of this thesis is to give a taxonomy of such problems with their solutions. Additionally the thesis outlines a neighborhood search technique which uses the disjunctive graph model and which can be applied as a heuristic for a wide range of NP-hard shop problems.

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