Award Date

5-2011

Degree Type

Thesis

Degree Name

Master of Science in Computer Science

Department

Computer Science

First Committee Member

Wolfgang Bein, Chair

Second Committee Member

Lawrence L. Larmore

Third Committee Member

Laxmi Gewali

Graduate Faculty Representative

Ju-Yeon Jo

Number of Pages

52

Abstract

The shop problems in scheduling will be discussed in this thesis. The ones I'll be discussing will be the flow shop, open shop, and job shop. The general idea of shop problems is that you're given a set of jobs and a set of machines. Each job is predeterminely broken into parts and there are rules to how each part is executed on a machine. In this thesis, several shop problems and their algorithms will be introduced that I have researched. There are several examples and counter examples that I have constructed. Also I will discuss how an arbitrary problem that can be solved polynomially can be changed so that there are no polynomial algorithms that can solve it. Scheduling is used in computer science in the area of operating systems and it can be used in engineering. This is an important for a company when they want to run several jobs efficiently so that resources can be saved.

Keywords

Computer scheduling; Production scheduling

Disciplines

Computer Sciences | Theory and Algorithms

Language

English


Share

COinS