A class of order-based genetic algorithm for flow shop scheduling

A class of order-based genetic algorithm is presented for flow shop scheduling that is a typical NP-hard combinatorial optimisation problem with a strong engineering background. The proposed order-based genetic algorithm borrows from the idea of ordinal optimisation to ensure the quality of the solution found with a reduction in computation effort and applies the evolutionary searching mechanism and learning capability of genetic algorithms to effectively perform exploration and exploitation. Under the guidance of ordinal optimisation and with an emphasis on order-based searching and elitist-based evolution in the proposed approach, a solution that is "good enough" can be guaranteed with a high confidence level and reduced level of computation. The effectiveness of the proposed algorithm is demonstrated by numerical simulation results based on benchmarks, and its optimisation quality is much better than that of the classic genetic algorithm, the well-known NEH heuristic, as well as being better than a pure blind search. Moreover, the effects of some parameters on optimisation performance are discussed.