Text

A Theoretical Framework for Instance Complexity of the Resource-Constrained Project Scheduling Problem

The resource-constrained project scheduling problem (RCPSP) addresses the problem of constructing a schedule with minimum makespan for a set of activities, subject to precedence and resource constraints. Recent research introduced a data set with small instances that cannot be solved by the state-of-the-art algorithms, revealing a gap in our understanding of instance complexity. We propose a new theoretical framework for the instance complexity for the RCPSP, consecutively incorporating precedence constraints, resource constraints, and activity durations. Our approach contributes to the existing knowledge base in two ways. First, it is independent from solution algorithms, which enables generalisable conclusions. Second, the theoretical perspective enables a deeper understanding of the drivers of instance complexity. We evaluate the performance of our approach with a series of computational experiments. These show that our framework is a strong discriminator between easy and hard instances and explains a large fraction of CPU times of optimal solution algorithms.

Ketersediaan

Informasi Detail

Judul Seri

MATHEMATICS OF OPERATIONS RESEARCH; Vol.47 No.4 November 2022

No. Panggil

-

Penerbit

: .,

Deskripsi Fisik

p. 3156-3183

Bahasa

English

ISBN/ISSN

-

Klasifikasi

NONE

Tipe Isi

-

Tipe Media

-

Tipe Pembawa

-

Edisi

-

Subjek

RESOURCE-CONSTRAINED PROJECT SCHEDULING
INSTANCE COMPLEXITY
PARTIAL ORDERS
COUNTING PROBLEMS

Info Detail Spesifik

https://doi.org/10.1287/moor.2021.1237

Pernyataan Tanggungjawab

Rob Van Eynde, Mario Vanhoucke

Versi lain/terkait

Lampiran Berkas

Komentar