Mixed-integer linear programming for project scheduling under various resource constraints

Nicklas Klein

doi:10.1016/j.ejor.2024.06.036

2024-11-01

Nicklas Klein

Mario Gnägi

Ν. Trautmann *

DOI：10.1016/j.ejor.2024.06.036

原文链接

查看原文

摘要

En 中文

Project scheduling is an important management task in many companies across different industries. Generally, projects require resources, such as personnel or funds, whose availabilities are limited, giving rise to the challenging problem of resource-constrained project scheduling. In this paper, we consider the scheduling of a project consisting of precedence-related activities that require time and two types of resources for execution: storage resources representing, e.g., the project budget; and renewable resources representing, e.g., personnel or equipment. Storage resources are consumed by activities at their start or produced upon their completion, while renewable resources are allocated to activities at their start and released upon their completion. The resource-constrained project scheduling problem with consumption and production of resources (RCPSP-CPR) consists of determining a minimum-makespan schedule such that all precedence relations are respected, the demand for each renewable resource never exceeds its capacity, and the stock level of each storage resource never falls below a prescribed minimum. Due to the consideration of storage resources, the feasibility variant of this problem is NP-complete. We propose a novel compact mixed-integer linear programming (MILP) model based on a novel type of sequencing variables. These variables enable us to identify which activities are processed in parallel and whether a sequencing of activities is necessary to respect the resource capacities. Our computational results indicate that our novel model significantly outperforms state-of-the-art MILP models for all considered scarcity settings of the storage resources. Additionally, our results indicate a superior performance for instances of the well-known resource-constrained project scheduling problem (RCPSP).

Keyword:

Project scheduling

Mixed-integer linear programming

Resource-constrained project scheduling

Consumption and production of resources