Journée GOThA (Angers, juillet 2016)

08/07/16 : Journée GOThA (UCO, LARIS - Angers)

• Vincent T'Kindt, Algorithmes exponentiels avec application à l’ordonnancement

Résumé : Dans cette présentation nous allons nous intéresser à l’existence d’algorithmes exponentiels pour la résolution de problèmes d’ordonnancement. Un algorithme exponentiel est un algorithme exact , pour un problème NP-difficile, pour lequel il est possible de borner sa complexité temporelle au pire cas. Cette thématique de recherche est émergente dans le domaine de l’ordonnancement, bien que de nombreux résultats existent déjà pour des problèmes de graphe ou de décision. Nous verrons dans un premier temps une méthode générique pour déduire un tel algorithme pour des problèmes d’ordonnancement mettant en œuvre un problème d’affectation. Cet algorithme sera appliqué à différent problèmes. Nous traiterons dans un second temps de problèmes d’ordonnancement pour lesquels un problème de permutation est à résoudre.

• Imed Kacem et Christophe Rapine, Approximation Algorithms for the Open Shop Problem with Delivery Times

In this work we consider the open shop scheduling problem where the jobs have delivery times. Our minimization criterion is the maximal lateness of the jobs. This problem is knwon to be NP-hard, even restricted to only 2 machines. We establish that any list scheduling algorithm has a performance guarantee of 2. For a fixed number of machines, we design a polynomial time approximation scheme (PTAS) which represents the best possible result due to the strong NP-hardness of the problem.

• Nicolas Dupin, Multi-objective scheduling of nuclear power plant’s maintenances, sustainable development extensions of the challenge EURO/ROADEF 2010

Abstract: This paper addresses the scheduling problem of nuclear power plant outages for maintenance and refueling, defined for the Challenge EURO/ROADEF 2010. The challenge was formulated in 2-stage stochastic programming, first level being outage date decisions and refueling levels whereas production levels ensures feasibility questions and cost guarantees, minimizing the expected financial cost. Other criterion are investigated. For dynamic reoptimisation considerations, stability and robustness to outages prolongations are operational needs. Analyzing the impact of minimizing nuclear wastes implied by the maintenance scheduling allows to have another trade off to arbitrate between similar financial cost solutions. A MIP formulation for the challenge is first proposed before the extensions. A generic matheuristic resolution is proposed combining Variable Neighbourhood Descent and MIP neighbourhoods to tackle the real world instances. The numerical results offers some perspective on the mono and multi-objective objective scheduling of nuclear power plant’s maintenances.

• Guillerme Duvillié, Gap scheduling problems

We focus on two gap scheduling problems. This kind of problems aims at taking the number or the size of the gaps in the schedule into consideration either in the objective function or as a constraint. We focus particularily on "maximizing the minimum gap". The first model consists in a single machine and a set of unit length jobs with release dates and deadlines. The objective is to find a schedule of every job such that the minimum idle period between two consecutive jobs is maximum. We show that this problem can be solved in polynomial time. The second model consists in a set of identical machines, a set of unit jobs with fixed execution time and a set of prescheduled jobs. As previously, the objective is to maximize the minimum gap. After highlighting the NP-completeness of this problem, we provide a 2-dual approximation algorithm for the latter.

• Michael Poss, Robust scheduling with budgeted uncertainty

In this work we study min max robust scheduling problems assuming that the processing times can take any value in the budgeted uncertainty set introduced by Bertsimas and Sim (2003,2004). We focus more particularly on one-machine problems minimizing the weighted sum of completion times and multiple machines problems minimizing the makespan, providing polynomial algorithms, pseudo-polynomial algorithms, and approximation algorithms (FPTAS, PTAS, constant factor and average non-constant factor). In addition, we prove that the robust version of the polynomial problem 1||sum w_j C_j is NP-hard in the strong sense.

• Aurélien Froger et Eric Pinson, A Benders-based branch-and-cut approach to solve a wind turbine maintenance scheduling problem

We deal with a maintenance scheduling problem rising in the onshore wind power industry. We address the problem on a short-term horizon considering an individual management of the technicians through a space-time tracking. The objective is to find a maintenance planning that maximizes the production of the turbines while taking into account wind predictions, multiple task execution modes, and task-technician assignment constraints. We introduce an exact method to solve this challenging problem. We first propose integer linear programming (ILP) formulations of this problem. Then, on this basis, we build up a Benders-based branch-and-cut approach making use of Benders cuts as well as problem-specific cuts. Our method solves to optimality most of the instances or delivers solutions with a small average gap with respect to upper bounds. The results suggest that our method significantly outperforms the direct resolution of ILP models.