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.
Maini, Harpal and Ferreira, Ubirajara R., "Genetic Algorithms for Stochastic Flow Shop No Wait Scheduling" (1993). Electrical Engineering and Computer Science Technical Reports. Paper 164.