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 Configuration-LP 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 2-approximation 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 configuration-LP 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 configuration-LP. 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 non-constant 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 P-hard 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 NP-hard, the robust problems are frequently higher in the polynomial hierarchy, and, that combinatorial problems often require a two-stage 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 two-stage 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 Primal-Dual Algorithms with Configuration Linear Programs

    In the talk, we present a primal-dual 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 primal-dual 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, Energy-Efficient 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 best-known approximation guarantees in offline setting.

  • 15:30 - 16:15 Valeria Borodin - Service level in stochastic 2-machine permutation flow shop scheduling with random processing timesµ
    Stochastic scheduling problems, in which job processing times are supposed to be non-deterministic, are usually able to meet more accurately industrial realities than their deterministic counterparts. In this talk, we focus on the stochastic two-machine permutation flow-shop 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ère-Pé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, ISAE-SUPAERO, France
  • Christian Artigues, LAAS, France
  • Olga Battaïa, ISAE-SUPAERO, France
  • Valeria Borodin, LIMOS, France
  • Marin Bougeret, LIRMM, France
  • Stéphane Dauzère-Pé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, G-SCOP, 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

ANR

Dernière mise à jour le 27/04/2017