A multi-level hybrid framework applied to the general flow-shop scheduling problem

Despite the large amount of research conducted in flow-shop scheduling most of it has concentrated on the permutation problem in which passing is not allowed, i.e. a job cannot pass (overtake) another job while waiting in a queue to be processed by a machine. In this work the general flow-shop problem, in which passing is allowed, is dealt with as it is considered to be a better representation of flow-shop instances. The evolutionary techniques of scatter search (SS) and its generalised form, path relinking (PR) are applied to this problem as they are able to provide a wide exploration of the search space and they can be integrated with intelligent search methods such as tabu search. The SS and PR strategies are embedded within a core and shell framework. Initiated from a powerful starting solution, the core and shells iteratively search the solution space to find the best possible solutions. The core consists of a highly constrained neighbourhood, estimation strategies and a dynamic tabu tenure which provide efficiency and effectiveness during various improving and dis-improving phases of the search. Several shell strategies are superimposed on to the core in order to provide the necessary mixture of intensification and diversification. This framework is able to provide substantially better results than the tabu search approach of Nowicki and Smutnicki. The proposed framework is able to achieve an average deviation from optimum of 8.475% while equalling 53 best solutions and finding 42 new best solutions on a suite of 202 benchmark problems.