|国家预印本平台
首页|Periodic Chains Scheduling on Dedicated Resources -- A Crucial Problem in Time-Sensitive Networks

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

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

来源:Arxiv_logoArxiv
英文摘要

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 of generality and complexity and provide the corresponding proofs. 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.

Josef Grus、Zdeněk Hanzálek、Claire Hanen

10.1016/j.cor.2025.107072

通信无线通信

Josef Grus,Zdeněk Hanzálek,Claire Hanen.Periodic Chains Scheduling on Dedicated Resources -- A Crucial Problem in Time-Sensitive Networks[EB/OL].(2025-03-24)[2025-05-04].https://arxiv.org/abs/2503.19003.点此复制

评论