Many real-world applications deal with the problem of scheduling repetitive tasks in a periodic fashion. Often, such tasks involve precedence constraints and require sharing a limited set of, possibly heterogeneous, resources to enable their execution. This results in a problem that combines resource allocation and periodic task scheduling, which we refer to as the Allocation and Periodic Scheduling Problem (APSP). This paper proposes two linear-programming models for solving the APSP based on a novel modeling approach. The first model is a monolithic Mixed-Integer Linear Programming (MILP) model and the second one is a MILP model with a Benders decomposition. Both models allow finding an optimal resource allocation and periodic schedule that minimizes the period, i.e., they optimize throughput. In contrast to earlier work on optimally solving the APSP, our approach uses a time bound on considered start times of task executions, meaning that only the repetitions starting within the time bound are considered in the solving process. This effectively constrains the search space for finding optimal schedules. For feasible problem instances, we prove that there exists an optimal schedule in which all tasks execute at least once within this time bound, showing the soundness of the approach. Where earlier models for the APSP are in essence non-linear, our approach results in easier-to-solve linear models. Experiments show that, in comparison to the state of the art, our models are less prone to numerical instabilities and find optimal solutions more often, while being competitive in solve time.

Abstract An execution trace is a model of a single system behavior. Execution traces occur everywhere in the system’s lifecycle as they can typically be produced by executable models, by prototypes of (sub)systems, and by the system itself during its operation. An execution trace can be visualized and analyzed with various techniques, providing insight into the dynamic behavior, performance, bottlenecks, etc., of the system. In this paper, we present the Trace tool of the Eclipse Trace4cps project for the visualization and analysis of execution traces. A prominent application is the trace-based performance engineering of embedded or cyber-physical systems. Performance is an important system quality, as it can give a competitive advantage. Reasoning about system-level performance in such systems, however, is hard due to its cross-cutting nature. We show how the Trace tool can support this by various examples. Performance engineering is not the only application of the Trace tool, however: it supports system analysis in a wide range of situations.

Product family development facilitates reuse across all phases of systems engineering; in case of model-based systems engineering, this reuse involves the models as well. Introducing a model-based way of working is challenging, especially for product family development. This paper describes a case of introducing a modelbased way of working in brown-field product family development. We explain how we developed a master model, i.e. a library of model elements, to predict and optimize the productivity of a family of industrial production systems. Using this master model, we construct models of existing and yet-to-be-developed product family members by configuring and combining the appropriate library elements. We use system and model execution traces to validate the productivity models. For this, we developed a master transformation, i.e. a library of execution trace transformation rules, to unify system and model execution traces. Besides the master model and the master transformation, we present lessons learned regarding the introducing a model-based way of working. This proves both technically and organizationally complex, especially for brown-field product family development, but besides the intended prediction and optimization, it brings benefits with respect to capturing domain knowledge and system validation.

System-Performance Engineering (SysPE) encompasses modeling formalisms, methods, techniques, and industrial practices to design systems for performance, where performance is taken integrally into account during the whole system life cycle. Industrial SysPE state of practice is generally model-based. Due to the rapidly increasing complexity of systems, there is a need to develop and establish model-driven methods and techniques. To structure the field of SysPE, we identify (1) industrial challenges motivating the importance of SysPE, (2) scientific challenges that need to be addressed to establish model-driven SysPE, (3) important focus areas for SysPE and (4) best practices. We conducted a survey to collect feedback on our views. The responses were used to update and validate the identified challenges, focus areas, and best practices. The final result is presented in this paper. Interesting observations are that industry sees a need for better design-space exploration support, more than for additional performance modeling and analysis techniques. Also tools and integral methods for SysPE need attention. From the identified focus areas, scheduling and supervisory control is seen as lacking established best practices.

Cyber-physical systems (CPS) are complex, heterogeneous, and dynamic systems, spanning hardware and software components ranging from edge devices to cloud platforms. CPS need to satisfy many rigorous constraints, e.g., with respect to deadlines, safety, and quality, yielding a large configuration space where only a limited number of configurations meet the constraints and only a fraction are optimal regarding certain qualities. Finding the optimal configurations is hard, especially during runtime operation. We present QRML, the Quality and Resource Management domain-specific Language, and an accompanying toolset. QRML enables specifying heterogeneous hardware/software systems and their composition and configurations conveniently, automated reasoning about them, and generating implementation artifacts like quality and resource monitoring templates. A QRML model consists of a hierarchy of components. Component specifications express constraints and requirements, that may serve multiobjective quality and resource optimization and exploration purposes. The QRML toolset offers language support, visualizations, documentation generation, template-code generation, and constraint-solving support.

(m, k)-firm real-time tasks must meet the deadline of at least m jobs out of any k consecutive jobs to satisfy the firmness requirement. Scheduling of an (m,k)-firm task requires firmness analysis, whose results are used to provide system-level guarantees on the satisfaction of firmness conditions. We address firmness analysis of an (m, k)-firm task that is intended to be added to a set of asynchronous tasks scheduled under a Static-Priority Preemptive (SPP) policy. One of the main causes of deadline misses in periodic tasks running under an SPP policy is interference from higher priority tasks. Since the synchrony between the newly added task and higher priority tasks is unknown, the interference from the higher priority tasks is also unknown. We propose an analytic Firmness Analysis (FAn) method to obtain a synchrony that results in the maximum minimum number of deadline hit jobs in any k consecutive jobs of the task. Scalability of FAn is compared with that of existing work - a brute-force search approach - and a timed-automata model of the problem that is analysed using the reachability check of the Uppaal model checker. Our method substantially reduces the complexity of the analysis.

High-end manufacturing systems are cyber-physical systems, where productivity depends on the close cooperation of mechanical (physical) and scheduling (cyber) aspects. Mechanical and control constraints impose minimal and maximal time differences between events in the product flow. Sequence-dependent constraints are used by a scheduler to optimize system productivity while satisfying operational requirements. The numerous constraints in a schedule are typically related to a relatively small set of parameters, such as speeds, lengths, or settling times. We contribute a parametric critical path algorithm that identifies bottlenecks in terms of the feasible parameter combinations. This algorithm allows analysis of schedules to identify bottlenecks in terms of the underlying cause of constraints. We also contribute a way to find Pareto-optimal cost-performance tradeoffs and their associated parameter combinations. These results are used to quantify the impact of relaxing constraints that hinder system productivity.

Multi-scale dataflow models have actors acting at multiple granularity levels, e.g., a dataflow model of a video processing application with operations on frame, line, and pixel level. The state of the art timing analysis methods for both static and dynamic dataflow types aggregate the behaviours across all granularity levels into one, often large iteration, which is repeated without exploiting the structure within such an iteration. This poses scalability issues to dataflow analysis, because behaviour of the large iteration is analysed by some form of simulation that involves a large number of actor firings. We take a fresh perspective of what is happening inside the large iteration. We take advantage of the fact that the iteration is a sequence of smaller behaviours, each captured in a scenario, that are typically repeated many times. We use the (max ,+) linear model of dataflow to represent each of the scenarios with a matrix. This allows a compositional worst-case throughput analysis of the repeated scenarios by raising the matrices to the power of the number of repetitions, which scales logarithmically with the number of repetitions, whereas the existing throughput analysis scales linearly. We moreover provide the first exact worst-case latency analysis for scenario-aware dataflow. This compositional latency analysis also scales logarithmically when applied to multi-scale dataflow models. We apply our new throughput and latency analysis to several realistic applications. The results confirm that our approach provides a fast and accurate analysis.

This paper provides an overview of the architecture for self-organizing, co-operative and robust Building Automation Systems (BAS) proposed by the EC funded FP7 SCUBA1project. We describe the current situation in monitoring and control systems and outline the typical stakeholders involved in the case of building automation systems. We derive seven typical use cases which will be demonstrated and evaluated on pilot sites. From these use cases the project designed an architecture relying on six main modules that realize the design, commissioning and operation of self-organizing, co-operative, robust BAS.

There is a strong push towards smart buildings that aim to achieve comfort, safety and energy efficiency, through building automation systems (BAS) that incorporate multiple subsystems such as heating and air-conditioning, lighting, access control etc. The design, commissioning and operation of BAS is already challenging when handling an individual subsystem; however when introducing co-operation between systems the complexity increases dramatically. Balancing the contradictory requirements of comfort, safety and energy efficiency and coping with the dynamics of constantly changing environmental conditions, usage patterns, user needs etc. is a demanding task. This paper outlines an approach to the systematic engineering of cooperating, adaptive building automation systems, which aims to formalize the engineering approach in the form of an integrated tool chain that supports the building stakeholders to produce site-specific robust and reliable building automation.

Pareto analysis is a broadly applicable method to model and analyze tradeoffs in multi-objective optimization problems. The set of Pareto optimal solutions is guaranteed to contain the best solution for any arbitrary cost function or selection procedure. This work introduces a method to explicitly take uncertainty into account during Pareto analysis. A solution is not modeled by a single point in the solution space, but rather by a set of such points. This is useful in settings with much uncertainty, such as during model-based design space exploration for embedded systems. A bounding-box abstraction is introduced as a finite representation of Pareto optimal solutions under uncertainty. It is shown that the set of Pareto optimal solutions in the proposed approach still captures exactly the potentially best solutions for any cost function as well as any way of reducing the amount of uncertainty. During model-based design space exploration, for instance, design and implementation choices that are made during the development process reduce the amount of uncertainty. Steps in such a refinement trajectory can render previously Pareto optimal solutions sub optimal. The presented results provide a way to ensure that early selections in the refinement process remain valid.

We show that timed automata can be used to model and to analyze timeliness properties of embedded system architectures. Using a case study inspired by industrial practice, we present in detail how a suitable timed automata model is composed. Exact upper bounds on the timeliness properties can be found with the Uppaal model checker for a number of usage scenarios. We compare our results with three other performance modeling techniques. This comparison shows that if the state space of the model is tractable, Uppaal gives the most accurate results at similar cost. The proposed modeling strategy can be automated, which alleviates the difficulty and error-proneness of manually constructing timed automata models