GoTHA workshop on robust scheduling
Welcome to the GoTHA workshop on Robust Scheduling, taking place at the LIRMM laboratory in Montpellier on April 27th 2017. The aim of the workshop is to gather researchers interested in theoretical aspects of robust scheduling, such as moderately exponential algorithms, FPT, exact polynomial algorithms, and approximation algorithms. The workshop is organized in the context of the GOThA working group on scheduling and the ROBUST ANR project.
Location
The workshop will take pace in room 1/124 in building 5, accessible from the city center through tramway line A direction "Mosson". You must get off at the stop Chateau d'Ô. You can find more details here in French (the English translation contains less information).
!!! The slides of the presentation are available here !!!
Program
 9:00  9:30 : Welcome, breakfast
9:30  10:30: Klaus Jansen  New algorithmic results for bin packing and scheduling.
In this paper we present an overview about new results for bin packing and related scheduling problems. During the last years we have worked
on the design of efficient exact and approximation algorithms for packing and scheduling problems. In order to obtain faster algorithms we studied
integer linear programming (ILP) formulations for these problems and proved structural results for optimum solutions of the corresponding ILPs.
10:30  10:45: Coffee break / Discussion

10:45  11:30 : Lars Rohwedder  On the ConfigurationLP of the Restricted Assignment Problem
We consider the classical problem of Scheduling on Unrelated Machines. In this problem a set of jobs is to be distributed among a set of machines and the maximum load (makespan) is to be minimized. The processing time p(i, j) of a job j depends on the machine i it is assigned to. Lenstra, Shmoys and Tardos gave a polynomial time 2approximation for this problem. In this paper we focus on a prominent special case, the Restricted Assignment problem, in which p(i, j) = p(j) or p(i, j) = infinity. The configurationLP is a linear programming relaxation for the Restricted Assignment problem. It was shown by Svensson that the multiplicative gap between integral and fractional solution, the integrality gap, is at most 1.941. In this paper we significantly simplify his proof and achieve a bound of 1.833. As a direct consequence this provides a polynomial (1.833+epsilon)estimation algorithm for the Restricted Assignment problem by approximating the configurationLP. The best lower bound known for the integrality gap is 1.5 and no estimation algorithm with a guarantee better than 1.5 exists unless P=NP.
11:30  12:15 Marin Bougeret  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 consider problems on a single machine that minimize the (weighted and unweighted) sum of completion times and problems that minimize the makespan on parallel and unrelated machines. We provide polynomial algorithms and approximation algorithms: constant factor, average nonconstant factor, (fully or not) polynomial time approximation schemes. In addition, we prove that the robust version of minimizing the weighted completion time on a single machine is N Phard in the strong sense.
 12:30  13:30 Lunch
13:30  14:30 Sebastian Stiller  Robust Combinatorial Optimization
Robust optimization for combinatorial problems is still a substantial challenge. The two main reasons are, first, that the nominal problem often already being NPhard, the robust problems are frequently higher in the polynomial hierarchy, and, that combinatorial problems often require a twostage robustness to be meaningful.
The talk will be split in two parts. First, we will review the most important classical and recent general results on robust combinatorial optimization. Second, we will give three examples how techniques borrowed from approximation algorithms enable twostage robust combinatorial algorithms. The first example is appointment scheduling. The second how to pack a knapsack with unknown capacity. Third we will give a practical application from processor scheduling in safety critical embedded systems. 14:30  14:45 Coffee break / Discussion
14:45  15:30 Kim Thang  Online PrimalDual Algorithms with Configuration Linear Programs
In the talk, we present a primaldual approach based on configuration linear programs to design competitive online algorithms. Prior to our work, configuration linear programs have been considered only in offline setting and the main approaches are rounding techniques that are intrinsically offline. Instead, we consider a primaldual approach that first consists to strengthen natural linear programs by introducing exponential number of variables and constraints to reduce the integrality gap. Then, at any time, the algorithm maintains a primal feasible solution and a dual feasible solution for exponential number of dual constraints. The dual feasibility is proved by the mean of a new notion, called smoothness. The smoothness notion also allows us to characterize the competitiveness of online algorithms in our approach.
Building upon our approach, we present competitive algorithms for a class of problems such as Energy Efficient Scheduling, EnergyEfficient Virtual Network Routing, Online Vector Scheduling, etc. For these concrete problems, our algorithms are optimal (up to a constant factor) in online setting and their performance almost match currently bestknown approximation guarantees in offline setting.

15:30  16:15 Valeria Borodin  Service level in stochastic 2machine permutation flow shop scheduling with random processing timesµ
Stochastic scheduling problems, in which job processing times are supposed to be nondeterministic, are usually able to meet more accurately industrial realities than their deterministic counterparts. In this talk, we focus on the stochastic twomachine permutation flowshop scheduling problem, by handling explicitly random job processing times via the concept of service (confidence) level. More specifically, we investigate analytically the relationship between the optimal values of the makespan and the associated service level, which allows us to better model and reflect the incidence of the variability of uncertain data. This study provides valuable elements for addressing both open questions posed in the book chapter of DauzèrePérès et al. (2008): (i) "How to find the maximum service level corresponding to a given schedule, which respects a bounded objective value ?", and respectively (ii) "How to find the schedule that optimizes the service level, while respecting a given value of the objective function?".
Participants
 Dmitrii Arkhipov, ISAESUPAERO, France
 Christian Artigues, LAAS, France
 Olga Battaïa, ISAESUPAERO, France
 Valeria Borodin, LIMOS, France
 Marin Bougeret, LIRMM, France
 Stéphane DauzèrePérès, LIMOS, France
 Boris Detienne, INRIA Realopt, France
 Klaus Jansen, TU Kiel University, Germany
 Rodolphe Giroudeau, LIRMM, France
 Idir Hamaz, LAAS, France
 Ben Hermans, ORSTAT, KU Leuven, Belgium
 Laurent Houssin, LAAS, France
 Roel Leus, ORSTAT, KU Leuven, Belgium
 Erik Mühmer, RWTH Aachen University, Germany
 Widad Naji, GSCOP, France
 Margaux Nattaf, LAAS, France
 Michael Poss, LIRMM, France
 Lars Rohwedder, TU Kiel University, Germany
 Maxime Savaro, LIRMM, France
 Guopeng Song, ORSTAT, KU Leuven, Belgium
 Sebastian Stiller, TU Braunschweig, Germany
 Kim Thang, IBISC, France
Sponsors
Dernière mise à jour le 27/04/2017