SEDDIK Yasmina
责任导师 : 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é]
2011-2017 刊物
-
2017
- Ch. Dürr, Z. Hanzalek, Ch. Konrad, Y. Seddik, R. Sitters, O. Vasquez Perez, Gerhard J. Woeginger : “The triangle scheduling problem”, Journal of Scheduling, (Springer Verlag) (2017)
-
2015
- Y. Seddik, Ch. Gonzales, S. Kedad‑Sidhoum : “Performance guarantees for a scheduling problem with common stepwise job payoffs”, Theoretical Computer Science, vol. 562, pp. 377-394, (Elsevier) (2015)
-
2013
- Y. Seddik, Ch. Gonzales, S. Kedad‑Sidhoum : “A polynomial time OPT-1 algorithm for a scheduling problem with two delivery dates and cumulative payoffs”, 6th Multidisciplinary International Scheduling Conference: Theory and Applications, MISTA 2013, Gent, Belgium, pp. 268-289 (2013)
- Y. Seddik, Ch. Gonzales, S. Kedad‑Sidhoum : “An absolute approximation algorithm for a scheduling problem with cumulative payoffs”, 26th European Conference on Operational Research, Rome, Italy (2013)
- Y. Seddik, Ch. Gonzales, S. Kedad‑Sidhoum : “Single machine scheduling with delivery dates and cumulative payoffs”, Journal of Scheduling, vol. 16 (3), pp. 313-329, (Springer Verlag) (2013)
- Y. Seddik, Ch. Gonzales, S. Kedad‑Sidhoum : “Un algorithme avec garantie de performance pour un problème d’ordonnancement avec dates de livraison et gains cumulatifs”, Congres de la Societe Francaise de Recherche Operationnelle et d'Aide a la Decision, ROADEF 2013, Troyes, France (2013)
-
2012
- Y. Seddik : “Ordonnancement avec dates de livraison et gains cumulatifs”, 博士论文, 答辩 2012-12-7, 责任导师 Gonzales, Christophe, 助理责任导师 : Kedad-sidhoum, Safia (2012)
- Y. Seddik, Ch. Gonzales, S. Kedad‑Sidhoum : “Résolution exacte d’un problème d’ordonnancement de tâches avec dates de livraison et gains cumulatifs”, 13e Congrès de la Société Française de Recherche Opérationnelle et d'Aide à la Décision, Angers, France, pp. 512-513 (2012)
- Y. Seddik, Ch. Gonzales, S. Kedad‑Sidhoum : “A Branch and Bound method for a one-machine scheduling problem with cumulative payoffs”, International Symposium on Combinatorial optimisation (CO '12), Oxford, United Kingdom, pp. 86-87 (2012)
-
2011
- Y. Seddik, Ch. Gonzales, S. Kedad‑Sidhoum : “Single machine scheduling with delivery dates and cumulative payoffs”, proceedings of the 5th Multidisciplinary International Conference on Scheduling: Theory and Applications (MISTA'11), Phoenix, Arizona, United States, pp. 261-274 (2011)
- Y. Seddik, Ch. Gonzales, S. Kedad‑Sidhoum : “Solving the one-machine scheduling problem with cumulative payoffs”, proceedings of the 10th workshop on Models and Algorithms for Planning and Scheduling Problems (MAPSP'11), Nymburk, Czechia, pp. 245-247 (2011)
- Y. Seddik, Ch. Gonzales, S. Kedad‑Sidhoum : “Ordonnancement de tâches avec contraintes de livraison et gains cumulatifs”, 12e Congrès de la Société Française de Recherche Opérationnelle et d'Aide à la Décision (ROADEF 2011), vol. II, Saint-Etienne, France, pp. 855-856 (2011)