Award Date


Degree Type


Degree Name

Master of Science (MS)


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



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.


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


Computer Sciences