Heuristic procedures for resource—constrained project scheduling with minimal and maximal time lags: the resource—levelling and minimum project—duration problems

ABSTRACT

The paper presents heuristics for two types of resource—constrained project-scheduling problems: the problem of levelling the resources consumption and the minimum project—duration problem. Both minimal and maximal time lags between the start of successive activities of the project in question are permitted. Such a project can be modelled by an activity-on-node network containing cycles. For the resource—levelling problem with maximal time lags, neither exact algorithms nor heuristic procedures have been proposed so far. Two different heuristic procedures are presented. The sequential or direct method processes the nodes or respectively activities of the cyclic project network successively without scheduling the strong components of the network separately. The contraction method firstly finds a feasible subschedule for each strong component of the cyclic network and secondly replaces each strong component by a single node. The resulting (contracted) acyclic network is treated by the direct method. An empirical analysis shows that for the minimum project—duration problem, the contraction method is markedly superior to the direct method. For the resource—levelling problem, both approaches behave similarly.

RÉSUMÉ

Ce papier présente des méthodes heuristiques pour deux types de problèmes de planification de projets: la question du niveau des ressources nécessaires et la durée minimale du projet. Des fenêtres temps minimale et maximale pour le démarrage des activités sont autorisées. Un tel projet peut se modéliser comme un graphe d'activité avec des cycles. Pour la question du niveau des ressources avec borne supérieure de temps de démarrage des activités, aucun algorithme exact, ni même d'heuristique n'ont été proposés jusqu'à maintenant. Deux heuristiques différentes sont présentées. La méthode séquentielle, ou méthode directe, traite les nœuds ou les activités du graphe, successivement, sans ordonner les composantes fortes du graphe séparément. La méthode de contraction trouve d'abord un ordonnancement pour chaque composante forte du graphe avec cycles et ensuite remplace chacune de ces composantes par un nœud unique. Le graphe acyclique (contracté) résultant est ensuite traité par la méthode directe. Une analyse empirique montre que pour le problème de la durée minimale, la méthode de contraction est nettement supérieure à la méthode directe. Pour les niveaux de ressources les deux méthodes se comportent de façon similaire.

KEY WORDS:

• project scheduling
• minimal and maximal time lags
• activity-on-node networks
• resource constraints

MOTS-CLÉS:

• planification de projets
• intervalle de début de tâches
• graphes d'activités
• contraintes de resources