Séminaire

Possibilité de visio-conférence @IP : 193.55.95.10 Nom du correspondant technique : Nicolas CHAMPEIL Tél correspondant technique : 04 73 40 50 15 / 06 78 34 55 26 nicolas.champeil@isima.fr Tél salle de visio : 04 73 40 50 47 In this talk we consider the maximization of the weighted number of early jobs on a single machine with non-availability constraints. We deal with the resumable and the non-resumable cases. We show that the resumable version of this problem has a fully polynomial time approximation scheme (FPTAS) even if the number of the non-availability intervals is variable and a subset of jobs has deadlines instead of due dates. For the non-resumable version we remark that the problem cannot admit an FPTAS even if all due dates are equal and only one non-availability interval occurs. Nevertheless, we show in this case that it admits a polynomial time approximation scheme (PTAS) for a constant number of non-availability intervals and arbitrary due dates. REFERENCE : Imed KACEM, Hans KELLERER, Yann LANUEL. Journal of Combinatorial Optimization, October 2015, Volume 30, Issue 3, pp.403-412.