Evolutionary algorithms for flowshop sequencing with non-unique jobs

Sequencing problems are difficult combinatorial problems because of the extremely large search space of possible solutions and the large number of ‘local’ optima that arise. Unlike other NP-hard combinatorial problems, the search space, in general, for sequencing problems (under the makespan objective) consists of sequences with objective function values that lie within only a relatively small amount of each other. This means that when a change is made to the sequence, an improvement or non-improvement is not easily recognised. This makes the problem much more difficult to solve. A number of constructive heuristics exist that obtain good solutions in a short period of time, however, the output of such algorithms is generally a single sequence which may not be feasible or preferred with respect to industry constraints. Other heuristic algorithms such as Simulated Annealing and Tabu Search have also been applied and successes have been reported. However, the performance is dependent upon a number of finely tuned parameters and the output is again only a single solution. For these reasons, Evolutionary Algorithms (EAs) may be suitable solution strategy, for which limited research has been performed. In this research, a number of new EAs have been proposed and a number of modifications have been made to several constructive algorithms to cope with non-unique jobs or jobs with multiple demands. A numerical comparison of a number of benchmark problems and real data of a truck assembly line has also been presented.