A generic memory design for a memoryless metaheuristic with the application of flowshop scheduling problem

Advisors: Reinaldo J. Moraga; Shi-Jie Gary Chen.Committee members: Ziteng Wang.Includes bibliographical references.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.M.S. (Master of Science