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.

2023

New resource-constrained project scheduling instances for testing (meta-)heuristic scheduling algorithms

Autores
Coelho, J; Vanhoucke, M;

Publicação
COMPUTERS & OPERATIONS RESEARCH

Abstract
The resource-constrained project scheduling problem (RCPSP) is a well-known scheduling problem that has attracted attention since several decades. Despite the rapid progress of exact and (meta-)heuristic procedures, the problem can still not be solved to optimality for many problem instances of relatively small size. Due to the known complexity, many researchers have proposed fast and efficient meta-heuristic solution procedures that can solve the problem to near optimality. Despite the excellent results obtained in the last decades, little is known why some heuristics perform better than others. However, if researchers better understood why some meta-heuristic procedures generate good solutions for some project instances while still falling short for others, this could lead to insights to improve these meta-heuristics, ultimately leading to stronger algorithms and better overall solution quality. In this study, a new hardness indicator is proposed to measure the difficulty of providing near-optimal solutions for meta-heuristic procedures. The new indicator is based on a new concept that uses the o-distance metric to describe the solution space of the problem instance, and relies on current knowledge for lower and upper bound calculations for problem instances from five known datasets in the literature. This new indicator, which will be called the o -D indicator, will be used not only to measure the hardness of existing project datasets, but also to generate a new benchmark dataset that can be used for future research purposes. The new dataset contains project instances with different values for the o -D indicator, and it will be shown that the value of the o-distance metric actually describes the difficulty of the project instances through two fast and efficient meta-heuristic procedures from the literature.

2023

A prediction model for ranking branch-and-bound procedures for the resource-constrained project scheduling problem

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

Publicação
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH

Abstract
The branch-and-bound (B&B) procedure is one of the most widely used techniques to get optimal so-lutions for the resource-constrained project scheduling problem (RCPSP). Recently, various components from the literature have been assembled by Coelho and Vanhoucke (2018) into a unified search algo-rithm using the best performing lower bounds, branching schemes, search strategies, and dominance rules. However, due to the high computational time, this procedure is only suitable to solve small to medium-sized problems. Moreover, despite its relatively good performance, not much is known about which components perform best, and how these components should be combined into a procedure to maximize chances to solve the problem. This paper introduces a structured prediction approach to rank various combinations of components (configurations) of the integrated B&B procedure. More specifically, two regression methods are used to map project indicators to a full ranking of configurations. The objec-tive is to provide preference information about the quality of different configurations to obtain the best possible solution. Using such models, the ranking of all configurations can be predicted, and these predic-tions are then used to get the best possible solution for a new project with known network and resource values. A computational experiment is conducted to verify the performance of this novel approach. Fur-thermore, the models are tested for 48 different configurations, and their robustness is investigated on datasets with different numbers of activities. The results show that the two models are very competitive, and both can generate significantly better results than any single-best configuration.

  • 3
  • 5