Physical Sciences and Mathematics Commons^™

Genetic Algorithms For Stochastic Flow Shop No Wait Scheduling, Harpal Maini, Ubirajara R. Ferreira

Electrical Engineering and Computer Science - Technical Reports

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 …