Publication Date

2017

Document Type

Dissertation/Thesis

First Advisor

Moraga, Reinaldo J.||Chen, Gary

Degree Name

M.S. (Master of Science)

Department

Department of Industrial and Systems Engineering

LCSH

Operations research

Abstract

Although a strong construction phase in meta-heuristic algorithms is a critical factor to yield high-quality solutions in the local search, it has not been investigated thoroughly. The most effective mechanism to ensure the search in new areas is randomness, and a memory mechanism can help the algorithm tracking potential of good solutions during the search. This research focuses on depicting a general memory design in the construction phase of a memoryless meta-heuristic entitled Meta-RaPS (Meta-heuristic for Randomized Priority Search) in order to showing the effectiveness of spending more time in the construction phase. Permutation Flow Shop Scheduling Problem (PFSP) and famous Tillard's benchmark is represented as the application of memory mechanism in the construction phase of Meta-RaPS. The results highlight that implementing memory and learning mechanisms in the construction phase of Meta-RaPS improves its effectiveness. Computational results display the algorithm's competency even though the algorithm is just a construction meta-heuristic. The suggested technique strengthens the hypothesis that if the right procedure is executed in the construction phase of combinatorial optimization problems, local search can be eventually eliminated.

Comments

Advisors: Reinaldo J. Moraga; Shi-Jie Gary Chen.||Committee members: Ziteng Wang.||Includes bibliographical references.

Extent

iv, 87 pages

Language

eng

Publisher

Northern Illinois University

Rights Statement

In Copyright

Rights Statement 2

NIU theses are protected by copyright. They may be viewed from Huskie Commons for any purpose, but reproduction or distribution in any format is prohibited without the written permission of the authors.

Media Type

Text

Share

COinS