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

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]