Robust planning and scheduling using column generation

Autonomous Planning and Scheduling (APS) is the problem of autonomously planning, scheduling and executing a sequence of actions in an environment to achieve some goals. Due to the increased adoption of APS in sensitive applications, there is an increasing need for models that are robust to the uncertainty prevalent in the real world. Robustness can be achieved by modelling the APS problem via stochastic optimization, however such problems are inherently difficult to solve. Recently, the column generation method has shown precedent in solving stochastic optimization problems. In this technique, the main optimization problem is decomposed into two more manageable sub problems which are then solved iteratively: the Restricted Master Problem (RMP) and the Column Generation Problem (CGP). In this thesis, we apply column generation in a novel way to develop robust solutions to APS problems. The first problem we address is a 5G telecommunications planning problem called the Virtual Network Function Placement and Routing Problem (VNFPRP). In 5G, Internet Service Providers (ISP) must deliver tailored network services for a variety of use cases; often with heterogeneous requirements defining the expected Quality of Service (QoS). Past approaches at solving this problem do not consider all of the constraints required to guarantee QoS. Likewise, the majority of prior algorithms either solve a large Integer Linear Program (ILP), which is computationally intractable for practical problems; or leverage heuristics, which give no guarantees on solution quality. In this thesis, we present a column generation based VNF-PRP algorithm which solves: the RMP, which optimizes the placement, replication and routing of the VNFs given the paths generated so far; and the CGP, which generates new paths. Our approach is the first VNFPRP algorithm to consider throughput, latency and availability constraints. It is also the first that is capable of computing a valid VNF placement, routing and replication solution, while providing a measure of solution quality. We validate our approach on a realistic Mobile Edge Cloud (MEC) network architecture and show that our model can find near optimal solutions to practical sized problems within a reasonable time. The second problem we address is a scheduling problem called Strong Controllability (SC). SC of Probabilistic Simple Temporal Networks (PSTN) involves finding a schedule to execute a sequence of actions that maximises the probability that all constraints are satisfied (robustness). Previous approaches to this problem assume independence of probabilistic durations. This gives no guarantee of finding the schedule optimising robustness, and fails to consider correlations between action durations that frequently arise in practical applications. In this thesis, we formally define the Correlated Simple Temporal Network (Corr-STN), which generalises the PSTN by removing the restriction of independence, and show that the problem of Corr-STN SC is convex. We present the first Corr-STN SC algorithm based on column generation which solves: the RMP, which finds the most robust schedule given an approximation of the joint distribution; and the CGP, which finds a new point to refine the approximation. We validate our approach on a number of Corr-STNs and find that our method offers strictly more robust solutions when compared with prior PSTN SC approaches.

Name dc:type.qualificationname

phd

Level dc:type.qualificationlevel

doctoral-pg

Grantor dc:publisher.institution

University of Strathclyde

Year dc:date.issued

2024

Author dc:creator

• Murray, Andrew

Advisors dc:contributor.advisor

• Roper, Marc, 1961-
• Cashmore, Michael
• Arulselvan, Ashwin

DOI

10.48730/5zav-yd92

Identifier

T16971

Author Identifier

202067419

OAI identifier oai:identifier

oai:strathclyde:5138jf65x