Schedule Synthesis for Synchronous Dataflow Models with Lower and Upper Timing Bounds

Homogeneous Synchronous DataFlow Graphs (HSDFGs) have become a popular method for analysing the performance of manufacturing systems. Manufacturing tasks, modelled by actor firings in an HSDFG, are bounded by their earliest possible starting times, determined by the completion of preceding tasks. Taking into account these lower bounds, an HSDFG represents different possible task schedules for these tasks, namely any actor firing scheme that satisfies these lower bounds. However, in some cases, tasks in a manufacturing system must be completed before a deadline, which introduces an upper bound. Additionally, the relative start times between tasks may need to adhere to a lower bound. Such lower and upper bounds are not naturally supported by classical HSDFGs. In such cases, an HSDFG cannot represent all relevant aspects of the behaviour of a manufacturing system. This article extends the HSDFG model to support the specification of lower-bound and upper-bound constraints on timing differences between actor-firing starts and completions. The paper then presents a new method for transforming extended HSDFGs into a (max, +) linear system in the form of its state-space matrices. This system can be used to synthesize a task schedule that adheres to the specified lower and upper bounds while achieving the earliest possible execution times, optimizing throughput or makespan. We illustrate the necessity for specifying lower and upper bounds, and the application of our techniques, with a manufacturing system case study.