Lagrangian relaxation-based lower bound for the two-machine flow shop with synchronized periodic maintenance

Issam Krimi (1) , Rachid Benmansour (1) , Nizar Elhachemi (1) , David Duvivier (2)

1 UM6P - Université Mohammed VI Polytechnique [Ben Guerir]
2 LAMIH - Laboratoire d'Automatique, de Mécanique et d'Informatique industrielles et Humaines - UMR 8201

In this work, we present a Lagrangian relaxation approach to generate a new lower bound for the two-machine flow shop scheduling problem under synchronized and periodic maintenance activities. The word synchronized is used to specify that the maintenance starts at the same time on both machines. The problem is denoted as F2/nr - pm/C max . First, we investigate a time-indexed formulation for the problem. Then, a lower bound was proposed using Lagrangian relaxation. Computational study shows satisfactory results.

Mots clés: Maintenance engineering; Job shop scheduling; Dynamic programming; Linear programming; Synchronization; Heuristic algorithms; Task analysis

Domaines: Informatique [cs]

Issam Krimi, Rachid Benmansour, Nizar Elhachemi, David Duvivier. Lagrangian relaxation-based lower bound for the two-machine flow shop with synchronized periodic maintenance. 2018 4th International Conference on Optimization and Applications (ICOA), Apr 2018, Mohammedia, Morocco. pp.1-6, ⟨10.1109/ICOA.2018.8370572⟩. ⟨hal-03383522⟩