A new any-order schedule generation scheme for resource-constrained project scheduling

Université de Toulouse, LAAS-CNRS, 7 avenue du Colonel Roche, 31077 Toulouse, France; briand@laas.fr

Received: 30 October 2006
Accepted: 14 February 2009

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.

Résumé

Dans cet article, un nouveau schéma de génération de solution est proposé pour les problèmes d'ordonnancement de projet sous contraintes de ressources. Considérant un problème d'ordonnancement et une règle de priorité donnée, un schéma de génération de solution détermine une solution faisable en insérant une par une chaque activité du projet, en fonction de leur priorité et des relations de précédence, dans un ordonnancement partiel. Le schéma de génération décrit dans cet article diffère des schémas classiques par le fait qu'il autorise l'insertion des activités dans n'importe quel ordre, indépendamment de leurs relations de précédence. De plus, lors de l'insertion d'une activité, le schéma autorise aussi de retarder des activités déjà ordonnancées, ce qui constitue une deuxième originalité. L'article montre que cette stratégie conduit souvent à de meilleurs résultats que ceux obtenus avec les schémas classiques, tout en conservant un temps de calcul polynomial. De plus, on montre que certaines règles de priorité, peu efficaces avec les schémas classiques, deviennent très compétitives avec ce nouveau schéma.