A genetic algorithm application on ordered flow-shop problems

In this thesis, the problem of scheduling jobs in a flow-shop environment, which is a NP-complete problem is considered. Genetic algorithm is applied in order to find a new approachto the problem.In the first part of the study, the structure of flow-shop problems and some related randomsearch methods such as tabu search, simulated annealing, ant colonies and artificial immunesystems are considered.The application, which is made to determine the performance of genetic algorithm, on orderedflow-shop problems are considered as two different parts as the nature of the ordered type offlow-shop problems.In the first part, the general case, which is the maximum processing time for every joboccurred in intermediate machines, are considered. The application is made on 10 differentjob-machine combinations and as an outcome, genetic algorithm had close results, whichwere better than the results of simulated annealing, to Smith Panwalkar Dudek algorithm wasobserved.In the second part, the maximum processing time for every job occurred on the first or lastmachine, which was the special case, are considered. Same job-machine combinations forgeneral case are considered and again genetic algorithm had better result than simulatedannealing where the results are close enough to Smith Panwalkar Dudek algorithm.After two application, it was observed that in general case, genetic algorithm provides areasonable and close optimal solution which less effort and time than Smith Panwalker andDudek algorithm. But in the special case, Smith Panwalkar Dudek algorithm is much moresimple and optimal solution guaranteed than genetic algorithm.Keywords: Ordered Flow-Shop Problems, Genetic Algorithm