Search

International audience; Several algorithms for finding a lower bound on the makespan for the Resource Constrained Project Scheduling Problem (RCPSP) were proposed in the literature. However, fast computable lower bounds usually do not provide the best estimations and the methods that obtain better bounds are mainly based on the cooperation between linear and constraint programming and therefore are time-consuming. In this paper, a new pseudo-polynomial algorithm is proposed to find a makespan lower bound for RCPSP with time-dependent resource capacities. Its idea is based on a consecutive evaluation of pairs of resources and their cumulated workload. Using the proposed algorithm, several bounds for the PSPLIB benchmark were improved. The results for industrial applications are also presented where the algorithm could provide good bounds even for very large problem instances.

Volume 2020, Issue 12, The scheduling of activity sequences under resource constraints, also known as Resource-Constrained Project Scheduling Problem (RCPSP), is a well-known optimization problem that consists in finding an activity execution schedule that minimizes the total duration of the considered sequence. This problem is generally tackled with heuristic and meta-heuristic methods. This paper proposes a different approach based on artificial neural networks, used as decision tools, and machine learning. Moreover, it is shown that such methodology is able to provide good and fast activity execution schedules., Die Planung von ressourcenbeschränkten Aktivitätsfolgen, bekannt als das ressourcenbeschränkte Projektplanungsproblem, ist ein bekanntes Optimierungsproblem, das darin besteht, einen Ausführungsplan zu finden, der die Gesamtdauer der betrachteten Aktivitätsfolge minimiert. Dieses Problem wird im Allgemeinen mit heuristischen und meta-heuristischen Methoden gelöst. In diesem Beitrag wird ein alternativer Lösungsansatz vorgestellt, der eine Entscheidungsstrategie umfasst, die auf künstlichen neuronalen Netzen und maschinellem Lernen basiert. Darüber hinaus wird gezeigt, dass ein solcher Ansatz in der Lage ist, für Aktivitätsfolgen gute Ausführungspläne in kurzer Zeit zu generieren.

The production of semiconductors for applications in microelectronics is operated through photo-lithographic and chemical processes whereof Chemical Vapor Deposition (CVD) technology is one of the most used. CVD processes need to operate in furnaces under controlled atmosphere and, every time the furnace is accessed from the external environment, a purging time is needed to restore the prescribed atmosphere. The optimisation of the utilisation of the furnaces depends on the sequencing of loading and unloading operations entailing the need to disturb the controlled atmosphere. We propose the use of a disaggregated time formulation based on step variables to model a scheduling problem aiming at identifying the optimal sequence of operations and supporting the definition of optimal dispatching policies.

International audience; In this paper, we consider the weekly scheduling problem of activities within one of the research facilities of the French Alternative Energies and Atomic Energy Commission (CEA in short for French). To better represent this problem we propose a new variant of the multi-skill project scheduling problem (MSPSP) involving partial preemption. We describe the new MSPSP variant and we present two formulations for the problem: one using mixed-integer linear programming (MILP) and a second one using constraint programming (CP). Computational experiments on realistic data are carried out and discussed.

We consider one approach to formalize the Resource-Constrained Project Scheduling Problem (RCPSP) in terms of combinatorial optimization theory. The transformation of the original problem into combinatorial setting is based on interpreting each operation as an atomic entity that has a defined duration and has to be resided on the continuous time axis meeting additional restrictions. The simplest case of continuous-time scheduling assumes one-to-one correspondence of resources and operations and corresponds to the linear programming problem setting. However, real scheduling problems include many-to-one relations which leads to the additional combinatorial component in the formulation due to operations competition. We research how to apply several typical algorithms to solve the resulted combinatorial optimization problem: enumeration including branch-and-bound method, gradient algorithm, random search technique.

International audience; There are not many research works dedicated to the optimization of scheduling activities in research laboratories. In this paper, we consider the weekly scheduling problem of activities within a nuclear research laboratory. We show that this problem can be modeled as a preemptive multi-skill variant of the Resource-Constraint Project Scheduling Problem where the preemption of some activities is allowed and induces a penalty every time the activity is preempted. We propose two integer linear programs to find exact solutions. Computational tests are carried out and described.

International audience; This article proposes an extension of the Resource Constrained Project Scheduling Problem: the multi-site RCPSP with resource pooling between several sites. This extension considers new constraints for the RCPSP like transportation times and choice of the site where tasks are performed. A linear program of this problem is given. Four approximate methods are described: Local Search, Simulated Annealing and Iterated Local Search with two different acceptance criteria: Simulated Annealing type acceptance criterion and Better Walk acceptance criterion. We compare the results obtained with each method. The best results are obtained with Simulated Annealing and Iterated Local Search metaheuristics.

Doctoral Program in Industrial and Systems Engineering, Project management involves onetime endeavours which demand for getting it right the first time. Also, project scheduling, being one of the most modelled project management process stages, still faces a wide gap separating theory from practice. Demanding computational models, and their consequent call for simplification, divert the implementation of such models in project management tools from the actual day to day project management process. Special focus is being made to the robustness of the generated project schedules facing the omnipresence of uncertainty. An "easy" way out is to add, more or less cleverly calculated, time buffers that always result in project duration increase and correspondingly, in increased costs. A better approach to deal with uncertainty can be to explore slack that might exist in a given project schedule, even more when a non-optimal schedule is used, which is what usually happens in practice. The combination of such approach with recent advances in modelling resource allocation and scheduling techniques, to cope with the increasing flexibility in resources, is a promising line of research, in order to generate more adequate project management tools. "Flexible resource profiles Resource Constraint Project Scheduling Problem" (FRCPSP) formulations are a step in this direction but a distinct approach can be followed, considering that, apart from being flexibly allocated or not, resources are themselves flexible by nature. More specifically, when renewable resources are considered, their capacity to perform work in a time unit (e.g. a day), which is considered to be one unit for each resource in traditional models, can be increased so that they can perform additional work in a time unit, or it can be decreased with the consequent reduction on the performed work. In reality, this flexibility is frequently considered by project managers. The objective here is to use this possibility so that, when combined with the slack that some activities have in a specific schedule, deviations that might occur during a project's execution can be absorbed. In the most critical case, in which a critical activity (activity without slack) will have its duration increased, the strategy is basically to slow down non-critical activities (activities with slack), by putting their resources in a decreased work mode, so that the critical activity, which is about to have an increase in its duration delaying the whole project, can still be executed within time by using resources in an increased working mode. This thesis analyses this combination, its consequences and limitations and proposes models to generate and enhance starting (baseline) schedules that can take a greater advantage of this approach., A Gestão de Projetos consiste num esforço único que exige que se acerte logo à primeira tentativa. Além disso, o escalonamento de projetos, apesar de ser uma das etapas com mais modelação no processo de gestão de projetos, ainda apresenta uma grande divergência entre a teoria e a prática. Os modelos computacionais exigentes, e o consequente apelo para a sua simplificação, desviam a sua implementação dos processos de gestão de projetos reais. Especial atenção tem sido dada para a robustez dos cronogramas produzidos que enfrentam a omnipresença da incerteza. Uma forma "fácil" de resolver o problema é adicionar buffers temporais, mais ou menos habilmente calculados, que resultam sempre num aumento da duração do projeto e, por consequência, do seu custo. Uma abordagem melhor para lidar com a incerteza pode passar por explorar a folga que possa existir num determinado cronograma, especialmente quando é usado um cronograma não-ótimo, o que geralmente acontece na prática. A combinação de tal abordagem com os recentes avanços na modelação da alocação de recursos e das técnicas de escalonamento, para lidar com o aumento da flexibilidade dos recursos, são uma linha de investigação promissora para se obterem ferramentas de escalonamento de projetos mais adequadas. As formulações FRCPSP ( Flexible resource profile Resource Constraint Project Scheduling Problem) são um passo nessa direção, mas uma abordagem distinta pode ser seguida considerando que, apesar de poderem ou não ser alocados de forma flexível, os recursos são, eles próprios, flexíveis. Mais especificamente, considerando recursos renováveis, a sua capacidade para executar trabalho numa unidade de tempo, considerada unitária nos modelos tradicionais, pode ser aumentada, de forma a executarem trabalho adicional numa unidade de tempo, ou diminuída, com a consequente redução do trabalho realizado. Na realidade, esta flexibilidade é muitas vezes considerada pelos gestores de projeto. O objetivo aqui é usar esta possibilidade para que, quando combinada com a folga existente em algumas atividades num cronograma, os desvios que ocorram durante a execução do projeto possam ser absorvidos. No caso mais crítico, em que uma atividade crítica (atividade sem folga) tenha a sua duração aumentada, a estratégia consiste em desacelerar atividades não críticas (atividades com folga), colocando os seus recursos num modo de trabalho diminuído, para que a atividade crítica, que está prestes a aumentar a sua duração, ainda possa ser executada dentro do tempo, usando os seus recursos num modo de trabalho aumentado. Esta tese analisa esta combinação, as suas consequências e limitações e propõe alguns modelos para gerar e melhorar o cronograma inicial ( baseline) de modo a melhor aproveitar esta abordagem.

The Resource-Constrained Project Scheduling Problem (RCPSP) is known to be the framework that can deal with several types of scheduling problems. A number of RCPSP models exist where various constraints were relaxed or added. We develop a general project scheduler based on the framework of RCPSP/τ model which can be applied to various types of scheduling problems. Our scheduler solves such problems as the PSPLIB and the school timetable generation problem by a slight modification in its procedure. In this paper, we solve the nurse scheduling problem (NSP) by our previously proposed scheduler. Especially we deal with 3-shifts NSP of which data is original. Our scheduler can obtain the fusible solution in which all our constraints are satisfied.

International audience; This article proposes an extension of the Resource Constrained Project Scheduling Problem: the Multi-Site RCPSP with resource pooling between several sites. This extension considers new constraints for the RCPSP like transportation times and choice of the site where tasks are performed. A linear program of this problem is given. Four approximate methods are described: local search, simulated annealing and Iterated Local Searches with two different acceptance criteria: Simulated Annealing type acceptance criterion and Better Walk acceptance criterion. We compare the results obtained with each method. Simulated Annealing and Iterated Local Searches give good results.

Project Management involves onetime endeavors that demand for getting it right the first time. On the other hand, project scheduling, being one of the most modeled project management process stages, still faces a wide gap from theory to practice. Demanding computational models and their consequent call for simplification, divert the implementation of such models in project management tools from the actual day to day project management process. Special focus is being made to the robustness of the generated project schedules facing the omnipresence of uncertainty. An "easy" way out is to add, more or less cleverly calculated, time buffers that always result in project duration increase and correspondingly, in cost. A better approach to deal with uncertainty seems to be to explore slack that might be present in a given project schedule, a fortiori when a non-optimal schedule is used. The combination of such approach to recent advances in modeling resource allocation and scheduling techniques to cope with the increasing flexibility in resources, as can be expressed in "Flexible Resource Constraint Project Scheduling Problem" (FRCPSP) formulations, should be a promising line of research to generate more adequate project management tools. In reality, this approach has been frequently used, by project managers in an ad-hoc way.

[EN] Scheduling problems is one of the core areas in the planning and development of any project, with a wide applicability to real-world situations. Due to the high complexity of these problems, the solving process is often based on metaheuristics techniques, so that the evaluation of these methods is empirical. Therefore benchmarks, which provide a set of test cases to assess the behavior of algorithms, are generated. This paper extends the PSPLIB library. This extension incorporates to each instance of RCPSP (Resource Constrained Project Scheduling Problem), a realistic mathematical model of energy consumption. This proposal provides an alternative to the current trend in the feld of optimization and manufacturing that requires the inclusion of components and methods that reduce the environmental impact in the process of decision making. Finally a new optimality criterion is proposed to compare dierent search techniques. The PSPLIB-ENERGY is available at http://gps.webs.upv.es/psplib-energy/, [ES] Los problemas de scheduling constituyen una de las ´areas centrales en la planificaci´on y desarrollo de cualquier proyecto, con una gran aplicabilidad a situaciones del mundo real. Debido a la gran complejidad que habitualmente presentan estos problemas, su resoluci´on suele basarse en m´etodos metaheur´ısticos de optimizaci´on, de forma que la evaluaci´on de estos m´etodos es emp´ırica. Por esta raz´on se generan benchmarks, que proveen de un conjunto de casos de prueba que permiten evaluar el comportamiento de los algoritmos que se desarrollan. En este art´ıculo se extiende la librer´ıa PSPLIB. Esta extensi´on consiste en incorporar a cada instancia del RCPSP (Resource Constrained Project Scheduling Problem), un modelo matem´atico realista de consumo de energ´ıa. Esta propuesta brinda una alternativa a la tendencia actual en el campo de la optimizaci´on y la manufactura que demanda la inclusi´on de componentes y m´etodos que reduzcan el impacto ambiental en el proceso de toma de decisiones. Finalmente se propone un nuevo criterio de optimalidad para comparar las diferentes t´ecnicas de b´usqueda. La PSPLIB-ENERGY est´a disponible en http://gps.webs.upv.es/psplib-energy/., Este trabajo ha sido parcialmente financiado por el proyecto de Investigación TIN2013-46511-C2-1-P.

Home care services, is a generic term that gathers different kind of care: provider, agency, and organization. In France, the most important part of the in-home care is performed by HAD (Hospitalization At Home). The HAD concept is defined by decree. The HAD has to provide only complex care in the patient’s home for 24 motives. HAD are hospitals and have to ensure continuity of care for their patients. Our researches focus on the operation management for home care services. This problem is complex; it needs to solve sub-problems known to be NP - hard. In this work, this problem is studied at the operational level in design of tours of caregivers. The approach followed is based on three essential stages. Firstly, we study the health system and the home care structures in France. At the end of this step, we summarize the outcome obtained of the regional project Organization of Home Care Service (Organisation des Soins A Domicile : OSAD) on the home care structures in the Rhône-Alpes region (France). The second step gathers scientific literature about home care management, particularly about problems of management and planning of activities and human resources in the home care structures. This work leads to design a classification in order to management activities issues in home care structures. Based on this classification, we define three complexity axes of the operation management in home care problem, i.e. (i) the rate of the number of care activities per caregiver, (ii) dependency level between the patients’ activities and (iii) the environmental level. In the third stage, we suggest a set of mathematical approaches and tools for solving the problem of caregivers’ tours. Two MIPL model are developed, the first is based on a Traveling Salesman Problem (TSP) with coordination between the caregivers and the second on RCPSP (Ressources Constrained Project Scheduling Problem). Because the both previous models are time consuming, we suggest an original heuristic to solve the TSP coordinated problem, to resolve the care management activities in home care services, L’hospitalisation hors les murs est une expression générique qui désigne toutes les formes de structures accueillant des patients pour une prise en charge longue et régulière nécessitant des soins complexes. Les structures hors les murs doivent assurer une prise en charge sure et d’une qualité au moins identique à celle fourni par l’hôpital, tout en contribuant à la diminution des coûts de la prise en charge. D’où la nécessité d’une gestion efficiente des activités des soignants et des ressources humaines. Dans ce travail de recherche, l’intérêt est porté à la problématique générale de gestion des activités de soins en Hospitalisation À Domicile (HAD). Il s’agit d’une problématique très complexe, car elle vise à résoudre simultanément des sous-problèmes réputés NP – difficiles. Dans cette thèse, nous étudions cette problématique au niveau opérationnel de la conception des tournées des soignants. La démarche adoptée pour ce travail de recherche se base sur trois étapes essentielles. Nous commençons par une étude sur le système de santé et les structures d’HAD en France, tout en mettant en claire les facteurs essentiels de leur fonctionnement. Cette étape sera clôturée par une étude du fonctionnement des systèmes d’HAD dans la région Rhône-Alpes, en se basant sur les retours du projet régional Organisation des Soins A Domicile (OSAD). La deuxième étape concerne les problématiques de gestion et la planification des activités de soins et des ressources humaines en HAD. Ce travail conduira à l’élaboration d’une classification des problématiques de la gestion des activités en HAD. En se basant sur la classification identifiée précédemment, nous définissons, les axes de complexité de ce problème : (i) le nombre d’activités de soins par soignant, (ii) la dépendance temporelle entre les activités des patients et (iii) la dimension environnementale. Ensuite, nous proposons un ensemble d’approches et d’outils pour la résolution de la problématique des tournées d’infirmiers en HAD, sous différentes contraintes liées à la réalisation des soins et en particulier aux contraintes de dépendances temporelles. Pour répondre à l’ensemble des contraintes et exigences de performance, nous développons une heuristique originale permettant une résolution en un temps compatible avec les contraintes de mise en oeuvre, pour des instances de grande taille

This thesis is a study within the framework of the Helimaintenance project; a European project approved by the French aerospace valley cluster that aims to establish a center for civil helicopter maintenance which is also able to make R&D projects in the field. Our work consists of integrating uncertainties into both tactical and operational multiresources, multi-projects planning and dealing with Rough Cut Capacity Planning, Resource Leveling Problem and Resource Constraint Project Scheduling Problem under uncertainties. Uncertainty is modelled within a fuzzy/possibilistic approach instead of a stochastic approach since very limited data is available in our case of study. Three types of problems are referred in this study which are the Fuzzy Rough Cut Capacity Problem (FRCCP), the Fuzzy Resource Leveling Problem (FRLP) and the Fuzzy Resource Constraint Project Scheduling Problem (RCPSP). Moreover, a Genetic Algorithm and a Parallel SGS are provided to solve the FRLP and FRCPSP problems, respectively. A Simulated Annealing is provided to solve the FRCCP problem., Cette thèse entre dans le cadre du projet Hélimaintenance ; un project labellisé par le pôle de compétitivité Français Aérospace-Valley, qui vise à construire un centre dédié à la maintenance des hélicoptères civils qui soit capable de lancer des travaux en R&D dans le domaine. Notre travail consiste à prendre en considération les incertitudes dans la planification et l'ordonnancement de projets et résoudre les problèmes Rough Cut Capacity Planning, Resource Leveling Problem et Resource Constraint Project Scheduling Problem sous incertitudes. L'incertitude est modélisée avec l'approche floue/possibiliste au lieu de l'approche stochastique ce qui est plus adéquat avec notre cas d'étude. Trois types de problèmes ont été définis dans cette étude à savoir le Fuzzy Rough Cut Capacity Problem (FRCCP), le Fuzzy Resource Leveling Problem (FRLP) et le Fuzzy Resource Constraint Project Scheduling Problem (RCPSP). Un Algorithme Génétique et un Algorithme "Parallel SGS" sont proposés pour résoudre respectivement le FRLP et le FRCPSP et un Recuit Simulé est proposé pour résoudre le problème FRCCP.

This thesis is a study within the framework of the Helimaintenance project; a European project approved by the French aerospace valley cluster that aims to establish a center for civil helicopter maintenance which is also able to make R&D projects in the field. Our work consists of integrating uncertainties into both tactical and operational multiresources, multi-projects planning and dealing with Rough Cut Capacity Planning, Resource Leveling Problem and Resource Constraint Project Scheduling Problem under uncertainties. Uncertainty is modelled within a fuzzy/possibilistic approach instead of a stochastic approach since very limited data is available in our case of study. Three types of problems are referred in this study which are the Fuzzy Rough Cut Capacity Problem (FRCCP), the Fuzzy Resource Leveling Problem (FRLP) and the Fuzzy Resource Constraint Project Scheduling Problem (RCPSP). Moreover, a Genetic Algorithm and a Parallel SGS are provided to solve the FRLP and FRCPSP problems, respectively. A Simulated Annealing is provided to solve the FRCCP problem., Cette thèse entre dans le cadre du projet Hélimaintenance ; un project labellisé par le pôle de compétitivité Français Aérospace-Valley, qui vise à construire un centre dédié à la maintenance des hélicoptères civils qui soit capable de lancer des travaux en R&D dans le domaine. Notre travail consiste à prendre en considération les incertitudes dans la planification et l'ordonnancement de projets et résoudre les problèmes Rough Cut Capacity Planning, Resource Leveling Problem et Resource Constraint Project Scheduling Problem sous incertitudes. L'incertitude est modélisée avec l'approche floue/possibiliste au lieu de l'approche stochastique ce qui est plus adéquat avec notre cas d'étude. Trois types de problèmes ont été définis dans cette étude à savoir le Fuzzy Rough Cut Capacity Problem (FRCCP), le Fuzzy Resource Leveling Problem (FRLP) et le Fuzzy Resource Constraint Project Scheduling Problem (RCPSP). Un Algorithme Génétique et un Algorithme "Parallel SGS" sont proposés pour résoudre respectivement le FRLP et le FRCPSP et un Recuit Simulé est proposé pour résoudre le problème FRCCP.

En este artículo se presenta un algoritmo heurístico híbrido para resolver el Problema de Programación de Proyectos con Recursos Limitados (RCPSP). El algoritmo diseñado combina elementos de Recocido Simulado y Búsqueda en Múltiples Vecindarios. Adicionalmente, utiliza el método denominado Justificación, el cual es un método diseñado específicamente para el RCPSP. Para evaluar el desempeño del algoritmo se realizó un análisis estadístico para el ajuste de parámetros. Los resultados se comparan con los reportados en la literatura científica. This paper presents a hybrid heuristic algorithm for solving the Resource Constrained Project Scheduling Problem (RCPSP). The algorithm designed combines elements of Simulated Annealing and Variable Neighborhood Search. Additionally, it uses the method called Justification, which is a method designed specifically for the RCPSP. To evaluate the performance of the algorithm, a statistical analysis for tuning the parameters has done. The results were compared with those reported in the scientific literature.

Submitted by Manuel Brandão (mbrandao@estsp.ipp.pt) on 2014-06-04T10:44:46Z No. of bitstreams: 1 ART_JMendes_2009_CIDEM.pdf: 98142 bytes, checksum: ac13365cd2e01b09042478a407f1a014 (MD5) Approved for entry into archive by Luís Miguel Durão (lmd@isep.ipp.pt) on 2014-06-04T17:33:14Z (GMT) No. of bitstreams: 1 ART_JMendes_2009_CIDEM.pdf: 98142 bytes, checksum: ac13365cd2e01b09042478a407f1a014 (MD5) Approved for entry into archive by Ana Rebelo (amsr@isep.ipp.pt) on 2014-06-06T11:26:33Z (GMT) No. of bitstreams: 1 ART_JMendes_2009_CIDEM.pdf: 98142 bytes, checksum: ac13365cd2e01b09042478a407f1a014 (MD5) Made available in DSpace on 2014-06-06T11:26:33Z (GMT). No. of bitstreams: 1 ART_JMendes_2009_CIDEM.pdf: 98142 bytes, checksum: ac13365cd2e01b09042478a407f1a014 (MD5) Previous issue date: 2009

The resource constrained project scheduling problem (RCPSP) is a difficult problem in combinatorial optimization for which extensive investigation has been devoted to the development of efficient algorithms. During the last couple of years many heuristic procedures have been developed for this problem, but still these procedures often fail in finding near-optimal solutions. This paper proposes a genetic algorithm for the resource constrained project scheduling problem. The chromosome representation of the problem is based on random keys. The schedule is constructed using a heuristic priority rule in which the priorities and delay times of the activities are defined by the genetic algorithm. The approach was tested on a set of standard problems taken from the literature and compared with other approaches. The computational results validate the effectiveness of the proposed algorithm.

Neste artigo apresenta-se um algoritmo genético para o Problema do Sequenciamento de Projectos com Recursos Limitados (RCPSP). A representação cromossómica utilizada baseia-se em chaves aleatórias. O sequenciamento das actividades é feito com recurso a uma heurística baseada em prioridades definidas pelo algoritmo genético. A heurística gera sequenciamentos activos parametrizados. O algoritmo é testado num conjunto de problemas padrão retirados da literatura da especialidade e é comparado com outras abordagens. Os resultados computacionais validam o bom desempenho do algoritmo em termos de qualidade da solução. This paper presents a genetic algorithm for the Resource Constrained Project Scheduling Problem (RCPSP). The chromosome representation of the problem is based on random keys. The schedule is constructed using a heuristic priority rule in which the priorities activities are defined by the genetic algorithm. The heuristic generates parameterized active schedules. The approach is tested on a set of standard problems taken from the literature and compared with other approaches. The computation results validate the effectiveness of the proposed algorithm.

States-of-the-art of the RCPSP and of constraint programming-linear programming hybrid methods.Hybrid approaches of CP and ILP for the RCPSP: lower bounds computation by CP-based lagrangian relaxation; CP-based column generation and CP-based cutting-plane generation.Application of a generic, exact, and non-tree search method, Resolution Search, proposed by Vlasek Chvatal. Links with dynamic backtracking and nogood learning approaches in CP., La version classique du problème d'ordonnancement de projet à contraintes de ressources (RCPSP) consiste à trouver un ordonnancement, de durée minimale, des activités d'un projet entrant en compétition sur l'usage de ressources renouvelables, cumulatives et disponibles en quantité limité. La réputation d'extrême difficulté du RCPSP a mené nombre de chercheurs à proposer de nouvelles méthodes de résolution exacte toujours plus performantes pour ce problème. Malgré cela, les instances de tailles réelles, qui se recontrent fréquemment, par exemple dans la gestion de production industrielle, sont encore loins d'être résolues optimalement. Il est donc intéressant, en combinant les acquis des travaux précédents, en particulier en programmation par contraintes (PPC) et en programmation linéaire (PL), de se pencher sur des méthodes exactes innovantes ou encore de développer des procédures d'évaluation par défaut, pour permettre une meilleure estimation de la performance des heuristiques sur le RCPSP. Ce travail de thèse entre dans ce cadre.Dans un premier temps, nous nous attachons au calcul de bornes inférieures pour le RCPSP par relaxation lagrangienne. D'une part, nous cherchons à accélerer le calcul de la borne de Brucker et Knust (obtenue par hybridation de PPC et de génération de colonnes) en résolvant le programme linéaire sous-jacent par relaxation lagrangienne (méthodes de sous-gradient et de génération de contraintes). D'autre part, nous appliquons le même principe de relaxation lagrangienne, sur la formulation linéaire initiale de Mingozzi et al. dont est extraite la relaxation préemptive utilisée par Brucker et Knust. Une partie du problème se réduit alors, comme indiqué par Möhring et al., au calcul d'une coupe minimale dans un graphe. Nous étudions ensuite, un second type de bornes inférieures, obtenu par des méthodes de coupes basées sur les relaxations continues de deux formulations linéaires entières. Ces programmes linéaires sont au préalable resserés par des techniques éprouvées de propagation de contraintes, dont la règle globale du shaving. L'originalité de notre méthode repose essentiellement dans la génération des coupes qui sont, en grande partie, directement déduites des règles de propagation de contraintes.Enfin, nous proposons une méthode originale de résolution exacte pour le RCPSP, basée sur la procédure de Resolution Search de Chvàtal, une alternative aux méthodes de Branch-and-Bound classiques et qui se rapproche du Dynamic Backtracking en programmation par contraintes. Dans Resolution Search, l'espace de recherche ne se présente pas comme un arbre, puisqu'il s'agit, à chaque fois qu'un noeud terminal est rencontré, de rechercher par backtrakings successifs, les fixations minimales qui font de ce noeud un noeud terminal. L'ensemble des ces fixations est alors stocké de manière intelligente de façon à les exclure de l'espace de recherche. Resolution Search a été initialement développée pour la résolution de programmes linéaires en variables binaires, mais n'a semble-t'il jamais été employée dans le cadre de problèmes spécifiques.Dans le but de prouver son efficacité, nous commencons par l'appliquer basiquement à deux formulations linéaires en variables binaires pour le RCPSP et la comparons à une version tout aussi basique de Branch-and-bound. Nous en poursuivons l'étude en utilisant des règles de branchement et d'évaluation ayant déjà prouvé leur efficacité dans des implémentations classiques de méthodes arborescentes pour le RCPSP, telles que celles de Brucker et al., Carlier et Latapie, Demeulemeester et Herroelen.

The Resource Constrained Project Scheduling Problem (RCPSP) is NP-hard thus justifying the use meta-heuristics for its solution. This paper presents an evolutionary algorithm developed for the RCPSP problem. This evolutionary algorithm uses an alphabet based on random keys that makes easier its implementation while solving combinatorial optimization problems. Random keys allow the use of conventional genetic operators, what makes easier the adaptation of the evolutionary algorithm to new problems. To improve the method's performance, this evolutionary algorithm uses an initial population that is generated considering the information available for the instance. This paper studies the impact of using that information in the initial population. The computational experiments presented compare two types of initial population - the conventional one (generated randomly) and this new approach that considers the information of the instance., Fundação para a Ciência e a Tecnologia (FCT)

Project Management involves onetime endeavors that demand for getting it right the first time. On the other hand, project scheduling, being one of the most modeled project management process stages, still faces a wide gap from theory to practice. Demanding computational models and their consequent call for simplification, divert the implementation of such models in project management tools from the actual day to day project management process. Special focus is being made to the robustness of the generated project schedules facing the omnipresence of uncertainty. An "easy" way out is to add, more or less cleverly calculated, time buffers that always result in project duration increase and correspondingly, an increase in its cost. A better approach to deal with uncertainty seems to be to explore slack that might be present in a given project schedule especially when a non-optimal schedule is used. The combination of such approach to recent advances in modeling resource allocation and scheduling techniques to cope with the increasing flexibility in resources, as can be expressed in "Flexible Resource Constraint Project Scheduling Problem" (FRCPSP) formulations, should be a promising line of research to generate more adequate project management tools. In reality this approach is frequently used by project managers in an ad-hoc way.