Scholarlink

<p>The multi-mode resource-constrained project scheduling problem is an NP-hard optimization problem with practical applications in construction, software development, manufacturing, and other industrial and business situations. It involves a set of activities that need to be sequenced while considering precedence and resource constraints as well as different alternative execution modes, which determine each activity’s duration and resource consumption. This research proposes three matheuristic strategies based on a reformulation and partial relaxation of the problem, including a generalized Benders decomposition (GBD)-based algorithm to solve the relaxed problem and three different procedures to find a solution to the original problem. The strategies were tested using benchmark instances of various sizes obtained from published libraries. These strategies showed a significant improvement in speed, achieving up to 92.77% faster performance than the exact method for finding high-quality sub-optimal solutions. This offers a valuable trade-off between computation time and solution quality. Additionally, the GBD-based algorithm generated tighter lower bounds than other existing methods in the literature for a substantial number of the tested instances, all within a very short computing time.</p>

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

Generalized Benders decomposition-based matheuristics for the multi-mode resource-constrained project scheduling problem

  • 期刊论文

  • 发表日期：

    2025年3月13日

查看全文
  • Alfredo S. Ramos,
  • Pablo A. Miranda-Gonzalez,
  • Elias Olivares-Benitez,
  • Abraham Mendoza

摘要

The multi-mode resource-constrained project scheduling problem is an NP-hard optimization problem with practical applications in construction, software development, manufacturing, and other industrial and business situations. It involves a set of activities that need to be sequenced while considering precedence and resource constraints as well as different alternative execution modes, which determine each activity’s duration and resource consumption. This research proposes three matheuristic strategies based on a reformulation and partial relaxation of the problem, including a generalized Benders decomposition (GBD)-based algorithm to solve the relaxed problem and three different procedures to find a solution to the original problem. The strategies were tested using benchmark instances of various sizes obtained from published libraries. These strategies showed a significant improvement in speed, achieving up to 92.77% faster performance than the exact method for finding high-quality sub-optimal solutions. This offers a valuable trade-off between computation time and solution quality. Additionally, the GBD-based algorithm generated tighter lower bounds than other existing methods in the literature for a substantial number of the tested instances, all within a very short computing time.