Document Type

Report

Date

1-1993

Embargo Period

5-7-2012

Keywords

algorithms

Language

English

Disciplines

Computer Sciences

Description/Abstract

ln this paper we present Genetic Algorithms - evolutionary algorithms based on an analogy with natural selection and survival of the fittest - applied to an NP Complete combinatorial optimization problem: minimizing the makespan of a Stochastic Flow Shop No Wait (FSNW) schedule. This is an important optimization criteria in real-world situations and the problem itself is of practical significance. We restrict our applications to the three machine flow shop no wait problem which is known to be NP complete. The stochastic hypothesis is that the processing times of jobs are described by normally distributed random variables. We discuss how this problem may be translated into a TSP problem by using the start interval concept. Genetic algorithms, both sequential and parallel are then applied to search the solution space and we present the algorithms and empirical results.

Additional Information

School of Computer and Information Science, Syracuse University, SU-CIS-93-21

Source

local

Share

COinS
 
 

To view the content in your browser, please download Adobe Reader or, alternately,
you may Download the file to your hard drive.

NOTE: The latest versions of Adobe Reader do not support viewing PDF files within Firefox on Mac OS and if you are using a modern (Intel) Mac, there is no official plugin for viewing PDF files within the browser window.