Cookies
O website necessita de alguns cookies e outros recursos semelhantes para funcionar. Caso o permita, o INESC TEC irá utilizar cookies para recolher dados sobre as suas visitas, contribuindo, assim, para estatísticas agregadas que permitem melhorar o nosso serviço. Ver mais
Aceitar Rejeitar
  • Menu
Publicações

Publicações por José Coelho

2021

An analysis of network and resource indicators for resource-constrained project scheduling problem instances

Autores
Vanhoucke, M; Coelho, J;

Publicação
COMPUTERS & OPERATIONS RESEARCH

Abstract
In the past decades, the resource on the resource-constrained project scheduling problem (RCPSP) has grown rapidly, resulting in an overwhelming amount of solution procedures that provide (near)-optimal solutions in a reasonable time. Despite the rapid progress, little is still known what makes a project instance hard to solve. Inspired by a previous research study that has shown that even small instances with only up to 30 activities is sometimes hard to solve, the current study provides an analysis of the project data used in the academic literature. More precisely, it investigates the ability of four well-known resource indicators to predict the hardness of an RCPSP instance. The study introduces a new instance equivalence concept to show that instances might have very different values for their resource indicators without changing any possible solution for this instance. The concept is based on four theorems and a search algorithm that transforms existing instances into new equivalent instances with more compact resources. This algorithm illustrates that the use of resource indicators to predict the hardness of an instance is sometimes misleading. In a set of computational experiment on more than 10,000 instances, it is shown that the newly constructed equivalent instances have values for the resource indicators that are not only different than the values of the original instances, but also often are better in predicting the hardness the project instances. It is suggested that the new equivalent instances are used for further research to compare results on the new instances with results obtained from the original dataset.

2019

Clash and dance Yourself

Autores
Canossa, H; Coelho, J; Paulino, F;

Publicação
ACM International Conference Proceeding Series

Abstract
The main goal of the conference is to promote the interest in the current digital culture and its intersection with art and technology as an important research field, and also to create a common space for discussion and exchange of new experiences. It seeks to foster greater understanding about digital arts and culture across a wide spectrum of cultural, disciplinary, and professional practices. To this end, many scholars, teachers, researchers, artists, comput-er professionals, and others who are working within the broadly defined areas of digital arts, culture and education across the world, submitted their innovative work to the conference. © 2019 ACM.

2022

An efficient genetic programming approach to design priority rules for resource-constrained project scheduling problem

Autores
Luo, JY; Vanhoucke, M; Coelho, J; Guo, WK;

Publicação
EXPERT SYSTEMS WITH APPLICATIONS

Abstract
In recent years, machine learning techniques, especially genetic programming (GP), have been a powerful approach for automated design of the priority rule-heuristics for the resource-constrained project scheduling problem (RCPSP). However, it requires intensive computing effort, carefully selected training data and appropriate assessment criteria. This research proposes a GP hyper-heuristic method with a duplicate removal technique to create new priority rules that outperform the traditional rules. The experiments have verified the efficiency of the proposed algorithm as compared to the standard GP approach. Furthermore, the impact of the training data selection and fitness evaluation have also been investigated. The results show that a compact training set can provide good output and existing evaluation methods are all usable for evolving efficient priority rules. The priority rules designed by the proposed approach are tested on extensive existing datasets and newly generated large projects with more than 1,000 activities. In order to achieve better performance on small-sized projects, we also develop a method to combine rules as efficient ensembles. Computational comparisons between GP-designed rules and traditional priority rules indicate the superiority and generalization capability of the proposed GP algorithm in solving the RCPSP.

2022

Various extensions in resource-constrained project scheduling with alternative subgraphs

Autores
Servranckx, T; Coelho, J; Vanhoucke, M;

Publicação
INTERNATIONAL JOURNAL OF PRODUCTION RESEARCH

Abstract
In this research, we present several extensions for the resource-constrained project scheduling problem with alternative subgraphs (RCPSP-AS). First of all, we investigate more complex variants of the alternative project structure. More precisely, we consider nested alterative subgraphs, linked alternative branches, multiple selection, caused and closed choices, and split choices. Secondly, we introduce non-renewable resources in the RCPSP-AS in order to implicitly avoid certain combinations of alternatives given a limited availability of this resource over the complete project horizon. We formulate both the basic RCPSP-AS and its extensions as an ILP model and solve it using Gurobi. The computational experiments are conducted on a large set of artificial project instances as well as three case studies. The results show the impact of the different extensions on the project makespan and the computational complexity. We observe that combinations of the proposed extensions might imply complex alternative project structures, resulting in an increasing computational complexity or even infeasible solutions. The analysis of the three case studies shows that it is hard to find feasible solutions with a small time limit or optimal solutions with a larger time limit for projects with a realistic size in terms of the number of activities or alternatives.

2026

Comparing and extending satisfiability solution methods for the resource-constrained project scheduling problem

Autores
Coelho, J; Vanhoucke, M;

Publicação
COMPUTERS & OPERATIONS RESEARCH

Abstract
This paper solves the resource-constrained project scheduling problem (RCPSP) with a satisfiability problem (SAT) solver. This paper builds further on various existing SAT models for this well-known project scheduling problem and extends them with two methods to satisfy the resource constraints. Specifically, we use the wellknown minimal forbidden sets and compare them with the so-called covers that are traditionally used in SAT implementations. Moreover, we also implement an existing binary decision trees approach under various settings and extend the model with networks with adders, so far never used for solving the RCPSP, to guarantee that resource constraints are satisfied. The algorithms are tested under different settings on a set of 13,413 project instances with diverse network and resource structures, and the experiments demonstrate that a combination of these approaches help in finding better solutions within a reasonable time. Moreover, 393 new lower bounds, 62 new upper bounds, and 290 optimally solved instances (including 18 from the PSPLIB) have been discovered, which, to the best of our knowledge, had not been found before. The strong performance of the new algorithm motivated additional experiments, and the preliminary results suggest several promising directions for future research.

2025

Comparison of two problem transformation-based methods in detecting the best performing branch-and-bound procedures for the RCPSP

Autores
Guo, WK; Vanhoucke, M; Coelho, J;

Publicação
EXPERT SYSTEMS WITH APPLICATIONS

Abstract
The branch-and-bound (B&B) procedure is one of the most frequently used methods for solving the resource-constrained project scheduling problem (RCPSP) to obtain optimal solutions and has a rich history in the academic literature. Over the past decades, various variants of this procedure have been proposed, each using slightly different configurations to search for the optimal solution. While most of the configurations perform relatively well for many problem instances, there is, however, no known universal best B&B configuration that works well for all problem instances. In this work, we propose two problem transformation-based machine learning classification methods (binary relevance and classifier chains) to automatically detect the best-performing branch-and-bound configuration for the resource-constrained project scheduling problem. The proposed novel learning models aim to find the relationship between the project characteristics and the performance of a specific B&B configuration. With this obtained knowledge, the best-performing B&B configurations can be predicted, resulting in a better solution. A comprehensive computational experiment is conducted to demonstrate the effectiveness of the proposed classification models and the performance improvements over three categories of methods from the literature, including the latest branch-and-bound configurations, the state-of-the-art classification models in project scheduling, and commonly used clustering algorithms in machine learning. The results show that the proposed classification models can enhance solution quality for the RCPSP without changing the core components of existing algorithms. More specifically, the classifier chains method, when combined with the Back-Propagation Neural Network algorithm, achieves the best performance, outperforming binary relevance, which demonstrates the impact of label correlation on the performance. The experiments also demonstrate the merits of the proposed model in improving the robustness of the solutions. Furthermore, these findings not only highlight the potential of the classification models in detecting best-performing B&B configurations, but also emphasize the need for future work and development to further improve the performance and applicability of these models.

  • 3
  • 7