A genetic algorithm approach to the tool allocation problem in flexible manufacturing systems

Abstract

This thesis focuses on the development of a Genetic Algorithm (GA) to solve the tool allocation problem in flexible manufacturing systems (FMS). Tool allocation on machines’ tool magazines is a setup problem in an FMS and has significant effects on the overall system performance in terms of flexibility, efficiency and utilization. The tool allocation problem as defined in this study involves allocation of tools into the limited tool magazines of a set of machines in an FMS in order to produce a set of batches for part types that have route flexibilities. Consideration of the operation route flexibilities for parts and allowing splitting of part batches among alternative machines are important characteristics of this study which differentiate it from other work on tool allocation. The performance measure is selected as a multi-criteria objective that minimizes the weighted sum of unsatisfied demand of parts and the workload imbalance among machines. The mathematical programming model of the problem is presented. Since the exact solution procedures such as branch & bound are intractable for the tool allocation problem, a GA procedure is proposed. The chromosome structure and genetic operators are specifically designed. The developed GA procedure is tested on a set of problems. It is observed that the proposed approach provides satisfactory results in reasonable computation times when compared to exact solution algorithms.