Award Date

5-1-2014

Degree Type

Thesis

Degree Name

Master of Science in Computer Science

Department

Computer Science

First Committee Member

Wolfgang Bein

Second Committee Member

Ajoy K. Datta

Third Committee Member

Laxmi Gewali

Fourth Committee Member

Zhiyong Wang

Number of Pages

65

Abstract

We present a new branch and bound algorithm for solving three machine permutation flow shop problem where the optimization criterion is the minimization of sum of completion times of all the jobs. The permutation flow shop problem (F||∑Ci ) belongs to the class of NP-hard problems; finding the optimal solution is thus expected to be highly computational. For each solution our scheme gives an approximation ratio and finds near optimal solutions. Computational results for up to 20 jobs are given for 3 machine flow shop problem when the objective is minimizing the sum of completion times. The thesis also discusses a number of related but easier flow shop problems where polynomial optimization algorithms exist.

Keywords

Branch and bound algorithms; Combinatorial optimization; Permutations; Production scheduling; Scheduling

Disciplines

Computer Sciences

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