Forschungsleitung (Direction de recherche) : Christophe GONZALES

Co-Betreuung : 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.

Publikationen 2011-2017