A new genetic algorithm for lot-streaming flow shop scheduling with limited capacity buffers

Lot-streaming is the process of splitting a job (lot) into a number of smaller sublots to allow the overlapping of operations between successive machines in a multi-stage production system. The use of sublots usually results in substantially shorter job completion times for the corresponding schedule. A new genetic algorithm (NGA) is proposed for an n-job, m-machine, lot-streaming flow shop scheduling problem with equal size sublots and limited capacity buffers with blocking in which the objective is to minimize total earliness and tardiness penalties. NGA replaces the selection and mating operators of genetic algorithms (GAs), which often lead to premature convergence, by new operators (marriage and pregnancy operators) and also adopts the idea of inter-chromosomal dominance and individuals’ similarities. Extensive computational experiments have been conducted to compare the performance of NGA with that of GA. The results show that, on the average, NGA outperforms GA by 9.86 % in terms of objective function value for medium to large-scale lot-streaming flow-shop scheduling problems.