An Iterative Greedy Insertion Technique for Flexible Job Shop Scheduling Problem

Azzedine Bekkar (1) , Oualid Guemri (1) , Abdelghani Bekrar (2) , Nassima Aissani (1) , Bouziane Beldjilali (1) , Damien Trentesaux (2)

1 LIO - Laboratoire d'Informatique d'Oran
2 LAMIH - Laboratoire d'Automatique, de Mécanique et d'Informatique industrielles et Humaines - UMR 8201

This paper studies the problem of scheduling in a flexible job shop. A greedy heuristic is developed to solve precisely the sequencing (allocation) problem. The principle of this approach is to iteratively insert operations on the machines until the objective of minimizing the Cmax (makespan) is reached. The heuristic was tested on a particular Benchmark which considers the transportation times between the machines, and get inspiration from a real assembly cell: the AIP-PRIMECA cell at the University of Valenciennes, that from an OR perspective, can be viewed as Flexible Job Shop, leading to the formulation of a Flexible Job-Shop Scheduling Problem (FJSSP). The results obtained by the greedy heuristic on this benchmark are very promising.

Mots clés: "Flexible Job Shop"; "Greedy heuristics"; "Optimization"; "Scheduling"

Domaines: Automatique / Robotique

Azzedine Bekkar, Oualid Guemri, Abdelghani Bekrar, Nassima Aissani, Bouziane Beldjilali, et al.. An Iterative Greedy Insertion Technique for Flexible Job Shop Scheduling Problem. 8th IFAC Conference on Manufacturing Modelling, Management and Control MIM 2016, Dec 2016, Troyes, France. pp.1956-1961, ⟨10.1016/j.ifacol.2016.07.917⟩. ⟨hal-03406967⟩