Skip to Main content Skip to Navigation

Ordonnancement sur les machines à traitement par batches et contraintes de compatibilité

Abstract : This thesis deals with 2-stages hybrid flowshop scheduling problems with batching machines on the second stage and compatibility constraints. The processing times of tasks are given by intervals and tasks are compatible if they share a same second stage processing time. We developped 6 heuristics with worth-case analysis for the makespan minimization problem. The experimental results show that these heuristics give good schedules with an average gap of 1\% on 200 task instances. For small instances, we presented 2 exact methods, Branch \& Bounds, which solves up to 20 task instances. For the particular case with identical processing times on first stage and uniform processing time intervals we developped a Polynomial Time Approximation Scheme (PTAS). The second part of this thesis deal with scheduling problems on one batching machine with infinite capacity and regular criteria minimization. We developped pseudo-polynomial dynamic programming algorithm for minimization total completion time, maximal lateness and total tardiness. Finally we show the NP-completeness of problems with due dates
Complete list of metadata

Cited literature [231 references]  Display  Hide  Download
Contributor : Thèses Ul Connect in order to contact the contributor
Submitted on : Thursday, March 29, 2018 - 11:49:20 AM
Last modification on : Saturday, October 16, 2021 - 11:26:08 AM
Long-term archiving on: : Friday, September 14, 2018 - 9:51:41 AM


Files produced by the author(s)


  • HAL Id : tel-01748789, version 1



Adrien Bellanger. Ordonnancement sur les machines à traitement par batches et contraintes de compatibilité. Autre. Institut National Polytechnique de Lorraine, 2009. Français. ⟨NNT : 2009INPL087N⟩. ⟨tel-01748789⟩



Record views


Files downloads