Résumé : 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.

Résumé : 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.

Résumé : 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.

Résumé : No-Idle Scheduling of a Single-Machine to Minimize the Maximum Lateness

Résumé : 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.