Title: A hybrid genetic Tabu search algorithm for minimising total completion time in a flexible job-shop scheduling problem

Authors: Asma Fekih; Hatem Hadda; Imed Kacem; Atidel B. Hadj-Alouane

Addresses: LR-OASIS, National Engineering School of Tunis, University of Tunis El Manar, Tunis, Tunisia ' LR-OASIS, National Engineering School of Tunis, University of Tunis El Manar, Tunis, Tunisia ' Laboratoire LCOMS EA 7306 Metz, Université de Lorraine, France ' LR-OASIS, National Engineering School of Tunis, University of Tunis El Manar, Tunis, Tunisia

Abstract: The flexible job-shop scheduling problem (FJSP) is an extension of the classical job-shop problem in which an operation may be executed by any machine out of a set of candidate machines. This paper addresses the FJSP under partial and total flexibility with the objective of minimising the total completion time. The FJSP is one of the most complex problems. Thus, exact methods are not effective for solving this problem and heuristic approaches are generally used to find near optimal solutions within a reasonable computation time. We develop a hybrid approach combining genetic algorithms and the Tabu search metaheuristic. The resolution approach is based on a joint resolution of the inherent assignment and sequencing subproblems. To evaluate the performance of the proposed algorithms, several benchmark instances of FJSP are used. The experimental results prove the effectiveness and efficiency of the proposed hybridisation. [Received 28 May 2019; Revised 2 July 2019; Revised 2 November 2019; Accepted 11 January 2020]

Keywords: flexible job-shop; scheduling; total completion time; genetic algorithms; Tabu search; hybrid algorithm.

DOI: 10.1504/EJIE.2020.112479

European Journal of Industrial Engineering, 2020 Vol.14 No.6, pp.763 - 781

Published online: 19 Jan 2021 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article