Using priority rules for resource-constrained project scheduling problem in static environment

Mateja Đumić

doi:10.1016/j.cie.2022.108239

2022-07-01

PRE

Mateja Đumić *

Domagoj Jakobović

DOI：10.1016/j.cie.2022.108239

原文链接

原文求助

摘要

En 中文

The resource-constrained project scheduling problem (RCPSP) is one of the scheduling problems that belong to the class of NP-hard problems. Therefore, heuristic approaches are usually used to solve it. One of the most commonly used heuristic approaches are priority rules (PRs). PRs are easy to use, fast and able to respond to system changes, which makes them applicable in a dynamic environment. The disadvantage of PRs is that when applied in a static environment, they do not achieve results of the same quality as heuristic approaches designed for a static environment. Moreover, a new PR must be evolved separately for each optimization criterion, which is a challenging process. Therefore, recently significant effort has been put into the automatic development of PRs. Although PRs are mainly used in a dynamic environment, they are also used in a static environment in situations where speed and simplicity are more important than the quality of the obtained solution. Since PRs evolved for a dynamic environment do not use all the information available in a static environment, this paper analyzes two adaptations for evolving PRs in a static environment for the RCPSP -iterative priority rules and rollout approach. This paper shows that these approaches achieve better results than the PRs evolved and used without these adaptations. The results of the approaches presented in the paper were also compared with the results obtained with the genetic algorithm as a representative of the heuristic approaches used mainly in the static environment.

Keyword:

Genetic programming

Resource constrained project scheduling problem

Priority rules

Iterative priority rules

Rollout

Static environment