Abstract

Translate

The goal of this paper is to optimize mission schedules for vertical airports (vertiports in short) to satisfy the different needs of stakeholders. We model the problem as a resource-constrained project scheduling problem (RCPSP) to obtain the best resource allocation and schedule. As a new approach to solving the RCPSP, we propose answer set programming (ASP). This is in contrast to the existing research using MILP as a solution to the RCPSP. Our approach can take complex scheduling restrictions and stakeholder-specific requirements. In addition, we formalize and include stakeholder needs using a knowledge representation and reasoning framework. Our experiments show that the proposed method can generate practical schedules that reflect what stakeholders actually need. In particular, we show that our approach can compute optimal schedules more efficiently and flexibly than previous approaches. We believe that this approach is suitable for the dynamic and complex environments of vertiports.

Full text

Turn on search term navigation

Translate

1. Introduction

UAM Air Traffic Management (UATM) safely and efficiently coordinates electric vertical takeoff and landing (eVTOL) vehicles into densely populated urban airspace, contributing to next-generation transportation networks. UATM differs from the traditional methods of air traffic control. It specifically has to coordinate shared urban airspace while satisfying the needs of low-altitude operations with high frequencies and strict safety regulations and dealing with unpredictable weather [1,2]. The recent research suggests that developing frameworks for unbiased scheduling and resource allocation is necessary, and the frameworks help to reduce traffic congestion and ensure access to airspace resources [3,4]. Vertiport-centric scheduling—the focus of this work—serves as an important element of UATM, bridging aerial vehicle routing and ground infrastructure management to sustain system-wide efficiency as UAM operations expand.

Urban air mobility (UAM) facilitates rapid and low-emission aerial journeys through the utilization of eVTOL vehicles, transforming urban transportation. Vertiports, within UATM systems, are multifunctional hubs that can handle vehicle arrivals, departures, charging, passenger transfers, etc. [5]. Efficient scheduling at these hubs can reduce congestion, ensure safety, and meet the stakeholders’ diverse demands. These demands include ones from operators and passengers. However, the dynamic and resource-constrained nature that vertiports have—limited landing pads, charging stations, and airspace corridors—presents substantial challenges while we generate feasible and optimal schedules [6,7].

Traditionally, scheduling has depended on the approaches that solve the resource-constrained project scheduling problem (RCPSP), a well-established framework for optimizing tasks under resource limitations [8]. Along this line, mixed-integer linear programming (MILP) formulations of RCPSP have been widely studied [9,10]. However, these methods face unavoidable scalability issues for large UAM scenarios [11]. In addition, the existing scheduling approaches that solve RCPSPs are incapable of addressing stakeholder-specific requirements, such as flexible delay tolerances or over-assignable resources, which are necessary for practical UAM operations. These limitations inspire alternative paradigms to be explored, such as a declarative programming approach like answer set programming (ASP) [12,13,14]. ASP is effective for complicated combinatorial problems but remains unnoticeable in this specific scheduling context [15].

Based on our earlier work on the dynamic properties of UATM systems, we investigate ASP for vertiport scheduling [16,17,18,19]. We particularly used knowledge representation and reasoning techniques within ASP in order to handle detours or temporary vertiport unavailability. This paper expands on the previous research to the distinct problem domain of proactive vertiport resource scheduling. Specifically, we here focus on accommodating diverse stakeholder needs within the scheduling framework.

This paper addresses these gaps with three key contributions. First, we propose a novel ASP-based formulation for RCPSP and compare it against a MILP baseline. As far as we can tell, applying ASP to RCPSP has not been widely explored, and this work takes a step in that ASP outperforms MILP in scalability for large-scale UAM scheduling. Second, we extend RCPSP to incorporate stakeholder-driven scheduling requirements, including (1) strict on-time service guarantees, (2) over-assignable resources (e.g., shared charging stations), and (3) flexibly bounded execution delays for specific stakeholders. Third, we suggest two algorithmic procedures to calculate schedules that meet both RCPSP constraints and stakeholder needs. Afterwards, we provide extensive experimental confirmation of their effectiveness.

The remainder of this paper is structured as follows: Section 2 reviews the related work on RCPSP and UAM scheduling. Section 3 outlines preliminaries, while Section 4 formalizes the problem. Section 5 details our ASP formulations and stakeholder-considered algorithms. Section 6 and Section 7 present experimental results and conclusions, respectively.

2. Related Work

2.1. UAM Scheduling: Challenges and Domain-Specific Approaches

The UAM case study by [20] argues that for the UAM to be advanced, it requires the utilization of data-driven demand, vertiport locations, improved vertiport operations modeling, and aircraft trajectories. In addition, by integrating with advanced scheduling algorithms, its operations can be optimized, resulting in greater throughput and reduced wait times [21].

UAM operations are challenged to be introduced and scaled up by airspace restrictions [22], the workload of air traffic controllers [23], the integration of conventional and UAM flight operations [24], and the absence of robust airspace management strategies [25].

Various stakeholders, including airlines and regulatory bodies, are involved in UAM operations, and their demands require careful management. The authors in [26] pointed out that UAM vehicles should follow established air traffic regulations while communicating with Air Traffic Control (ATC) and interacting within controlled airspace. By adapting from the collaborative decision-making (CDM) technique, the framework [27] shows operations are efficiently maintained. In addition, research from [28,29] addresses that satisfying stakeholders’ needs will become much more important as UAM operations grow.

Recent studies show the challenges to the seamless integration of UAM in the existing urban transportation system [30]. Along this line, the works from [31,32,33] suggest an adaptive (on-demand) operational framework. The research in [34,35] introduces realistic UAM scheduling between heterogeneous small aircraft (including UAM fleets), suggesting a performance-based, multi-resolution model and a robust charging network. The research from [36] proposes strict safety protocols. As such, the dynamic nature of urban mobility presents both opportunities and challenges.

2.2. Resource-Constrained Scheduling: MILP and Heuristics

2.2.1. RCPSP and MILP Formulations

The resource-constrained project scheduling problem (RCPSP) is one of the major problems in operations research, requiring jobs in a project to be scheduled under resource constraints, with mixed-integer linear programming formulations being the major approach. The authors in [10] introduced a new model that accounts for both resource consumption and production, while their previous work in [37] suggested three established MILP models. The authors in [38] discussed ways in which automatic MILP reformulations and cutting plane techniques can optimize non-preemptive RCPSP solutions.

2.2.2. Heuristic and Metaheuristic Approaches

In addition to the MILP, alternative approaches have emerged, such as quantum annealing techniques [39], metaheuristic strategies [40], robust searching methodologies [41], and genetic algorithms [42]. These researchers explore RCPSP by integrating traditional MILP formulations with modern computational techniques and algorithmic strategies in order to optimize project scheduling under resource constraints.

Researchers have used many heuristic and metaheuristic algorithms, often deviating from the methods of linear programming (LP) and mixed integer linear programming (MILP). The author in [43] proposed a genetic algorithm specifically designed for project scheduling under resource constraints, showing its applicability to real-world scheduling challenges. The research in [44] introduced a hybrid approach that integrates genetic algorithms with local search to improve the solution quality of the RCPSP. Their work, particularly, was to improve both precision and computational efficiency.

The author in [45] suggested a differential evolution (DE) approach that utilizes constrained resources. The authors in [46] suggested the hybridization of multiple algorithms, such as particle swarm optimization (PSO) with differential evolution.

The authors of [47] suggested forward–backward improvement strategies for a GA to meet the RCPSP’s complicated needs, and the authors of [48] suggested a combined hybrid metaheuristic from a scatter search and from electromagnetism theory. The approach to decentralized, resource-constrained, multi-project scheduling from [49] shows how flexible resource scheduling methods are when used with optimizing a schedule for a multi-agent system.

2.3. Declarative Approaches: Answer Set Programming (ASP) in Scheduling

A few researchers have shown the possibility to solve complex scheduling problems in ASP. The authors in [50] suggest a way to break down complicated problems into manageable time windows. This would allow operations to be optimized while still following the order of operations. The work in [51] extends this to multi-resource partial-order flexible job-shop scheduling (MPF-JSS) scenarios using difference logic within the ASP framework. ASP is also adaptable in diverse scheduling contexts. In particular, the author in [52] suggests a hybrid scheduling environment. In addition, the work in [53] exemplifies resource-constrained scheduling.

Even though the research above introduced various scheduling problems, none of them stated RCPSP in the ASP formula.

2.4. Stakeholder-Centric Scheduling

The traditional techniques of RCPSP frequently lack adequate mechanisms to satisfy the changing needs of different stakeholders [54,55]. The works in [56,57,58] stick to resource restrictions, minimizing the makespan but not considering the distinctive demands of different stakeholders. In this respect, the authors in [59] proposed flexible structures in order to accommodate resource constraints. However, their work still did not capture the broader stakeholder context. In addition, in order to adapt to changing situations and requirements, the works from [60,61] suggested middle-ground solutions that apply fuzzy logic and heuristics. However, their works lacked systematic approaches to satisfy the varied demands from stakeholders.

Formalizing the requirements from different stakeholders to executable constraints can be inspired by particularly complex, multi-agent systems. The foundational work by [62] demonstrates how timed partial order specifications can enforce temporal and precedence rules, which are adaptable to UAM’s strict on-time guarantees and delay tolerances. This can also be complemented by multi-agent negotiation in resource allocation, such as distributed scheduling protocols [63,64,65], agent communication and coalition [49,66,67], and auction-based methods [68].

3. Preliminaries

3.1. Scenario I: Vertiport Operations as an RCPSP

In the context of vertiport scheduling, jobs represent distinct operational activities such as an electric vertical takeoff and landing vehicle’s arrival, landing, passenger disembarkation, battery charging, passenger embarkation, pre-flight checks, and departure. Each of these activities has an estimated processing time. The resources correspond to limited vertiport assets like landing pads, charging stations, parking stands, and available airspace slots for approach and departure. Each activity requires a certain unit of a specific resource, and these resources have finite capacities. Precedence relations define the necessary sequence of operations; for example, landing must precede charging, and charging must precede the next departure for the same vehicle.

Several typical job sequences can illustrate these operations and their inherent precedences:

Full Turnaround Sequence: Arrival → Landing → Passenger Disembarkation → Battery Charging → Passenger Embarkation → Pre-flight Checks → Departure. This is a sequence of the general operations that a vehicle drops off passengers, proceeds to required maintenance (like charging), boards new passengers, and then departs. Resources like landing pads, gates or stands, and charging stations are utilized sequentially.

Quick Drop-off Sequence: Arrival → Landing → Passenger Disembarkation → (Minimal Checks or Preparation) → Departure. This might be used for repositioning flights or short hops where extensive ground services like charging are not immediately required.

Cargo Operations Sequence: Arrival → Landing → Cargo Unloading → Cargo Loading → Pre-flight Checks → Departure. This is for transporting cargo. Instead of passenger-related jobs, it handles cargo-related jobs.

Charging-Focused Sequence: Arrival → Landing → Battery Charging → Pre-flight Checks → Departure. This sequence is only for eVTOL to visit the vertiport for charging without handling passengers or cargo.

3.2. RCPSP

The resource-constrained project scheduling problem (RCPSP) is a combinatorial optimization problem where we have to find a feasible plan for a group of n jobs while taking into account limitations on resources and order of priority. Each job has a processing time, a list of jobs that come after it, and a set of resources that it needs. Even though resources may be limited, they can be used again and again. Due to the rules of order, no job can start before all of its predecessors are completed. The jobs must be scheduled without interruption, meaning that once they begin, they cannot be stopped.

The RCPSP accepts the following input:

J: a set of jobs ${j \in N | 1 \leq j \leq n}$ ,

R: a set of resources,

S: a list of the order in which the tasks $(i, j)$ in the jobs will be executed,

T represents the planning horizon, which is a list of potential completion time steps for jobs,

$p_{j}$ : the time required to complete job j,

The formula $u (j, r)$ represents the required unit of resource r to complete job j, and

$C_{r}$ : the capacity of resource r.

In addition, the job set J contains two dummy jobs, ${0, n + 1}$ , that indicate the beginning and the end of scheduling. The dummies require no resources and have zero processing time.

The following is a binary formulation adapted from [69]. Decision variables $x_{(j, t)}$ are represented as follows:

(1) $x_{(j, t)} : = \{\begin{matrix} 1 & if job j is assigned to begin at time t \\ 0 & otherwise \end{matrix}$

Every job should be assigned at one time following its precedence order and resource restrictions. The entire model is as follows:

(2) $\begin{matrix} Minimize & \sum_{t \in T} t \cdot x_{(n + 1, t)} \end{matrix}$

(3) $\begin{matrix} Subject to & \sum_{t \in T} x_{(j, t)} & = 1 & \forall j \in J \end{matrix}$

(4) $\begin{matrix} \sum_{j \in J} \sum_{t_{2} = max (0, t - p_{j} + 1)}^{t} u_{(j, r)} \cdot x_{(j, t_{2})} \leq c_{r} & \forall t \in T, r \in R \end{matrix}$

(5) $\begin{matrix} \sum_{t \in T} t \cdot x_{(s, t)} - \sum_{t \in T} t \cdot x_{(j, t)} \geq p_{j} & \forall (j, s) \in S \end{matrix}$

(6) $\begin{matrix} x_{(j, t)} \in {0, 1} & \forall j \in J, t \in T \end{matrix}$

Below, from Equations (7)–(12), we provide ASP formulations to solve the same problem in a different approach converting from the one in Equations (2)–(6). Figure 1 shows two different resource assignments of the instance in Table 1. Both are valid, as we can see from the resource graphs shown in side by side.

(7) $\begin{matrix} 1 {start (A, I) : step (I)} 1 \leftarrow & task (A) . \\ \leftarrow & psrel (P, S), dur (P, D 1), start (P, I 1), start (S, I 2), \end{matrix}$

(8) $\begin{matrix} I 2 < I 2 + D 1 . \\ assigned_res (TS, A, R, AM) \leftarrow & step (TS), task (A), rsreq (A, R, AM), dur (A, AD), \end{matrix}$

(9) $\begin{matrix} start (A, TS 1), TS \leq TS < TS 1 + AD . \\ sum_assigned_res (TS, R, AM) \leftarrow & step (TS), limit (R,_), \end{matrix}$

(10) $\begin{matrix} AM = # sum {AM 1, A : assigned_res (TS, A, R, AM 1)} . \\ \leftarrow & sum_assigned_res (TS, R, AM), step (TS), limit (R, L), \end{matrix}$

(11) $\begin{matrix} AM > L . \\ estart (I) \leftarrow & start (A, I), etask (A) . \end{matrix}$

(12) $\begin{matrix} # minimize {I : estart (I)} . \end{matrix}$

For clarity, the core predicates used in Equations (7)–(12) are defined as follows:

task(A) signifies that A is a task to be scheduled.

step(I) denotes that I is a discrete time step within the planning horizon.

The predicate start(A,I) means task A is assigned to begin at time step I.

dur(A,D) indicates that task A has a processing duration of D time steps.

Resource requirements are specified by rsreq(A,R,AM), meaning task A requires AM units of resource R.

The predicate assigned_res(TS,A,R,AM1) is used to track that AM1 units of resource R are assigned to task A at time step TS.

sum_assigned_res(TS,R,AM) is to calculate the total amount AM of resource R to be assigned at time step TS. This includes all active tasks at this time step.

limit(R,L) specifies that resource R has a maximum capacity of L units.

psrel(P,S) is a precedence relation. It means that task P must complete before task S starts.

Finally, etask(A) identifies A as an end task (specifically, the tail dummy task in this context) whose start time is part of the objective function.

In addition, detailed explanations for some Equations are as follows:

Equation (8) ensures that every task A is assigned exactly one start time I from the available time steps. The construct 1 {…} 1 is an ASP choice rule, guaranteeing one successful assignment.

Equation (10) calculates the total resource usage. For a given time step TS and resource R, the component of the rule sums (#sum) all amounts AM1 of that resource assigned to any task A (via assigned_res(TS,A,R,AM1)). The result is unified with AM.

Equation (12) is the objective function. It instructs the ASP solver to find a schedule that minimizes the value I, where I is the start time of the tail dummy task (identified by estart(I), which is derived from start(A,I), etask(A)). Hence, minimizing the start time of this final dummy task effectively minimizes the overall project makespan.

We remark on the mathematical distinction between MILP and ASP formulations. Unlike MILP, which uses algebraic equations and inequalities, ASP is a declarative programming paradigm. ASP is based on logic programming and stable model semantics. A program in ASP consists of logical rules, and its solutions (answer sets) are the interpretations that satisfy these logical rules. Thus, Equations (7)–(12) are a logical specification of RCPSP constraints, which are different from a direct algebraic representation.

Table 2 shows a comparison of the formulas between MILP and ASP.

3.3. Multiple Schedules

We need to address multiple schedules to extend the model to cover individual requirements.

Here, we define a job tree, $J$ , that connects a set of jobs in an execution order.

A schedule can have more than one job tree, $J$ . Therefore, we call a schedule a job forest, $F$ . When we compute a schedule, we add two dummy jobs: one, called a head dummy, at the beginning, and another, called a tail dummy, at the end. Then we connect each head job in $J_{i}$ to the head dummy and each tail job in $J_{i}$ to the tail dummy.

Multiple schedules can be specified by $F_{i}$ . If $F_{1}$ and $F_{2}$ exist, they are independent of each other. $F_{1}$ executes its operations first, followed by $F_{2}$ , not simultaneously.

For example, Figure 1 has one schedule $F_{1}$ , two dummies (0 for the head and 11 for the tail), and three job trees. $J_{1}$ is ${4, 5, 3, 2, 1}$ , $J_{2}$ is ${8, 6, 7}$ , and $J_{3}$ is ${10, 9}$ .

3.4. Requirements

There are stakeholders. Each of them has its own goal for the Vertiport operation. The goal is to deliver passengers and/or cargo from point A to point B, taking into account connected transportation services. In addition, they need to specify their operational requirements based on their business needs.

Here, we present three general scenarios, each of which can effectively describe a specific requirement that each stakeholder wants to achieve.

3.4.1. [Req¹] Requirement 1: Punctuality

The main reason we take an air taxi that can fly through cities, avoiding the uncertainty of congested roads on the ground, would be to reach the destination on time. Therefore, it is important to complete a set of tasks associated with a particular stakeholder by the deadline.

3.4.2. [Req²] Requirement 2: Boarding of Additional Seats

In most cases, airlines want to have as many passengers and/or cargo as safety allows. During the scheduling process, if a task requires additional resources beyond its capacity, it is highly recommended to allocate those extra resources. However, safety, in particular payload, is an important factor for these aircraft, and there must be a high limit to allow increasing the amount of some required resources.

3.4.3. [Req³] Requirement 3: Managing Delivery Delays

When we track packages, we sometimes experience unexpected delays at certain points in the middle of shipping. Since this may increase the uncertainty of extended deliveries, it is recommended to manage the possible delays while operating the schedule. Specifically, overall schedules should not extend the duration of a set of jobs related to a particular stakeholder to a high limit.

4. Problem Formulation

4.1. Problem Statement

The following definition formally states the problem.

Definition 1.

RCPSP-REQ (Resource-Constrained Project Scheduling Problem with Requirements)

Input: Instances $I_{i} = 〈F_{i}, p s_{i}, r e s_{i}, j_{F_{i}}, d u r_{i}〉$ and requirements $R_{i} = {R e q_{i}^{1}, R e q_{i}^{2}, R e q_{i}^{3}}$

Output: A set of start times $S_{i}$ and a solution $R_{i}^{S}$ of requirements $R_{i}$

Process: Calculate a schedule for $F_{i}$ under the consideration of $R_{i}$ where $i \in Z_{\geq 1}$ .

4.2. Solution Overview

A simple flow shown in Figure 2a is as follows: given a set of input pairs as an instance of RCPSP-REQ, we solve the problem repeatedly after reading each pair of the input. When the model returned by the solver is satisfied, we output the result. If we obtain an unsatisfied result, we print the error. Then we move on to the next input pair. For an iterative approach, as shown in Figure 2b, we repeat the simple flow until the termination condition is met.

We note that a basic RCPSP is in the class of NP-hard [70]. Hence, when we consider $R_{i} = {\emptyset, \emptyset, \emptyset}$ as a conversion to the basic RCPSP from the RCPSP-REQ, it is in NP-hard too.

5. Proposed Solution

In order to provide the solution, we translated each requirement in Section 3.4 into predicates and constraints in answer set programming (ASP).

5.1. Listings of Requirements

In order to handle multiple schedules, we sequentially process each pair of inputs. Each schedule $F_{i}$ consists of an instance $I_{i}$ and a set of requirements $R_{i}$ .

$J_{i}$ is a tree ID in the ASP code, and $F_{i}$ is a set of trees in the schedule. A $tree / 2$ not only represents a set of relationships between related jobs but it also specifies the relationship between each tree and its respective stakeholder. Hence, we have a predicate $owner / 2$ . In the following listings, the owner represents the relationship between each requirement and its corresponding tree. Since two stakeholders may have similar requirements, we have the concept of track. Therefore, we use the predicate $tree_extension / 3$ and $preferable_range / 4$ to specify the same stakeholder across multiple schedules.

5.1.1. Solution for Req¹

The listing below focuses on restricting a specific tree of jobs, requested by a specific stakeholder, to ensure timely completion. For this, we give a predicate $deadline / 2$ . First, we collect the corresponding tail jobs in Equation (13). Next, before checking if the corresponding tree meets the deadline, we have to simply check the validation of the given deadline/2, comparing this with a precomputed value of the tree’s minimum duration in Equation (15). Then, in Equations (16) and (17), we check if at least one of the tail jobs is planning to finish the exact time we gave. With the constraint in Equation (14), followed by Equation (13), we can reliably conclude that all other jobs will be completed before the deadline.

$\begin{matrix} punctual_candidate (A, I 2) \leftarrow & task (A), tree (TR, A), owner (“ req 1 ”, TR), start (A, I 2), \end{matrix}$

(13) $\begin{matrix} 0 = = # count {1 : psrel (A, B), tree (TR, B)} . \\ \leftarrow & punctual_candidate (A, I 2), deadline (TR, I), dur (A, I 1), \end{matrix}$

(14) $\begin{matrix} tree (TR, A), I 2 > I - I 1, step (I 2) . \end{matrix}$

(15) $\begin{matrix} \leftarrow & deadline (TR, I 1), \min_tree_dur (TR, I 2), I 1 < I 2 . \\ deadline_met (TR) \leftarrow & punctual_candidate (A, I 2), deadline (TR, I), \end{matrix}$

(16) $\begin{matrix} tree (TR, A), I 2 = = I - I 1, dur (A, I 1) . \\ \leftarrow & C 1 = # count {1, TR : deadline (TR,_)}, C 1 \neq C 2, \end{matrix}$

(17) $\begin{matrix} C 2 = # count {1, TR : deadline_met (TR)} . \end{matrix}$

5.1.2. Solution for Req²

The following list focuses on allocating additional resources to specific jobs for specific stakeholders. To achieve this, we provide a specific resource type, $r^{★}$ , and a predicate called $preferable_range / 3$ . Firstly, in Equations (18) and (24), we classify jobs of trees that do not belong to the stakeholders of interest and/or do not require the specific resource $r^{★}$ as unoverassignable tasks. Then, we gather overassignable tasks in Equation (20) and assign an additional amount of resource $r^{★}$ in Equation (21). Through Equations (22) and (23), the assigned amount becomes no higher than the limit (Equation (23) works with Equations (10) and (11). In addition, Equation (9) is replaced with Equations (23)–(25)). Finally, with the rule in Equation (26) and its constraints in Equations (27) and (28), we can determine the total amount of excess resources allocated to the tree, keeping the value safely within the preferable range (We note that, conservatively, the lower bound of the preferred range could be zero. This is because, in some extreme cases, there may be no extra volume needed to overassign the resource. In such a scenario, the existing listing for $R e q^{2}$ may not be sufficient to meet the required range. However, we can compute the available volume early on while investigating the instance and determining the preferable range.).

(18) $\begin{matrix} excessed (A, 0) \leftarrow & task (A), tree (TR, A), not owner (“ req 2 ”, TR) . \\ excessed (A, 0) \leftarrow & task (A), tree (TR, A), owner (“ req 2 ”, TR), \end{matrix}$

(19) $\begin{matrix} 0 = = # count {L 1 : rsreq (A, r^{★}, L 1)} . \\ overassignable (A) \leftarrow & task (A), tree (TR, A), owner (“ req 2 ”, TR), \end{matrix}$

(20) $\begin{matrix} rsreq (A, r^{★}, L 1), limit (r^{★}, L 2), L 1 \leq L 2 . \end{matrix}$

(21) $\begin{matrix} 1 {excessed (A, L 1) : level (L 1)} 1 \leftarrow & overassignable (A), tree (TR, A), owner (“ req 2 ”, TR) . \\ \leftarrow & excessed (A, L 1), rsreq (A, r^{★}, L 2), limit (r^{★}, L 3), \end{matrix}$

(22) $\begin{matrix} L 1 + L 2 > L 3 . \\ assigned_res (TS, A, r^{★}, AM) \leftarrow & step (TS), overassignable (A), excessed (A, L 1), \\ dur (A, AD), start (A, TS 1), TS 1 \leq TS < TS 1 + AD, \end{matrix}$

(23) $\begin{matrix} rsreq (A, r^{★}, L 2), AM = L 1 + L 2 \\ assigned_res (TS, A, r^{★}, L 2) \leftarrow & step (TS), not overassignable (A), task (A), \\ dur (A, AD), start (A, TS 1), TS 1 \leq TS < TS 1 + AD, \end{matrix}$

(24) $\begin{matrix} rsreq (A, r^{★}, L 2) . \\ assigned_res (TS, A, R, L 2) \leftarrow & step (TS), task (A), dur (A, AD), start (A, TS 1), \end{matrix}$

(25) $\begin{matrix} TS 1 \leq TS < TS 1 + AD, rsreq (A, R, L 2), R \neq r^{★} . \\ excess_in_total (TR, AM) \leftarrow & preferable_range (TR, LB, HB), \end{matrix}$

(26) $\begin{matrix} AM = # sum {X, A : excessed (A, X), tree (TR, A)} . \\ \leftarrow & preferable_range (TR, LB, HB), AM < LB, \end{matrix}$

(27) $\begin{matrix} excess_in_total (TR, AM) . \\ \leftarrow & preferable_range (TR, LB, HB), AM > HB, \end{matrix}$

(28) $\begin{matrix} excess_in_total (TR, AM) . \end{matrix}$

5.1.3. Basic Solution for Req³

The following listing focuses on the overall delay for specific trees. We compute each schedule sequentially and measure this delay over the schedules by tracing the same track in Equations (29)–(31). For this inter-schedule tracking, we give three predicates: $delay_range / 1, delay_margin / 2$ , and $tree_extension / 3$ .

In addition, in order to calculate the delay (in Equations (34)–(37)), minimum tree durations for specific trees are pre-computed before scheduling. The previous schedule updates the predicate $delay_margin / 2$ and $delay_range / 1$ . Equations (40) and (41) process the $delay_margin / 2$ for the current schedule using the measured actual delay. The constraint in Equation (42) safely validates the actual delay for the specific tree within the overall margin.

(29) $\begin{matrix} tr_rel (TR, A) \leftarrow & owner (“ req 3 ”, X), tree (X, A), tree_extension (TR, X,_) . \end{matrix}$

(30) $\begin{matrix} tr_psrel (TR, A, B) \leftarrow & psrel (A, B), tr_rel (TR, A), tr_rel (TR, B) . \end{matrix}$

(31) $\begin{matrix} tr (TR) \leftarrow & tr_rel (TR,_) . \end{matrix}$

(32) $\begin{matrix} heads (TR, A) \leftarrow & tr_rel (TR, A), 0 = = # count {1 : tr_psrel (TR, B, A)} . \end{matrix}$

(33) $\begin{matrix} tails (TR, A) \leftarrow & tr_rel (TR, A), 0 = = # count {1 : tr_psrel (TR, A, B)} . \end{matrix}$

(34) $\begin{matrix} \min_tree_duration (TR, I) \leftarrow & tree_extension (TR, X,_), \min_tree_dur (X, I) . \\ actual_tree_duration (TR, I 3) \leftarrow & I 1 = # \min {I : start (A, I), heads (TR, A)}, tr (TR), \\ I 2 = # \max {I + D : start (B, I), dur (B, D), tails (TR, B)}, \end{matrix}$

(35) $\begin{matrix} I 3 + I 1 = = I 2, I 1 < I 2, step (I 3) . \\ actual_delay (TR, L 3) \leftarrow & \min_tree_duration (TR, L 1), actual_tree_duration (TR, L 2), \end{matrix}$

(36) $\begin{matrix} L 3 + L 1 = = L 2, L 1 \leq L 2, delay_range (L 3) . \end{matrix}$

(37) $\begin{matrix} \leftarrow & 0 = = # count {1 : actual_delay (TR, L 3)} . \\ within_delay_range (TR, CD 1) \leftarrow & tree_extension (TR,_, L 1), actual_delay (TR, L 2), \end{matrix}$

(38) $\begin{matrix} L 1 = = L 2 + CD 1, delay_range (CD 1) . \\ outside_delay_range (TR, CD 1) \leftarrow & tree_extension (TR,_, L 1), actual_delay (TR, L 2), \end{matrix}$

(39) $\begin{matrix} L 1 + CD 1 = = L 2, CD 1 \geq 1, delay_range (CD 1) . \\ current_delay_margin (TR, CD 2) \leftarrow & outside_delay_range (TR, CD 1), delay_margin (TR, CD), \end{matrix}$

(40) $\begin{matrix} CD 1 + CD 2 = = CD, CD 2 \leq CD, CD 1 \leq CD, delay_range (CD 2) . \\ current_delay_margin (TR, CD 2) \leftarrow & within_delay_range (TR, CD 1), delay_margin (TR, CD), \end{matrix}$

(41) $\begin{matrix} CD 1 + CD = = CD 2, delay_range (CD 2) . \\ \leftarrow & tree_extension (TR,_, L 1), actual_delay (TR, L 2), \end{matrix}$

(42) $\begin{matrix} delay_margin (TR, L 3), L 2 - L 3 > L 1 . \end{matrix}$

5.2. Combining Listings with Procedural Codes

To satisfy all specified requirements, particularly $R e q^{2}$ and $R e q^{3}$ , it is necessary to compute all schedules within the set of job forests $F_{1}, F_{2}, \dots$ . The procedure to calculate these schedules is as follows:

Algorithm 1 outlines the procedural flow for solving a sequence of vertiport scheduling instances, each with associated stakeholder requirements. This procedure corresponds to the simple flow depicted in Figure 2a in Section 4.2. For each instance and requirement pair $〈 I_{i}, R_{i} 〉$ (We remark that the instance $I$ has predicates related to task, tree, precedence relationship, required resources, and their limits. The requirement $R$ has predicates related to the deadline of some trees, the preferable amount of resources and their quarters, and permitable track and tree extensions. Auxiliary facts are predicates related to the time step range, resource levels, dummy tasks and their precedence relationships, delay range and margin, and minimum tree durations for some trees.) in the input list, along with its current delay margin $M [i]$ (The delay margin, $M$ , is for $R e q^{3}$ . When the corresponding tree takes longer than its minimum duration, it represents an allowable delay. Therefore, during the sequential schedule calculation, we measure the tree’s delay and update the allowable margin accordingly. In Algorithm 2, we show how to handle this from outside, including its setup.), the algorithm initializes a reasoning controller, $C$ . This controller is then loaded with the foundational RCPSP rules (Equations (7)–(12)), the specific ASP rules for handling stakeholder requirements (Equations (13)–(42)), the factual data representing the current scheduling instance $I_{i}$ and its requirements $R_{i}$ , any necessary auxiliary facts, and the current delay margin $M [i]$ . The $C . g r o u n d ()$ operation translates these rules and facts into a propositional program suitable for the ASP solver. Subsequently, $C . c o m p u t e ()$ invokes the solver to find an optimal schedule. If a satisfiable model is found ( $C . s a t i s f i a b l e ()$ is true), the resulting schedule $S_{i}$ and the outcome of the requirement satisfaction $R_{i}^{S}$ are extracted from $C . m o d e l ()$ . This pair is stored, and then the delay margin list is updated to $M [i + 1]$ based on the current_delay_margin/2 predicate, which is derived from the model. This is for use in the next iteration or by a higher-level iterative process (We note that for the last iteration, where the returned model is for the last schedule and its requirement, the delay margin in the first index is updated. For further details, refer to Algorithm 2, where each iteration requires the updated $M$ for the RCPSP-REQ-ASP.). While sequentially processing all input pairs, it returns the list of computed schedules and the final updated delay margins.

Algorithm 1: RCPSP-REQ-ASP

Algorithm 2: RCPSP-REQ-ASP-ITER

Algorithm 2 describes an iterative approach to handle interdependencies between schedules. This is particularly for serving requirements like $R e q^{3}$ that involve managing delays across a series of operations. This procedure aligns with the ’Iterative Approach’ shown in Figure 2a in Section 4.2. The algorithm first initializes a list of delay margins $M$ to zeros for all trees in the input instances. It then starts a while loop. This loop continues as long as the progressing holds (by which the flag keeps true). Within the loop, it calls Algorithm 1. The current set of instances $H$ and the delay margins $M$ are delivered to the input. Algorithm 1 then returns the computed schedules $W$ and potentially updated margins $M$ . The termination condition, CheckTerminationCondition( $W$ ) (as defined in Equation (43)), is evaluated. This condition check investigates if the set of schedules $W$ has changed. If $W$ has changed, it repeats the iteration again. However, if $W$ has stabilized (i.e., no changes occurred), the terminated flag becomes true. This makes progressing false, and the loop terminates. It finally returns the final set of computed schedules $W$ . This procedure allows schedules to adjust based on the outcomes and delay propagations from others.

(43) $CHECK TERMINATION CONDITION (W) : = \{\begin{matrix} F a l s e & W is changed \\ T r u e & otherwise \end{matrix}$

Remark on Termination Condition: In our practical implementation, the termination condition specified in Equation (43) is adjusted to handle intrinsic cycles. In Algorithm 2, we terminate the iteration process if terminated becomes true as a result of having ‘not changed’. We regard having ‘not changed’ when the current set of schedules $W$ matches any set of schedules $W$ that has been generated in a previous iteration. On the other hand, the process is considered ‘changed’ if the current $W$ is novel compared to all previously generated sets. This approach ensures termination even if the algorithm enters a cycle of states rather than strictly converging to a fixed point identical to the immediately preceding iteration, a behavior observed in a small percentage (less than 1%) of our test instances. It is important to note that this convergence process is not related to optimizing each job forest but to finding stable, balanced delay margins over the set of job forests.

Theorem 1

(Correctness). Each listing for $R e q^{k}$ , where $k \in {1, 2, 3}$ , restricts an instance $I$ as it is specified in $R$ .

Proof.

We have three cases for the entire set of requirements.

Case $k = 1$ s.t. $R e q^{1}$ : The $R$ is deadline/2. We demonstrate here that the corresponding tree’s task does not exceed the given deadline, and the tree meets the deadline. First of all, Equation (15) guarantees the validity of the given deadline, comparing the deadline of the corresponding tree with its precomputed minimum duration. Next, given that the puctual_candidate/2 collects the tail jobs in the related tree and applies the constraint in Equation (14), it is valid to say that no subsequent job will start after the deadline. The rule for deadline_met/1 in Equation (16) and the constraint in Equation (17) require at least one tail job to finish at deadline/2. Therefore, in order to satisfy the model, the constraints should hold, making the latest tail job be finished on time.

Case $k = 2$ s.t. $R e q^{2}$ : The $R$ comprises two elements: $r^{★}$ and preferable_range/3. Here, we demonstrate that it only selects $r^{★}$ requiring tasks as overassignable tasks in the corresponding tree and ensures that the total amount of overassigned resources does not fall below or exceed the preferred range. First, constraints in Equations (18) and (24) remove irrelevant tasks, assigning zero to the excess value. These tasks in the corresponding tree have no effect on the total. Secondly, the rule in Equation (20) gathers relevant tasks, and Equations (21) and (22) provide possibly permitted excess values. Finally, the constraints in Equations (27) and (28) force the computed total amount of excessed values over the tasks in Equation (26) to fall within the specified preference range.

Case $k = 3$ s.t. $R e q^{3}$ : The $R$ consists of delay_range/2, delay_margin/2, and tree_extension/3. Here, we demonstrate that the actual delays for trees in the corresponding track do not surpass the limits set by $R$ . Firstly, to select the same track, we obtain the track value from tree_extension/3 in Equation (29). Then, for all the other rules representing the variable TR, we use the track value. Secondly, after measuring an actual tree duration and comparing it with its minimum duration in Equations (34) and (35), it computes the actual delay. Finally, it computes the current delay margin, taking into account both the actual delay and the given delay margin. The constraint in Equation (42) ensures that the actual delay, when subtracted by the given margin, should not surpass the tree_extension/3, thereby controlling the start times for corresponding heads and tails within this boundary. This ensures that the actual tree duration and delay do not exceed the extension. □

Theorem 2

(Completeness). Given a sequence of $〈I, R〉$ pairs as the input of the RCPSP-REQ problem, Algorithm 2 computes a sequence of schedules if one exists and outputs the computed schedules with the results of requirements if one exists. Otherwise, it returns an empty set.

Proof.

In this proof, both cases are covered:

The first case is whether Algorithm 2 computes a solution when one exists. Without loss of generality, the existing solution has a form of $W$ , which consists of $S$ and $R^{S}$ pairs. Additionally, each element pair in $W$ has been updated with a proper schedule and a result based on the requirements, replacing the initial empty set. Since each iteration in Algorithm 2 calls Algorithm 1, and Algorithm 1 returns $〈W, M〉$ without any exception, we can safely obtain the result from Algorithm 1. The only case when one of the output pairs has the un-updated element from its initial value is that the model from the controller $C$ is not satisfied in line 12 of Algorithm 1. Therefore, a successful element pair with the proper schedule and a requirements’ result implies that it holds all rules and constraints in RCPSP and the requirements in Equations (7)–(42), returning a model that is a set of start times for tasks and requirement results. Then, this iteration in Algorithm 2 repeats until the termination condition in line 5 is met. Finally, it exits the loop, returning the $W$ output.

The second case is whether it returns an empty set when a solution does not exist. Assume that one of the instance and requirement pairs does not have a solution. We can easily elaborate on this case. Without loss of generality, the failed output has an empty set, and this set has a form of $〈\emptyset, \emptyset〉$ by its initial setup in line 1 in Algorithm 1. Since this input, which we refer to as $I^{⊥}$ here, lacks a proper schedule, we are unable to determine a set of start times for tasks within $I^{⊥}$ . We assume that there exists an unempty set of tasks in $I^{⊥}$ . If it has an empty set of tasks, still it cannot satisfy the requirements (i.e., the deadline/2) so that it is unsatisfiable, returning an empty set as its output. Since this unempty set of tasks does not have a set of start times; this cannot meet the requirements. For example, there is no set of start times to satisfy the deadline/2 in $R e q^{1}$ . Hence, it is not satisfiable in line 12 in Algorithm 1, keeping the initial value the same. Algorithm 2 repeats this iteration, maintaining the same value for this element without any changes. This holds the termination condition, and then finally, it returns an empty set of the element in the output list. □

6. Experiments and Discussions

6.1. Experiments

6.1.1. Toy Example

To demonstrate the conceptual example of our solution, we examined the same instance in Table 1. Table 3 represents the facts given for two different requirement sets and their results. Figure 3 shows individual trees for the owners of $R e q^{1}$ , $R e q^{2}$ , and $R e q^{3}$ and resource assignments for each requirement set.

Both sets have a common auxiliary fact for the constraint: $I$ . $R$ set 1 has a deadline at 25 steps, while $R$ set 2 has a deadline at 15 steps. The preferable ranges for the overassignable resource are 1 to 2, 2 to 3, respectively. $R$ set 1 allows the extensions of the tree to span up to five steps, while $R$ set 2 allows it up to four steps. Both sets were configured with no allowable delay margin (set to zero). For $R e q^{1}$ , task 9 ends at 25 steps in Figure 3b and ends at 15 steps in Figure 3c. For $R e q^{2}$ , both have one unit of the excess resource for tasks 4 and 5 (Refer to the excessed/2 in the $R e q^{2}$ row of Table 3. In addition, in this example, $r^{★}$ is Resource 1.). The available slots range from 0 to 7 steps in Figure 3b and from 5 to 12 steps in Figure 3c. For $R e q^{3}$ , the actual tree durations for the tree are 15 steps and 12 steps, respectively.

6.1.2. Numerical Experiments

We constructed a common experimental environment, using exclusively open-source software to ensure full reproducibility. The MILP models were implemented through Python (version 3.12.3, conda-forge, AMD64). We used the PuLP library (version 2.8.0) with the CBC (COIN-OR Branch and Cut) solver, accessed via PULP_CBC_CMD, running within a Cygwin environment. For the ASP-based approaches, we used Clingo (version 5.7.1). This is also operated within the same Python environment as the MILP experiments. For the experiments, the machine we used had an 11th Gen Intel(R) Core(TM) i5-1135G7 processor (Intel Corporation, Santa Clara, CA, USA) at 2.40 GHz and 8GB of RAM. A consistent time limit of 600 s was set for each instance across both cases.

We constructed a common experimental environment. The MILP models were implemented through Python (version 3.12.3; Python Software Foundation, Wilmington, DE, USA). We used the PuLP library (version 2.8.0; University of Auckland, Auckland, New Zealand) with the CBC (COIN-OR Branch and Cut) solver (COIN-OR Foundation, Towson, MD, USA), running within a Cygwin environment (Red Hat, Inc., Raleigh, NC, USA). For the ASP-based approaches, we used Clingo (version 5.7.1; University of Potsdam, Potsdam, Germany). This is also operated within the same Python environment as the MILP experiments. The machine we used had an 11th Gen Intel(R) Core(TM) i5-1135G7 processor (Intel Corporation, Santa Clara, CA, USA) at 2.40 GHz and 8GB of RAM. A consistent time limit of 600 s was set for each instance across both cases.

Within this setup, we conducted two major numerical experiments. The first experiment evaluates scalability for both approaches and assesses solution time for standard RCPSP instances. Table 4 shows the comparison between MILP and ASP performance. In the table, ‘ $| J |$ ’ denotes the job count. ‘ $F_{i}$ Time [s]’ indicates the minimum, median, and maximum computation time per 100 instances. ‘ $S$ Step [#]’ represents the minimum, median, and maximum makespan. ‘Succ. [#]’ lists successful instances (out of 100) within a 600-s limit. The results in Table 4 showed MILP’s success dropped to zero for 40 or more jobs, while ASP, though its success also declined with increasing job numbers, solved more instances for larger job sets, practically handling up to 50 jobs within our settings.

The second experiment investigated ASP with stakeholder requirements, using 100 job forests ( $F s$ ), each containing five 20-job schedules ( $F_{i} s$ ). Table 5 compares the ‘Plain’, ‘Req’, and ‘Iter’ methods. In this table, ‘ $F_{i}$ Time [s]’ shows aggregated minimum, median, and maximum computation time per individual schedule $F_{i}$ . ‘ $F$ Time [s]’ is the total computation time per complete job forest $F$ . ‘ $S$ Step [#]’ is the makespan per $F$ . ‘Punctuality [#]’ counts the job forests meeting all $R e q^{1}$ (punctuality requirements). Key findings, presented in Table 5 and Figure 4, include the following: The ‘Plain’ solver (Figure 4a,b, tracks 0, 2) showed no excess resource allocation and no delay limits. The ‘Req’ solver (tracks 1, 3) accommodated these. The ‘Req’ and ‘Iter’ solvers showed similar excess resource results (Figure 4c). However, the ‘Iter’ solver achieved narrower, more constrained delay ranges (Figure 4d), although its computation time was approximately four times longer than the ‘Req’ approach, reflecting its iterative refinement. The ‘Plain’ solver did not address punctuality, unlike the ‘Req’ and ‘Iter’ methods.

6.2. Discussions

6.2.1. Performance Issue

Scalability: The inherent combinatorial explosion of RCPSP limits the scalability of our solution, as demonstrated in Table 4. We recommend developing a heuristic algorithm for practical use and to support large-scale job scheduling, such as a genetic algorithm (GA) [43,44,47], differential evolution (DE) [45,46], and metaheuristic [48].

MILP vs. ASP: Comparing general computational efficiency between MILP and ASP is beyond the scope of this paper. This is because of the inherent complexities of their distinct solving paradigms. Choosing a method to solve a problem often depends on the specific problem structure. ASP solvers uses grounding techniques and conflict-driven clause learning (CDCL) similar with SAT solvers. These choices allow us to excel in problems with intricate logical constraints [71,72]. On the other hand, MILP solvers are mostly optimized for problems that fit in their linear algebraic framework. Then, they utilize methods like branch-and-cut [73,74].

The authors in [75] show that ASP-based approaches can offer competitive performance. Their statement only holds for certain types of problems, like scheduling and combinatorial optimization of their domain. In semiconductor manufacturing, their work shows that constraint answer set programming (CASP) is more effective than traditional MILP solutions. Their approach particularly generates optimal schedules for automated wet-etch stations. CASP reduces the makespan more effectively. This clearly provides that ASP is able to assist with task scheduling jobs. Even though theoretical advantages have not been proven universally, the result is consistent with what we discovered in this paper.

6.2.2. What We Have Not Covered Here

LP Relaxation: Our approach to RCPSP is focused on MILP, not linear programming. This is because our MILP formulation in Section 3.2 was to clearly introduce discrete and countable resource management through integer programming. We can narrow down the possible result sets for a specific RCPSP case. This can be performed by heuristically performing LP relaxation. We can also establish lower bounds [38,76,77,78,79]. However, we chose MILP to obtain an exact solution. Choosing MILP let us easily transition to the ASP formulation, and this allowed for a simpler representation of the requirements.

Graph-Based Algorithmic Approach: This scheduling problem differs from a simple pathfinding problem in that it does not involve navigating a physical environment. Decisions made in one job plan by the RCPSP will impact other job plans. This approach is quite similar to cooperative pathfinding [49]. Since this perspective is relatively new in research, we need more scenarios and simulation results. This will help us apply this problem and approach in practice.

6.2.3. Future Directions

We need to explore more detailed resource characteristics and specialized task types, such as time-varying or preemptive maintenance scheduling.

Research into human–machine interaction for UAM system operators and managers would be important to expand. This is particularly important for the decision making in automated scheduling environments.

The next step to move should be to extend and to validate our method to more complex and larger-scale UAM scheduling problems. Particularly, this includes handling real-time data (e.g., weather, congestion), integrating with broader UAM ecosystem simulations, and modeling network effects across interconnected vertiports.

In order to support the UAM vision of widespread unmanned autonomous flight and responsive on-demand services, future research ultimately should develop adaptive and resilient scheduling methodologies. These would be capable of managing dynamic and disruptive scenarios, such as priority flights or unforeseen system-wide perturbations.

7. Conclusions

This paper studies a new framework for UAM scheduling. It integrates stakeholder needs into the RCPSP via the ASP approach. Through experiments, we show that the ASP-based model outperforms traditional MILP formulations in scalability for large-scale UAM scheduling, particularly in dynamic resource allocation scenarios. Our model, then, introduces how to handle stakeholder-specific constraints, such as on-time guarantees, overassignable resources, and flexible delay bounds. This approach enables schedules that balance operational efficiency with real-world stakeholder needs and maintains feasibility while accommodating diverse requirements.

We believe that our findings are relevant to UAM operators and policymakers because this approach allows vertiports to handle increasing eVTOL traffic without sacrificing computational tractability. On the other hand, the suggested model still assumes static stakeholder priorities and, therefore, requires further investigation. Future research directions include extending the ASP formulation to handle dynamic stakeholder priorities, investigating hybrid models, optimizing multi-vertiport coordination, and incorporating energy consumption models for eVTOLs.

Author Contributions

J.K.: Conceptualization, formal analysis, software, writing—review and editing, validation, investigation, K.K.: Conceptualization, formal analysis, software, writing—review and editing, writing—original draft preparation, validation. All authors have read and agreed to the published version of the manuscript.

Data Availability Statement

The source code for the RCPSP-REQ instance generators and solvers, including the ASP encodings used for the experiments reported in this paper, is openly available in a GitHub repository at: https://github.com/kangjinkim/rcpsp-req-solver (accessed on 16 June 2025). The repository includes a README file with instructions on prerequisites, configuration, and usage to facilitate the reproduction of our results and further research.

Conflicts of Interest

Author Jeongseok Kim was employed by the company SK Telecom. The remaining author declares that the research was conducted in the absence of any commercial or financial relationships that could be construed as a potential conflict of interest.

Abbreviations

The following abbreviations are used in this manuscript:

ASP	Answer set programming
ATC	Air Traffic Control
CDM	Collaborative decision making
DE	Differential evolution
eVTOL	electric vertical takeoff and landing
GA	Genetic algorithm
MILP	Mixed-integer linear programming
MPF-JSS	Multi-resource partial-order flexible job-shop scheduling
PSO	Particle swarm optimization
RCPSP	Resource-constrained project scheduling problem
UAM	Urban air mobility
UATM	UAM Air Traffic Management
CDCL	Conflict-driven clause learning
SAT	boolean SATisfiability problem

Footnotes

Disclaimer/Publisher’s Note: The statements, opinions and data contained in all publications are solely those of the individual author(s) and contributor(s) and not of MDPI and/or the editor(s). MDPI and/or the editor(s) disclaim responsibility for any injury to people or property resulting from any ideas, methods, instructions or products referred to in the content.

Figures and Tables

Figure 1 This is an RCPSP instance with ten jobs (numbered 1–10) and three types of resources (0–2). The top graph illustrates the precedence relations between jobs, where each task is assigned a unique color for easy identification across all graphs. The lower graphs show the resource allocation for each time step. The red dashed lines indicate the maximum capacity for each resource type. The sum of resources allocated to tasks at any point in time cannot exceed this line. Each side of the schedule has a dummy for marking its beginning and finishing.

Figure 2 This is an overall solution sketch we provide in Section 5.

Figure 3 Toy Example Solution Result. This demonstrates the application of two different requirement sets from Table 3. This figure uses the same RCPSP instance introduced in Figure 1. (a) Illustrates the precedence relations for the tasks. (b,c) Display the resulting schedules for Requirement Set 1 and Requirement Set 2, respectively. The notational conventions, including the color-coding for jobs, task numbering, and the red dashed lines indicating resource capacity, are consistent with those defined in Figure 1.

Figure 4 Numerical Experiment Result for Plain vs. Req vs. Iter. Across the plots, blue bars represent data from Tracks 0 and 2, and yellow bars represent data from Tracks 1 and 3. Cyan bars indicate the count of instances at 0%, and red bars represent the count at 100%.

Table 1

This is a table to represent the instance shown in Figure 1.

Job	Duration	Resources Required			Successors
Job	Duration	Resource 0	Resource 1	Resource 2	Successors
1	5			3
2	2	1			1
3	1			2	2
4	5	3	1		2
5	2	3	1		3
6	4			1
7	2			3
8	5	1	3
9	5		1		6, 7
10	4			1	9

Table 2

Formula Map between MILP and ASP.

Function	MILP	ASP	Description
Objective	Equation (2)	Equation (12)	It minimizes the start time of the tail dummy.
Constraints	Equations (3) and (6)	Equation (7)	Each task should be assigned only once.
	Equation (4)	Equations (9)–(11)	The required resources for each task should be allocated for the duration from its beginning, and the sum of all allocated resources at every time step should not exceed the limit.
	Equation (5)	Equation (8)	Every pair of tasks in the precedence relationship should follow the order.

Table 3

Facts and Results for $R$ set 1 and $R$ set 2.

	$R$ Set 1	$R$ Set 2
Aux. facts for $I$	The set $F$ is {“tx1”, “tx2”, “tx3”}.owner(“req1”, “tx3”), owner(“req2”, “tx1”), owner(“req3”, “tx2”),tree(“tx3”, 9..10), tree(“tx1”, 1..5), tree(“tx2”, 6..8).
Aux. facts for $R$	deadline(“tx3”, 25),preferable_range(“tx1”, 1, 2),text_extension(0, “tx2”, 5),delay_range(0..5).	deadline(“tx3”, 15),preferable_range(“tx1”, 2, 3),text_extension(0, “tx2”, 4),delay_range(0..4).
Additional facts	delay_margin(0, 0).
$R e q^{1}$	punctual_candidate(9, 20),deadline_met(“tx3”).	punctual_candidate(9, 10),deadline_met(“tx3”).
$R e q^{2}$	excessed(4, 1), excessed(5, 1),excess_in_total(0, 2).	excessed(4, 1), excessed(5, 1),excess_in_total(0, 2).
$R e q^{3}$	actual_delay(0, 4).	actual_delay(0, 1).
Total Duration	estart(25).	estart(19).

Table 4

Numerical Results for MILP vs. ASP. Time [s] denotes the computation time in seconds. Step [#] indicates the makespan as the number of time steps, and Succ. [#] represents the count of successful instances.

	MILP			ASP
$\| J \|$	$F_{i}$ Time [s]	$S$ Step [#]	Succ. [#]	$F_{i}$ Time [s]	$S$ Step [#]	Succ. [#]
$\| J \|$	(Min\|Median\|Max)	(Min\|Median\|Max)	Succ. [#]	(Min\|Median\|Max)	(Min\|Median\|Max)	Succ. [#]
10	00.108\|000.256\|041.252	09\|16.0\|25	100	0.000\|000.031\|000.064	09\|16.0\|25	100
20	00.646\|015.134\|455.195	13\|21.0\|32	94	0.080\|000.271\|002.156	13\|20.5\|32	100
30	27.312\|132.038\|424.036	20\|23.5\|30	20	0.459\|001.887\|375.537	18\|26.0\|42	98
40	—	—	0	2.516\|026.192\|572.800	20\|31.0\|38	71
50	—	—	0	7.943\|148.850\|554.881	28\|35.0\|42	24

Table 5

Numerical Results for Plain vs. Req vs. Iter. Time [s] is the computation time in seconds, Step [#] is the makespan in time steps, and Punctuality [#] is the count of instances meeting all punctuality requirements.

	$F_{i}$ Time [s]	$F$ Time [s]	$S$ Step [#]	Punctuality [#]
	(Min\|Median\|Max)	(Min\|Median\|Max)	(Min\|Median\|Max)	Punctuality [#]
Plain	0.095\|0.446\|30.191	—	13\|21\|40	35
Req	0.136\|0.657\|04.082	01.795\|03.378\|08.275	16\|25\|45	1000
Iter	0.121\|0.648\|04.285	06.669\|13.864\|35.994	16\|25\|45	1000

© 2025 by the authors. Licensee MDPI, Basel, Switzerland. This article is an open access article distributed under the terms and conditions of the Creative Commons Attribution (CC BY) license (https://creativecommons.org/licenses/by/4.0/). Notwithstanding the ProQuest Terms and Conditions, you may use this content in accordance with the terms of the License.

Enhancing Urban Air Mobility Scheduling Through Declarative Reasoning and Stakeholder Modeling

Content area