[Back]

R. Ganian, T. Hamm, G. Mescoff:
"The Complexity Landscape of Resource-Constrained Scheduling";
Talk: IJCAI 2020, Yokohama; 2021-01-07 - 2021-01-15; in: "Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence", (2021), ISBN: 978-0-9992411-6-5; 1741 - 1747.

The Resource-Constrained Project Scheduling
Problem (RCPSP) and its extension via activity
modes (MRCPSP) are well-established scheduling
frameworks that have found numerous applications
in a broad range of settings related to artificial intelligence.
Unsurprisingly, the problem of finding
a suitable schedule in these frameworks is known
to be NP-complete-however, aside from a few results
for special cases, we have lacked an in-depth
and comprehensive understanding of the complexity
of the problems from the viewpoint of natural
restrictions of the considered instances.
In the first part of our paper, we develop new algorithms
and give hardness-proofs in order to obtain a
detailed complexity map of (M)RCPSP that settles
the complexity of all 1024 considered variants of
the problem defined in terms of explicit restrictions
of natural parameters of instances. In the second
part, we turn to implicit structural restrictions defined
in terms of the complexity of interactions between
individual activities. In particular, we show
that if the treewidth of a graph which captures such
interactions is bounded by a constant, then we can
solve MRCPSP in polynomial time.

http://dx.doi.org/10.24963/ijcai.2020/241

https://publik.tuwien.ac.at/files/publik_293765.pdf