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

What is it about?

Homogeneous Synchronous Dataflow (HSDF) is a widely used model of computation for analysing the timing behaviour of tasks in manufacturing systems. These models allow the efficient synthesis of schedules that define the start times of manufacturing tasks. These schedules maximize manufacturing productivity and offer insight into the system's overall behaviour. This paper presents manufacturing case studies for which it is necessary to impose additional lower and upper timing bounds on start times of tasks beyond the usual sequential execution constraint, something that is not possible with traditional HSDF. We describe how these constraints can be modelled and introduce a novel technique with which we can synthesize task schedules for HSDF models that incorporate these added timing constraints.

Featured Image

Why is it important?

Many manufacturing systems must adhere to lower and upper bound constraints on the timing of manufacturing tasks. For instance, a product that must be placed before glue hardens, a conveyor belt that must deliver a product within a specific time frame to prevent congestion, or an inspection that must be completed before a product moves out of sight. If such constraints are not present in the model, the schedule that is synthesized does not represent correct manufacturing behaviour. Our proposed method extends the widely used HSDF modelling formalism to express these constraints and efficiently synthesize schedules that respect these constraints while maximizing productivity.