Title: Iterated greedy insertion approaches for the flexible job shop scheduling problem with transportation times constraint

Authors: Azzedine Bekkar; Ghalem Belalem; Bouziane Beldjilali

Addresses: Department of Computer Science, Faculty of Exact and Applied Sciences, LIO Laboratory, University of Oran 1 Ahmed Ben Bella, Oran, Algeria ' Department of Computer Science, Faculty of Exact and Applied Sciences, LIO Laboratory, University of Oran 1 Ahmed Ben Bella, Oran, Algeria ' Department of Computer Science, Faculty of Exact and Applied Sciences, LIO Laboratory, University of Oran 1 Ahmed Ben Bella, Oran, Algeria

Abstract: This paper proposes two greedy heuristics based on an iterated insertion technique to solve the flexible job shop scheduling problem with transportation time's constraint. The approaches treat the two sub-problems of: the assignment of machines to operations and the sequencing of the operations on the assigned machines. The idea is to start with a greedy construction method, then, apply an iterative destroy and recreate algorithm, to minimise the maximal completion time of machines (makespan). The heuristics were tested on a benchmark that considers the transportation times between the machines and based on a real flexible job shop 'AIP-PRIMECA cell of Valenciennes University'. The results of the proposed heuristics are compared with the results of a mixed integer linear program (MILP) and the potential fields (PF) approach. The results obtained are very promising. [Submitted 2 May 2017; Accepted 26 January 2018]

Keywords: flexible job shop; scheduling; production; optimisation; greedy heuristics.

DOI: 10.1504/IJMR.2019.096746

International Journal of Manufacturing Research, 2019 Vol.14 No.1, pp.43 - 66

Received: 02 May 2017
Accepted: 26 Jan 2018
Published online: 10 Dec 2018 *

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