Journées Franciliennes de Recherche Opérationnelle
ROADEF




Retour

journee.html

Programme de la 24-ème journée JFRO

LE VENDREDI 24 SEPTEMBRE 2010

Sur le thème

Ordonnancement sans temps mort et ordonnancement sans attente

A L’Université Paris 6
Laboratoire d’informatique de Paris 6 (Tour 25-26, salle 105)
4 place Jussieu 75252 Paris cedex 05

Plan d’accès Jussieu

Inscription : merci de remplir le formulaire d’inscription



9h30-10h Accueil des participants
10h-11h30

Ordonnancement sans temps mort et nouveaux problèmes associés



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.

11h30-11h45 Pause
11h45-12h15

Single machine scheduling with no idle time and release dates to minimize a regular criterion


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.

12h15-14h15 Pause déjeuner
14H15-14h45



Professeur Alain Quilliot
LIMOS, Université Blaise Pascal, Clermont-Ferrand


14H45-15h15

Polynomial Time Algorithms for Minimum Energy Scheduling



Christoph Dürr
Chargé de recherche au CNRS
LIX, Ecole Polytechnique


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.

15h15-15h30 Pause
15h30-16h00

No-Idle Scheduling of a Single-Machine to Minimize the Maximum Lateness



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.

16h00-16h30

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.