Skip to Main content Skip to Navigation
Theses

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

https://hal.univ-lorraine.fr/tel-01748789
Contributor : Thèses Ul <>
Submitted on : Thursday, March 29, 2018 - 11:49:20 AM
Last modification on : Tuesday, April 24, 2018 - 1:31:01 PM
Long-term archiving on: : Friday, September 14, 2018 - 9:51:41 AM

File

2009_BELLANGER_A.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : tel-01748789, version 1

Collections

Citation

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⟩

Share

Metrics

Record views

84

Files downloads

65