Retour au site du LAAS-CNRS

Mots-Clés / Keywords

Integer linear programming; Dominance conditions; Single machine scheduling;

Abstract

This work focuses on the interests of interval analysis in scheduling. The analysis of intervals considers the order relation (Allens algebra) among the execution intervals of the tasks (or their processing time intervals) in order to deduce useful problem properties. For several kinds of scheduling problems, we particularly show how interval analysis allows defining dominance-based optimality conditions or sufficient conditions of feasibility, which characterize remarkable sets of schedules. Using these conditions, taking an interest in some one machine scheduling problems, we establish new and efficient integer-linear-programming formulations. Since the dominance conditions are relatively insensitive to variations of schedule parameters, we also show the interest of such conditions for characterizing a set of robust schedules. We also present some other works also based on interval analysis.

Résumé

Ce travail s'attache à décrire l'intérêt de l'analyse d'intervalles en ordonnancement. L'analyse d'intervalles considère les relations d'ordres existantes (algèbre de Allen) entres certains intervalles caractéristiques des tâches à ordonnancer. On montre comment, pour certains problèmes particuliers, elle permet de définir des conditions de dominance ou des conditions suffisantes d'optimalité, caractérisant des ensembles remarquables de solutions. Dans le cas de certains problèmes à une machine réputés difficiles, nous montrons comment de telles conditions peuvent être utiles pour déduire des nouvelles formulations de programmation linéaire en nombres entiers très efficaces. De plus, les conditions étant relativement indépendantes des valeurs numériques du problème, on montre aussi leur intérêt pour la caractérisation d'ensembles flexibles et robustes de solutions. D'autres travaux seront également évoqués dans lesquels la notion d'intervalle est centrale.

Mots-Clés / Keywords

Ordonnancement; Programmation linéaire en nombres entiers; Conditions de dominance; Incertitudes; Scheduling; Integer linear programming; Dominance conditions; Uncertainty;

Abstract

We define the resource-constrained activity insertion problem with minimum and maximum time lags. The problem aims at inserting a single activity in a partial schedule while preserving its structure represented through resource flow networks and minimizing the makespan increase caused by the insertion. We show that finding a feasible insertion position that minimizes the project duration is NP-hard in the general case. When only minimum time lags are considered and when activity durations are strictly positive, we show the problem is polynomially solvable, generalizing previously established results on activity insertion for the standard resource-constrained project scheduling problem.

Mots-Clés / Keywords

Resource-constrained project scheduling; Minimum and maximum time lags; Activity insertion problem; Complexity;

Abstract

In this paper, a new schedule generation scheme for resource-constrained project scheduling problems is proposed. Given a project scheduling problem and a priority rule, a schedule generation scheme determines a single feasible solution by inserting one by one each activity, according to their priority, inside a partial schedule. The paper proposes a generation scheme that differs from the classic ones in the fact that it allows to consider the activities in any order, whether their predecessors have already been scheduled or not. Moreover, activity insertion is performed so that delaying some already scheduled activities is allowed. The paper shows that this strategy remains polynomial and often gives better results than more classic ones. Moreover, it is also interesting in the fact that some priority rules, which are quite poor when used with classic schedule generation schemes, become very competitive with the proposed schedule generation scheme.

Mots-Clés / Keywords

Project scheduling; Schedule generation scheme; Activity insertion;