A genetic algorithm for a flexible job shop scheduling problem with sequence dependent set up times

This thesis addresses the problem of scheduling flexible job shops with sequence dependent setup times, and aims at minimizing makespan as an objective by using genetic algorithms. The flexible job shop is characterized by job flow through a number of work centers that contain identical or nonidentical parallel machines. Flexible Job Shop Problems divided into two subproblems. In the first subproblem, assignments of operations to machines are made. In the second subproblem, sequencing problem is solved. For the first subproblem, three assignment methods were used in this thesis. The first method is ?Approach by Localization? which assigns each operation to the suitable machine by taking into accounts the processing times and workloads of machines. This assignment procedure assumes that there are no setup times. The second method is modified version of the first method. In this method, we modified the assignment procedure by using sequence dependent setup times in addition to processing times and workloads of machines. In the third method, assignments were made randomly just for the comparison purposes. For the second subproblem, dispatching rules such as shortest processing time (SPT), most work remaining (MWR), longest processing time (LPT), shortest setup time first rule (SSTFR), random rule and neighborhood search were applied to sequence the machines.The main feature of this thesis is to combine the sequence dependent setup times with the processing times and the workloads on both assignment and sequencing procedures. The performance of genetic algorithm was also analyzed by taking into account the issues such as, initial population generation, sequencing, selection and mutation methods.