An effective multi-start multi-level evolutionary local search for the flexible job-shop problem. (June 2017)

• Record Type: Journal Article
• Authors: Kemmoé-Tchomté, S.; Lamy, D.; Tchernev, N.
• Is Part Of: Engineering applications of artificial intelligence. Volume 62(2017:Feb.)
• Page Start: 80
• Page End: 95
• Publication Date: 2017-06
• Subjects: Flexible Job‐shop -- Metaheuristics -- GRASP -- Multi-level ELS -- Neighbourhood structures; Engineering -- Data processing -- Periodicals; Artificial intelligence -- Periodicals; Expert systems (Computer science) -- Periodicals; Ingénierie -- Informatique -- Périodiques; Intelligence artificielle -- Périodiques; Systèmes experts (Informatique) -- Périodiques; Artificial intelligence; Engineering -- Data processing; Expert systems (Computer science); Periodicals; 620.00285
• DOI: 10.1016/j.engappai.2017.04.002
• Languages: English
• ISSNs: 0952-1976

Abstract

Abstract: In this paper, an improved greedy randomized adaptive search procedure (GRASP) with a multi-level evolutionary local search (mELS) paradigm is proposed to solve the Flexible Job-shop Problem (FJSP). The FJSP is a generalisation of the well-known Job-Shop Problem with the specificity of allowing an operation to be processed by any machine from a given set. The GRASP metaheuristic is used for diversification and the mELS is used for intensification. Four different neighbourhood structures are formalised. A procedure for fast estimation of the neighbourhood quality is also proposed to accelerate local search phases. The metaheuristic has been tested on several datasets from the literature. The experimental results demonstrate that the proposed GRASP-mELS has achieved significant improvements for solving FJSP from the viewpoint of both quality of solutions and computation time. A comparison among the proposed GRASP-mELS and other state-of-the-art algorithms is also provided in order to show the effectiveness and efficiency of the proposed metaheuristic. Highlights: An efficient construction heuristic which generates good starting solutions. A local search based on critical path analysis which encompasses both machine changes and operation permutations using procedure for fast estimation of the neighbours' quality. Definition of new neighbourhoods integrated in a highly randomized neighbourhood structure where several permutations or machine changes are made to generate a neighbour of a solution. An improved intensification scheme, the multi-level ELS, embedded in a GRASP metaheuristic.