LIP6 CNRS Sorbonne Université Tremplin Carnot Interfaces
Direct Link LIP6 » News » PhD students

SEDDIK Yasmina

PhD graduated
Team : DECISION
Departure date : 08/31/2013
http://www-desir.lip6.fr/~seddiky/
Supervision : Christophe GONZALES
Co-supervision : KEDAD-SIDHOUM Safia

Scheduling with delivery dates and cumulative payoffs

Starting from a real world digitization workflow issue, we identified a scheduling problem with a new criterion involving common delivery dates for the jobs. In order to focus on this new criterion and on the jobs' release dates, we mainly worked on a single machine problem. We delimited the complexity classes of the problem, and provided a Branch and Bound algorithm for the general problem, based on dedicated bounds and dominance rules. We also considered the weakly NP-hard problem with two delivery dates, for which we designed a pseudopolynomial dynamic programming algorithm and an approximation algorithm with an absolute performance guarantee of 1. Finally, in order to consider a problem more closely related to the industrial issue, we studied a permutation flowshop problem with the same criterion. For this problem, we proposed several heuristic methods: constructive algorithms, local search, and a GRASP algorithm. All the algorithms were implemented. In particular the Branch and Bound method for the single machine problem and the local search algorithms for the flowshop provide good solutions in a reasonable time.
Defence : 12/07/2012 - 10h30 - Site Jussieu 55-65/211
Jury members :
M. Jacques Carlier [Rapporteur]
M. Stéphane Dauzère-Pérès [Rapporteur]
M. Philippe Chrétienne
M. Federico Della Croce
M. Christophe Gonzales
Mme. Safia Kedad-Sidhoum
M. Pascal Wirth [Invité]

2011-2017 Publications

 Mentions légales
Site map |