SEDDIK Yasmina

毕业博士
科研组 : DECISION
离开日期 : 2013-8-31
https://lip6.fr/Yasmina.Seddik

责任导师 : Christophe GONZALES

助理责任导师 : 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.

答辩 : 2012-12-7

评委会 :

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é]

离开日期 : 2013-8-31

2011-2017 刊物

Mentions légales
网站导航