Award Date

5-1-2013

Degree Type

Thesis

Degree Name

Master of Science in Computer Science

Department

Computer Science

First Committee Member

Wolfgang Bein

Second Committee Member

Ajoy K. Datta

Third Committee Member

Ju-Yeon Jo

Fourth Committee Member

Venkatesan Muthukumar

Number of Pages

58

Abstract

Flow Shop Scheduling refers to the process of allotting various jobs to the machines given, such that every job starts to process on a machine n only after it has finished processing on machine n-1, with each job having n operations to be performed one per machine. To find a schedule that leads to the optimal utilization of resources, expects the schedule to finish in a minimum span of time, and also satisfy the optimality criterion set for the related scheduling problem is NP-Hard, if n > 2. In this thesis, we have developed an algorithm adopting a heuristic called Simulated Annealing, to act as a support to the Flow Shop Scheduling. This algorithm tries to deliver good/near optimal solutions to the given scheduling problem, in a reasonable time. We also carry out various tests to determine the behavior of the algorithm as well as to evaluate its effectiveness.

Keywords

Combinatorial optimization; Computer scheduling; Flow shop; Production scheduling; Scheduling; Simulated annealing (Mathematics)

Disciplines

Computer Sciences | Discrete Mathematics and Combinatorics

Language

English


Share

COinS