Percorrer por autor "Guo, Weikang"
A mostrar 1 - 4 de 4
Resultados por página
Opções de ordenação
- An efficient genetic programming approach to design priority rules for resource-constrained project scheduling problemPublication . Luo, Jingyu; Vanhoucke, Mario; Coelho, José; Guo, WeikangIn 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.
- Automatic detection of the best performing priority rule for the resource-constrained project scheduling problemPublication . Guo, Weikang; Vanhoucke, Mario; Coelho, José; Luo, JingyuPriority rules are applied in many commercial software tools for scheduling projects under limited resources because of their known advantages such as the ease of implementation, their intuitive working, and their fast speed. Moreover, while numerous research papers present comparison studies between different priority rules, managers often do not know which rules should be used for their specific project, and therefore have no other choice than selecting a priority rule at random and hope for the best. This paper introduces a decision tree approach to classify and detect the best performing priority rule for the resource-constrained project scheduling problem (RCPSP). The research relies on two classification models to map project indicators onto the performance of the priority rule. Using such models, the performance of each priority rule can be predicted, and these predictions are then used to automatically select the best performing priority rule for a specific project with known network and resource indicator values. A set of computational experiment is set up to evaluate the performance of the newly proposed classification models using the most well-known priority rules from the literature. The experiments compare the performance of multi-label classification models with multi-class classification models, and show that these models can outperform the average performance of using any single priority rule. It will be argued that this approach can be easily extended to any extension of the RCPSP without changing the methodology used in this study.
- Comparison of two problem transformation-based methods in detecting the best performing branch-and-bound procedures for the RCPSPPublication . Guo, Weikang; Coelho, José; Vanhoucke, MarioThe 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 BackPropagation 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
- A prediction model for ranking branch-and-bound procedures for the resource-constrained project scheduling problemPublication . Guo, Weikang; Vanhoucke, Mario; Coelho, JoséThe branch-and-bound (B&B) procedure is one of the most widely used techniques to get optimal solutions 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 algorithm 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 objective 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 predictions 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. Furthermore, 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.