Award Date

December 2018

Degree Type

Thesis

Degree Name

Master of Science in Computer Science

Department

Computer Science

First Committee Member

Wolfgang Bein

Second Committee Member

Ajay Datta

Third Committee Member

Justin Zhan

Fourth Committee Member

Pradip Bhowmik

Number of Pages

55

Abstract

Researchers have developed efficient techniques, meta-heuristics to solve many Combinatorial Optimization (CO) problems, e.g., Flow shop Scheduling Problem, Travelling Salesman Problem (TSP) since the early 60s of the last century. Ant Colony Optimization (ACO) and its variants were introduced by Dorigo et al. [DBS06] in the early 1990s which is a technique to solve CO problems. In this thesis, we used the ACO technique to find solutions to the classic Flow shop Scheduling Problem and proposed a novel method for solution improvement. Our solution is composed of two phases; in the first phase, we solved TSP using ACO technique which gave us an initial permutation or tour. We used the same trip as an initial solution for our problem and then improved it by using 2-opt exchanges which yielded in a promising result. Furthermore, we introduced another improvement technique which gave us a more promising result. We have compared our results with the best (optimal) and worst solution known till date. A comprehensive experimental study using existing dataset proves that our approach remarkably gives good results.

Keywords

2-opt; ant colony optimization; makespan minimizing; metaheuristic; permutation flow-shop scheduling; travelling salesman analogy

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