Professeur Philippe Chrétienne
LIP6, Université Pierre et Marie Curie

Dans cette présentation, nous introduisons d’abord la contrainte d’absence de temps mort dans l’activité d’une ressource et nous donnons quelques exemples justifiant sa prise en compte. Nous nous intéressons ensuite au problème sans temps mort à une machine. Après avoir évoqué certains aspects concernant la complexité de ce problème, nous présentons quelques propriétés générales facilitant la résolution de certains problèmes et nous donnons quelques exemples de sous- problèmes polynomiaux. La dernière partie concerne le problème sans temps mort à m machines identiques. Nous considérons d’abord le cas où les séquences de jobs exécutés par les machines sont fixées. Nous montrons ensuite que certains algorithmes polynomiaux pour le cas classique s’étendent à un coût polynomial près au cas sans temps mort. Nous concluons avec certains problèmes ouverts et quelques perspectives.

Antoine Jouglet
UMR CNRS 6599 HEUDIASYC,
Université de Technologie de Compiègne

We address the one-machine scheduling problem with release dates, in which the machine is subject to the non-idling constraint, i.e. no intermediate idle time is permitted between the jobs processed by the machine. The objective is to minimize a regular objective function. We describe a constraint programming approach for solving this type of problem exactly. Some necessary and/or sufficient conditions for obtaining non-idling semi-active, active and optimal schedules are described.We propose some propagation rules based on these properties. As an application, we apply the proposed method to the total (weighted) completion time problem, and we provide some experimental results to illustrate its effectiveness.

The aim of power management policies is to reduce the amount of energy consumed by computer systems while maintaining satisfactory level of performance. One common method for saving energy is to simply suspend the system during the idle times. No energy is consumed in the suspend mode. However, the process of waking up the system itself requires a certain fixed amount of energy, and thus suspending the system is beneficial only if the idle time is long enough to compensate for this additional energy expenditure. In the specific problem studied in the paper, we have a set of jobs with release times and deadlines that need to be executed on a single processor. Preemptions are allowed. The processor requires energy L to be woken up and, when it is on, it uses one unit of energy per one unit of time. It has been an open problem whether a schedule minimizing the overall energy consumption can be computed in polynomial time. We solve this problem in positive, by providing an O(n^5)-time algorithm. In addition we provide an O(n^4)-time algorithm for computing the minimum energy schedule when all jobs have unit length.

Professeur Imed Kacem
LITA, Université Paul Verlaine, Metz

This work aims to design efficient approximation algorithms for the single-machine maximum lateness minimization problem when jobs have different release dates and tails (or delivery times) under the no-idle time assumption (i.e., the schedule cannot contain any idle-time between two consecutive jobs on the machine). Our work is motivated by interesting industrial applications to the production area (see for example Chrétienne, Dis App Math). Our analysis shows that modifications of the classical algorithms of Potts and Schrage can lead to the same worst-case performance ratios obtained for the relaxed problem without the no-idle time constraint. Then, we extend the result developed by Mastrolilli for such a relaxed problem and we propose a polynomial time approximation scheme with efficient running time. Remark : the authors of this works are Imed Kacem and Hans Kellerer.

No-wait flowshop problem with mixed batching machine

Ammar Oulamara
LORIA, Université de Nancy

This presentation deals with the problem of tasks scheduling in a no-wait flowshop consisting of two mixed batching machines. Each task has to be processed by both machines. All tasks visit the machines in the same order. Batching machines can process several tasks in batch so that all tasks of the same batch start and complete together. The processing time of a batch on the first batching machine is equal to the maximal processing time of the tasks in this batch, and on the second batching machine is equal to the sum of the processing time of tasks in this batch. We assume that the capacity of any batch on the first machine is bounded, and when a batch is completed on this machine should immediately transferred to second machine. The aim is to make batching and sequencing decisions so that the makespan is minimized.