Periodic Chains Scheduling on Dedicated Resources - A Crucial Problem in Time-Sensitive Networks

Josef Grus, Claire Hanen, Zdeněk Hanzálek · 2025

Read Periodic Chains Scheduling on Dedicated Resources - A Crucial Problem in Time-Sensitive Networks by Josef Grus, Claire Hanen, Zdeněk Hanzálek (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2503-19003.txt.

Introduction

Modern cars and planes shuttle sensor readings to actuators on strict repeating clocks, and one late message can break the system. Josef Grus, Claire Hanen, and Zdeněk Hanzálek study how to schedule those message chains in time-sensitive networks. Each message hops across dedicated links, and the paper proves the scheduling problem is strongly NP-hard even with tidy, harmonic periods.

The team builds a solver that pairs a constraint programming warm start with local search and a first-fit rule. It finds good schedules in minutes for cases with thousands of tasks running at full load. A second polishing step cuts the start-to-end delay slack even further. Tests on car, plane, and factory style cases show the method holds up where older tools stall.

Catalog record

CREATORJosef Grus, Claire Hanen, Zdeněk Hanzálek
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE100 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2503-19003

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Periodic Chains Scheduling on Dedicated Resources - A Crucial Problem in Time-Sensitive Networks Josef Grus, Claire Hanen, Zdeněk Hanzálek Abstract Periodic messages transfer data from sensors to actuators in cars, planes, and complex production machines. When considering a given routing, the unicast message starts at its source and goes over several dedicated resources to reach its destination. Such unicast message can be represented as a chain of point-to-point communications. Thus, the scheduling of the periodic chains is a principal problem in time-triggered Ethernet, like IEEE 802.1Qbv Time-Sensitive Networks. This paper studies a strongly NP-hard periodic scheduling problem with harmonic periods, task chains, and dedicated resources. We analyze the problem on several levels and provide proofs of complexity and approximation algorithms for several special cases. We describe a solution methodology to find a feasible schedule that minimizes the chains’ degeneracy related to start-to-end latency normalized in the number of periods. We use the local search with the first fit scheduling heuristic, which we warm-start with a constraint programming model. This notably improves the schedulability of instances with up to 100% utilization and thousands (and more) of tasks, with high-quality solutions found in minutes. An efficient constraint programming matheuristic significantly reduces the degeneracy of the found schedules even further. The method is evaluated on sets of industrial-, avionic-, and automotive-inspired instances. Journal: Computers & Operations Research † † highlights: Offset schedules guarantee worst-case degeneracy for acyclic instances Constraint programming successfully initializes the local search Per-period matheuristic efficiently improves existing schedules Publicly available diverse set of PSP instances 1 Introduction 1.1 Motivation Periodic events and processes play an essential role in many application domains. To ensure efficient and deterministic data exchange among different parts of the application, engineers need to configure communication protocols to satisfy timing and throughput requirements. For example, with the advent of self-driving cars [ 1 ] requiring a deterministic exchange of high-volume data, the communication network may quickly become a congestion point, and efficient schedules are needed to satisfy all safety-relevant features. When considering a given routing, the periodic (unicast) message goes from a sensor over several dedicated resources to reach its actuator. Thus, the message can be represented as a chain of point-to-point communications performed on communication links. Ethernet is widely used in everyday life due to its high throughput and availability of SW stacks. Still, it lacks time determinism, essential for real-time applications, such as in-vehicle networks, industrial production lines, and audio streaming, that are very sensitive to delays. Time-sensitive networking (TSN) is a set of new standards that enables sending messages in a time-triggered manner. To use TSN efficiently and satisfy various requirements, many researchers [ 2 , 3 ] have developed algorithms that can synthesize a schedule of periodic messages. Their results are versatile, but the network utilization and algorithm performance are often very low. Thus, in this paper, we omit a complex behavior of the TSN (link delays, queues, deadlines, frame isolation, see [ 4 ] ), and we concentrate on a crucial part of this problem: the scheduling of periodic tasks. We focus on harmonic periods of the messages (i.e., for each pair of distinct periods, it holds that the longer period is divisible by the shorter one) that are widely used in engineering practice and help with the tractability of Periodic Scheduling Problem (PSP). 1.2 Related Work Scheduling of periodic tasks has been studied from many different directions, as is outlined in [ 5 ] . Crucial results regarding the complexity of the scheduling of periodic tasks on a single resource were presented in [ 6 ] , where the authors proved that the problem with non-preemptive tasks is strongly NP-complete. However, in [ 7 ] , it was shown that if both the periods and processing times of the tasks are harmonic, a feasible schedule can be found in polynomial time. Scheduling of both harmonic and non-harmonic periodic problems and several special cases were studied in [ 8 , 9 ] . The authors presented a local schedulability condition for the general case of PSP. Motivated by the desire to increase the schedulability for highly-utilized instances, alternative views of PSPs based on bin-trees [ 10 ] and bin packing [ 11 , 12 , 13 ] were presented. These perspectives enabled the relevant authors to devise heuristics and exact methods to find feasible schedules efficiently. PSPs are often found in the domains of avionics and automotive. Building on their previous work, authors of [ 14 ] used Integer Linear Programming (ILP) to partition tasks on different processors of modern aircraft. In [ 15 ] , the goal was to schedule tasks in the avionics domain to maximize a leeway between them. This way, the occasional increase in the processing time of the task would not interfere with the rest of the schedule. A game-theoretic approach to tackling a similar problem was presented in [ 16 ] . In [ 17 ] , the authors tackled the scheduling of so-called partitions on shared processors. Their idea utilized a greedy heuristic, streamlining an otherwise exhaustive approach without a significant loss in the quality of the schedules. In [ 18 ] , communication between modules of the aircraft is considered, and the authors solve it with constraint-generating ILP procedure. In the automotive domain, many papers tackle scheduling problems related to specific protocols and architectures. In [ 19 ] , the authors schedule tasks for AUTOSAR architecture to eliminate load peaks. ILP and heuristics for the same architecture were also investigated in [ 20 ] . FlexRay, a protocol often coupled with the AUTOSAR specification, was studied in [ 11 ] and more recently in [ 21 , 22 ] . In the latter, the authors consider multiple message variants so the same schedule can be repurposed for different vehicle models. Apart from communications, PSPs apply to manufacturing and maintenance. In [ 23 , 24 ] , the scheduling problems with (almost) periodic maintenance windows are studied; there, the maintenance task is frequently repeated, while the manufacturing tasks are essentially aperiodic. This framework is helpful in practice since regularly inspecting the machines reduces the risk of failures. A practical application can be found in [ 25 ] , where the authors schedule patients’ non-preemptive treatments around the medical machine’s maintenance. The rest of this section focuses on papers regarding PSP with dedicated resources, which is the main focus of this paper. Messages are transmitted through the network, and the tasks are assigned to resources beforehand, given the network’s routing. In [ 26 ] , the authors co-optimize the resource utilization as well as the control performance of the system that relies on signals from sensors passed through the network. In [ 27 ] , large-neighborhood search is used to improve control-wise properties of the schedules. Another domain is scheduling for cloud radio access networks. In [ 28 , 29 ] , the authors focus on periodic scheduling with a single period and uniform processing times of the messages. Especially in the latter, the no-buffering constraint complicates the problem. The authors provide a polynomial scheduling algorithm applicable, when the network load is sufficiently low, and a general greedy method used in other cases. Early work on

Read the complete text