Award Date

5-1-2019

Degree Type

Thesis

Degree Name

Master of Science (MS)

Department

Computer Science

First Committee Member

Wolfgang Bein

Second Committee Member

Ajoy Datta

Third Committee Member

Laxmi Gewali

Fourth Committee Member

Henry Selvaraj

Number of Pages

63

Abstract

Permutation Flow Shop Scheduling refers to the process of allocating operations of jobs to machines such that an operation starts to process on machine j only after the processing completes in j-1machine. At a time a machine can process only one operation and similarly a job can have only one operation processed at a time. Finding a schedule that minimizes the overall completion times for Permutation Flow Shop problems is NP-Hard if the number of machines is greater than 2. Sowe concentrates on approaches with approximate solutions that are good enough for the problems. Heuristics is one way to find the approximate solutions for a problem. For our thesis, we have used two heuristics - NEH and Simulated Annealing, both individually and in a combined form, to find the solutions for Permutation Flow Shop problems. We have compared NEH and Simulated Annealing algorithm based on result and execution time and also compared the combined algorithm with existing ones. Standard benchmarks are used to evaluate the performances of the implemented algorithm.

Keywords

Flow shop; NEH; NP Hard; Permutation flow shop; Scheduling; Simulated annealing

Disciplines

Computer Sciences

Language

English


Share

COinS