Periodic scheduling of marked graphs using balanced binary words

DOI10.1016/J.TCS.2012.08.012MaRDI QIDQ1758156zbMATH OpenOpenAlexFDO

Authors Jean-Vivien Millo, Robert de Simone

Publication date 8 November 2012

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1202.4912

zbMATH Keywords

balanced binary wordconnected marked graphsscheduling graphs

Mathematics Subject Classification ID

Network design and communication in computer systems (68M10) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Combinatorics in computer science (68R05) Graph theory (including graph drawing) in computer science (68R10)

Abstract: This report presents an algorithm to statically schedule live and strongly connected Marked Graphs (MG). The proposed algorithm computes the best execution where the execution rate is maximal and place sizes are minimal. The proposed algorithm provides transition schedules represented as binary words. These words are chosen to be balanced. The contributions of this paper is the proposed algorithm itself along with the characterization of the best execution of any MG.

Recommendations

• Periodic schedules for linear precedence constraints
• scientific article; zbMATH DE number 4092766
• Scheduling cyclic tasks with binary periods
• scientific article; zbMATH DE number 850294
• Scheduling with timed automata

Cites work

• A simple characterization of Sturm numbers
• Abstraction of Clocks in Synchronous Data-Flow Systems
• Balanced sequences and optimal routing
• Free Choice Petri Nets
• scientific article; zbMATH DE number 627763 (Why is no real title available?)
• scientific article; zbMATH DE number 1737190 (Why is no real title available?)
• scientific article; zbMATH DE number 932432 (Why is no real title available?)
• Marked directed graphs
• Operations on Christoffel words
• Sturmian words, Lyndon words and trees
• Un domaine très ouvert : les problèmes d'ordonnancement

Cited in

(2)

• An improved approach for marking optimization of timed weighted marked graphs
• Explicit routing schemes for implementation of cellular automata on processor arrays

This page was built for publication: Periodic scheduling of marked graphs using balanced binary words

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1758156)