A genetic algorithm-based approach to flexible flow-line scheduling with variable lot sizes

Genetic Algorithms (GA's) have been used widely for such combinatorial optimization problems as the Traveling Salesman Problem (TSP), the Quadratic Assignment Problem (QAP), and job shop scheduling. In all of these problems there is usually a well defined representation which GA's use to solve the problem. In this paper, we present a novel approach for solving two related problems - lot-sizing and sequencing - concurrently using GA's. The essence of our approach lies in the concept of using a unified representation for the information about both the lot sizes and the sequence and enabling GA's to evolve the chromosome by replacing primitive genes with good building blocks. In addition, a simulated annealing procedure is incorporated to further improve the performance. We evaluate the performance of applying the above approach to flexible flow-line scheduling with variable lot sizes for an actual manufacturing facility, comparing it to such alternative approaches as pair-wise exchange improvement, tabu search, and simulated annealing procedures. The results show the efficacy of this approach for flexible flow-line scheduling.