Direção de pesquisa : Christophe GONZALES

Co-supervisão£o : 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.

Publicações 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”, 6^th 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”, 26^th 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”, tese, defesas 07/12/2012, direção de pesquisa Gonzales, Christophe, co-supervisão£o : 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”, 13^e 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 5^th 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 10^th 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”, 12^e 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)