Passive surveillance systems (PSS) are used to detect and track various targets by processing the electromagnetic signals they release. The study and design of the resource management algorithm for these systems revealed several phenomena and combinatorial problems with crucial theoretical properties. In this article, we first prove the completeness of the algorithm used to generate receiver settings that determine which frequency bands the PSS monitors. Next, we formulate a new optimization problem called multiple-interval coverage (MIC), which is used to determine how often each of the generated settings must be used by the PSS. We show that the MIC problem is closely related to the multicover problem, which is an extension of the well-known set cover problem. The uniqueness of MIC stems from the fact that both covered elements and covers are multiple-intervals. We propose a notation to distinguish between different variants of the problem and prove that some of them can be solved in polynomial time. Finally, we prove that the MIC problem is NP-hard even when restricted to 2-interval covers.

Constraint Programming (CP) is a powerful optimization method that provides optimality guarantees, but due to its exact nature, its scalability to large instances is often limited. To address this, we propose a hybrid approach that combines a CP solver with heuristic methods, directly and asynchronously exchanging solutions and objective values during runtime. The hybrid parallel configuration yields faster convergence to good solutions across various problem domains than the solver alone, while retaining the ability to guarantee optimality, leveraging the complementary nature of the CP solver and heuristics. The efficiency of this approach is evaluated on three well-known scheduling problems and three well-known routing problems. Noticeable improvements are observed for the Flow-shop Scheduling Problem (FSSP), the Traveling Salesman Problem (TSP), and the Vehicle Routing Problem with Time Windows (VRP-TW). Even for problems where improvements are marginal, the portfolio of methods increases the robustness of the approach.

Multi-Processor Systems-on-Chip (MPSoC) can deliver high performance needed in many industrial domains, including aerospace. However, their high power consumption , combined with avionics safety standards , brings new thermal management challenges. This paper investigates techniques for offline thermal-aware allocation of periodic tasks on heterogeneous MPSoCs running at a fixed clock frequency, as required in avionics. The goal is to find the assignment of tasks to (i) cores and (ii) temporal isolation windows, as required in ARINC 653 standard, while minimizing the MPSoC temperature. To achieve that, we formulate a new optimization problem , we derive its NP-hardness, and we identify its subproblem solvable in polynomial time . Furthermore, we propose and analyze three power models, and integrate them within several novel optimization approaches based on heuristics, a black-box optimizer, and Integer Linear Programming (ILP). We perform the experimental evaluation on three popular MPSoC platforms (NXP i.MX8QM MEK, NXP i.MX8QM Ixora, NVIDIA TX2) and observe a difference of up to 5.5 °C among the tested methods (corresponding to a 22% reduction w.r.t. the ambient temperature). We also show that our method, integrating the empirical power model with the ILP, outperforms the other methods on all tested platforms.

International audience

Lap time minimization is of interest in every automotive racing competition. However, finding an optimal racing line is not a trivial task. In this work, we study one particular part of the racing line optimization problem, namely the track segmentation problem. We analyze how different track segmentation methods influence the racing line quality. Further, we present Automated Segmentation based on Curvature (ASC) method, which creates segments adaptively according to the track layout. Using lap time estimation based on a vehicle model, we compare ASC with two other methods from the literature. The preliminary results show that optimization based on ASC is able to outperform the other tested approaches by up to 15 % for the given number of iterations while converging to a good solution 3.88 times faster than the second-best method.

This paper investigates the problem of trajectory planning for autonomous vehicles at unsignalized intersections, specifically focusing on scenarios where the vehicle lacks the right of way and yet must cross safely. To address this issue, we have employed a method based on the Partially Observable Markov Decision Processes (POMDPs) framework designed for planning under uncertainty. The method utilizes the Adaptive Belief Tree (ABT) algorithm as an approximate solver for the POMDPs. We outline the POMDP formulation, beginning with discretizing the intersection's topology. Additionally, we present a dynamics model for the prediction of the evolving states of vehicles, such as their position and velocity. Using an observation model, we also describe the connection of those states with the imperfect (noisy) available measurements. Our results confirmed that the method is able to plan collision-free trajectories in a series of simulations utilizing real-world traffic data from aerial footage of two distinct intersections. Furthermore, we studied the impact of parameter adjustments of the ABT algorithm on the method's performance. This provides guidance in determining reasonable parameter settings, which is valuable for future method applications.

Due to its diversity, the physical design of the Analog and Mixed-Signal Integrated Circuits is not as automated as the physical design of digital Integrated Circuits. The placement process is one of the critical steps of the physical design, and automating it would significantly shorten the design time. We formulate the placement process using an Integer Linear Programming approach, with features to support a specific semiconductor technology. We include an enumeration of possible variants of the circuit’s topological structures, which are afterward considered during optimization. We use the Gurobi solver to minimize both the approximate wire length and the placement area. The results were evaluated by layout design experts and compared with manual designs. We also utilize a graph drawing-based method to generate an initial feasible solution to warm start the Integer Linear Programming solver, which noticeably improves the performance and shortens the computation time (5x to 15x), a nd makes the approach applicable even for larger problem instances containing 100 independent elements. Experiments performed on real-life industrial problem instances show that our graph drawing-enhanced approach can produce high-quality placement in a much shorter time than the designers need.

Modern industrial production with alternative process plans and the use of complex machine equipment increases requirements for its intralogistics operations in terms of efficiency, resilience, and flexibility. One of the most common solutions for transporting workpieces between the manufacturing stations is a system of conveyor belts where each conveyor rotates in a fixed direction at a constant speed. The movement of the individual workpieces can be controlled only indirectly via a set of gates connecting different carousels. In this paper, we aim to increase the flexibility of conveyor belt systems by carefully scheduling the gates to route the workpieces efficiently along the production line according to their process plans. The key component of our solution is the discretization of both the time and positions on the belts to represent the system by a directed graph with circular components. To find the routing of workpieces that minimizes the total flow time, we have reduced the problem to the integer multi-commodity flow on the time-expanded network with an extension for the vertex precedences. Despite the simplicity of the formulation, the results suggest that off-the-shelf solvers can find optimized routing for instances with tens of workpieces and more than hundreds of belt positions within a few minutes.

The problem of path planning for automated parking is usually presented as finding a collision-free path from initial to goal positions, where three out of four parking slot edges represent obstacles. We rethink the path planning problem for parallel parking by decomposing it into two independent parts. The topic of this paper is finding optimal parking slot entry positions. Path planning from initial to entry position is out of scope here. We show the relation between entry positions, parking slot dimensions, and the number of backward-forward direction changes. This information can be used as an input to optimize other parts of the automated parking process.

In many safety-critical applications, Multi-Processor Systems-on-Chip (MPSoC) must operate within a given thermal envelope under harsh environmental conditions. Meeting the thermal requirements often requires using advanced task allocation and scheduling techniques that are guided by detailed power models. This paper introduces a method that has the potential to simplify the creation of such models. It constructs so-called heat maps from thermal camera images. By comparing the heat maps of different workloads, we identify the locations of on-chip components and the amount of heat produced by them. We demonstrate our method on the i.MX8QuadMax chip from NXP, where we identify the locations of CPU clusters, bigger CPU cores, GPUs, and DRAM controllers.

In every timed car race, the goal is to drive through the racing track as fast as possible. The total time depends on selection of the racing line. Following a better racing line often decides who wins. In this paper, we solve the optimal racing line problem using a genetic algorithm. We propose a novel racing line encoding based on a homeomorphic transformation called Matryoshka mapping. We evaluate the fitness of racing lines by lap time estimation using a vehicle model suitable for F1/10 autonomous racing competition. By comparing to the former state-of-the-art, we show that our method is able to find racing lines with lower lap times. Specifically, on one of the testing tracks, we achieve 2.5% improvement.

The demand for high-performance computing leads to the adoption of modern Multi-Processor System-on-Chip platforms in the avionics domain, where many applications are safety-critical. To fulfill the safety requirements, it is vital to avoid the platform’s overheating. In this paper, we propose a task mapping method, MultiPAWS, for thermal-aware allocation of the safety-critical avionics workloads under time isolation constraints. With the help of MultiPAWS, we jointly find an optimal number of scheduling windows and their lengths and optimal mapping of the workload to these windows and available CPU cores. To guide the optimization, we introduce a thermal model based on power-characteristic coefficients, which we experimentally identify for a benchmark dataset on NXP i.MX8QuadMax platform (based on ARMv8 big.LITTLE architecture). Furthermore, to mimic the execution of safety-critical avionics applications, we introduce DEmOS, an open-source Linux-based scheduler. DEmOS provides a time-partitioned scheduling similar to the ARINC 653 standard. We use DEmOS for the experimental evaluation on the i.MX8 platform. The experimental results suggest that MultiPAWS achieves over a 12% decrease of the platform temperature compared to the minimum-utilization-based approach. Moreover, we demonstrate how MultiPAWS can be used in design space exploration for finding the tradeoff between the platform temperature and the length of the scheduling hyper-period.

Convergecast and broadcast operations in WSN-based applications impose demands in terms of energy efficiency, reliability, and timeliness QoS properties which existing protocols struggle to fulfill. The Deterministic Synchronous Multi-channel Extension (DSME) mechanism introduced in the IEEE 802.15.4e standard constitutes a promising solution to address these stringent QoS requirements, by enabling significant enhancements to the legacy IEEE 802.15.4 protocol, such as multi-channel communications, reduction of the Contention-Access Period, and group acknowledgments. However, the DSME-IEEE 802.15.4e standards do not propose a mechanism to build a traffic-aware schedule that assigns a frequency channel and time-slots to each transmission. Therefore, in this paper, we show how to configure the DSME parameters for the convergecast and broadcast operations while having in mind the above-mentioned QoS properties. In that direction, we propose an exact traffic-aware scheduling algorithm, based on Integer Linear Programming (ILP), that enables the system designers to optimize the configuration of all the required parameters of the DSME-IEEE 802.15.4e so that QoS requirements are met.

Automotive software implements different functionalities as multiple control applications sharing common platform resources. Although such applications are often developed independently, the control performance of the resulting system depends on how these applications are integrated. A key integration challenge is to efficiently schedule these applications on shared resources with minimal control performance degradation. We formulate this problem as that of scheduling multiple distributed periodic control tasks that communicate via messages with non-zero jitter. The optimization criterion used is a piecewise linear representation of the control performance degradation as a function of the end-to-end latency of the application. The three main contributions of this article are: 1) a constraint programming (CP) formulation to solve this integration problem optimally on time-triggered architectures; 2) an efficient heuristic called Flexi; and 3) an experimental evaluation of the scalability and efficiency of the proposed approaches. In contrast to the CP formulation, which for many real-life problems might have unacceptably long running times, Flexi returns nearly optimal results (0.5 percent loss in control performance compared to optimal) for most problems with more acceptable running times.

Many modern computing platforms in the safety-critical domains are based on heterogeneous Multiprocessor System-on-Chip (MPSoC). Such computing platforms are expected to guarantee high-performance within a strict thermal envelope. This paper introduces a testbed for thermal and performance analysis. The testbed allows the users to develop advanced scheduling and resource allocation techniques aiming at finding an optimal trade-off between the peak temperature and the achieved performance. This paper presents a new, open-source Thermobench tool for data collection and analysis of user-defined workloads. Furthermore, a methodology for shortening the time needed for the data collection is proposed. Experiments show that a significant amount of time can be saved. Specifically, time reduction from 60 minutes to 15 minutes is achieved with the i.MX8 MPSoC from NXP while running a set of user-defined benchmarks that stress CPU, GPU, and different levels of the memory hierarchy.

This paper, inspired by a real production process of steel hardening, investigates a scheduling problem to minimize the idle energy consumption of machines. The energy minimization is achieved by switching a machine to some power-saving mode when it is idle. For the steel hardening process, the mode of the machine (i.e., furnace) can be associated with its inner temperature. Contrary to the recent methods, which consider only a small number of machine modes, the temperature in the furnace can be changed continuously, and so an infinite number of the power-saving modes must be considered to achieve the highest possible savings. To model the machine modes efficiently, we use the concept of the energy function, which was originally introduced in the domain of embedded systems but has yet to take roots in the domain of production research. The energy function is illustrated with several application examples from the literature. Afterward, it is integrated into a mathematical model of a scheduling problem with parallel identical machines and jobs characterized by release times, deadlines, and processing times. Numerical experiments show that the proposed model outperforms a reference model adapted from the literature.

In this paper, we investigate the use of deep learning for solving a classical NP-Hard single machine scheduling problem where the criterion is to minimize the total tardiness. Instead of designing an end-to-end machine learning model, we utilize well known decomposition of the problem and we enhance it with a data-driven approach. We have designed a regressor containing a deep neural network that learns and predicts the criterion of a given set of jobs. The network acts as a polynomial-time estimator of the criterion that is used in a single-pass scheduling algorithm based on Lawler's decomposition theorem. Essentially, the regressor guides the algorithm to select the best position for each job. The experimental results show that our data-driven approach can efficiently generalize information from the training phase to significantly larger instances (up to 350 jobs) where it achieves an optimality gap of about 0.5%, which is four times less than the gap of the state-of-the-art NBR heuristic.

Thanks to the standards being developed by IEEE Time-Sensitive Networking (TSN) Task Group, the classical IEEE 802.1 Ethernet architecture is now enhanced to accommodate real-time and safety-critical requirements emerging in various cyber-physical systems. The deterministic nature of the communication is achieved through the time-triggered traffic, which requires introducing strict scheduling constraints that may be an obstacle in finding a feasible schedule. In this article, we propose a simple hardware enhancement of a switch along with a relaxed scheduling constraint that increases schedulability and throughput of the time-triggered traffic but maintains the deterministic nature and timeliness guarantees in a TSN network. We give a formal proof to justify the claims and an algorithm benchmarking and experimental validation to demonstrate the gains. The results show that the number of flows that can be scheduled in the model with the relaxed constraint is on average by 75.1 % larger than in the traditional model.

The design of Medium Access Control (MAC) protocol for Wireless Sensor Networks (WSNs) with both limited energy consumption and data delivery time is crucial for industrial and control applications. Since Time Division Multiple Access (TDMA) MAC eliminates the collision occurrence and seeks the minimization of the number of time-slots assigned to each node, the energy consumption of the nodes is reduced. Furthermore, with the proper allocation of the time-slots to the nodes, the transmission delay can be significantly reduced. In this article, we propose TDMA scheduling algorithm for Cluster-tree topology WSNs that meets the timeliness and the energy demands. The algorithm adopts an elegant approach that expresses the timing constraints of the data transmissions as an integer multiple of the length of the schedule period. Moreover, since the distributed algorithm is well-suited to the scarce resources of the WSNs, we focus on the distributed methods that allow each cluster to come up with its allocated time-slots. The algorithm is based on graph theory, such as distributed shortest path, distributed topological ordering, and distributed graph coloring algorithms. The efficiency of the algorithm, regarding the elapsed time to construct the schedule and the energy consumption, is evaluated over benchmark instances up to several thousands of nodes.

This work studies a problem of scheduling non-preemptive independent jobs on dedicated machines while considering an energy consumption limit. The problem is motivated by energy-demanding production processes, such as glass tempering and steel hardening, in which a material is heated to high temperature in furnaces. The production companies have contracts with electric utilities that specify a maximum energy consumption limit. If the heating in the furnaces is not planned carefully, the energy spikes overshoot the energy consumption limit, and the companies must pay large penalty fees. In this paper, we propose two exact methods that find schedules with the minimum makespan such that the energy limit is satisfied. The first proposed method is a Constraint Programming model and the second one finds the optimal solution by iteratively re-solving a Mixed Integer Linear Programming model with a decreasing scheduling horizon. The iterative algorithm exploits the fact that the start times do not need to be modeled explicitly, which leads to an efficient method for solving instances with a higher number of shorter jobs. The experimental results show that our methods outperform an adapted approach from the literature for a related problem.

This paper deals with a scheduling problem that emerges in the production of water tubes of different sizes that require reconfiguration of the machines. The reconfiguration of the machines leads to the notion of sequence-dependent setup times between tasks. These setups are often performed by a single person who cannot serve more than one machine at the same moment, i.e., the setups must not overlap. Surprisingly, the problem with non-overlapping setups has received only a little attention so far. To solve this problem, we propose an Integer Linear Programming formulation, Constraint Programming models and a hybrid heuristic that leverages the strength of Integer Linear Programming in the shortest Hamiltonian path problem and the efficiency of Constraint Programming at sequencing problems with makespan minimization. The experimental evaluation shows that among the proposed exact approaches, the Constraint Programming is a superior method being able to solve instances with 3 machines and up to 11 tasks on each machine to optimality within a few seconds. The proposed hybrid heuristic attains high-quality solutions for instances with 50 machines and up to 116 tasks on each machine.

Many real-world scheduling problems are characterized by uncertain parameters. In this paper, we study a classical parallel machine scheduling problem where the processing time of jobs is given by a normal distribution. The objective is to maximize the probability that jobs are completed before a given common due date. This study focuses on the computational aspect of this problem, and it proposes a Branch-and-Price approach for solving it. The advantage of our method is that it scales very well with the increasing number of machines and is easy to implement. Furthermore, we propose an efficient lower bound heuristics. The experimental results show that our method outperforms the existing approaches.

Finding a collision-free path for autonomous parking is usually performed by computing geometric equations, but the geometric approach may become unusable under challenging situations where space is highly constrained. We propose an algorithm based on Rapidly-Exploring Random Trees Star (RRT*), which works even in highly constrained environments and improvements to RRT*-based algorithm that accelerate computational time and decrease the final path cost. Our improved RRT* algorithm found a path for parallel parking maneuver in 95 % of cases in less than 0.15 seconds.

The complexity of embedded application design is increasing with growing user demands. In particular, automotive embedded systems are highly complex in nature, and their functionality is realized by a set of periodic tasks. These tasks may have hard real-time requirements and communicate over an interconnect. The problem is to efficiently co-schedule task execution on cores and message transmission on the interconnect so that timing constraints are satisfied. Contemporary works typically deal with zero-jitter scheduling, which results in lower resource utilization, but has lower memory requirements. This article focuses on jitter-constrained scheduling that puts constraints on the tasks jitter, increasing schedulability over zero-jitter scheduling. The contributions of this article are: 1) Integer Linear Programming and Satisfiability Modulo Theory model exploiting problem-specific information to reduce the formulations complexity to schedule small applications. 2) A heuristic approach, employing three levels of scheduling scaling to real-world use-cases with 10,000 tasks and messages. 3) An experimental evaluation of the proposed approaches on a case-study and on synthetic data sets showing the efficiency of both zero-jitter and jitter-constrained scheduling. It shows that up to 28 percent higher resource utilization can be achieved by having up to 10 times longer computation time with relaxed jitter requirements.

Cluster scheduling respecting collision avoidance is a complex problem in cluster-tree wireless sensor networks (WSNs). The difficulty of the problem also increases significantly when the traffic is organized as time-constrained data flows with opposite directions. Thus, in this paper, we seek a collision-free cluster schedule that meets all the data flow deadlines as given in time units. In this context, we have found an elegant approach that expresses the deadline of each flow as an integer number of the length of the schedule period (i.e., period crossing constraints). Consequently, the data flow timeliness requirements become easier to be tackled. Due to the scarce resources of the WSNs, the minimization of the energy consumption of the nodes is a problem of paramount importance. Therefore, the objective is to maximize the lifetime of the network by maximizing the time when the nodes stay in low-power mode. In this paper, we present a novel heuristic scheduling algorithm to obtain the desired schedule. The algorithm is based on very interesting formulations of graph theory problems. Thus, it is efficient in both computational time (instances with thousands of devices are solved in a short time) and solution quality (evaluated over smaller size instances while comparing it with optimal solutions obtained by integer linear programming).

Real-life scheduling has to face many difficulties such as dynamics of manufacturing environments with unforeseen events occurring during the execution of a schedule. Namely, in the case of a resource failure, it may be necessary to process a lot of work again, or a feasible schedule recovery may not exist at all. Moreover, the time window within which the ongoing schedule must be updated may be very short, and too timeconsuming computation of the schedule may lead to a failure of the scheduling mechanism and setback in production. Our approach in the area of predictive-reactive scheduling is to allow for substitution of tasks, which cannot be executed, with a set of alternative tasks. This paper makes use of the model of the hierarchical workflows and gives an SMT and a CSP models to recover an ongoing schedule from a resource failure with the objective to minimize the work processed in vain. The experimental analysis identified parameters for which the SMT model clearly outperforms the CSP model and vice versa.

This study focuses on the energy optimization of industrial robotic cells, which is essential for sustainable production in the long term. A holistic approach that considers a robotic cell as a whole toward minimizing energy consumption is proposed. The mathematical model, which takes into account various robot speeds, positions, power-saving modes, and alternative orders of operations, can be transformed into a mixed-integer linear programming formulation that is, however, suitable only for small instances. To optimize complex robotic cells, a hybrid heuristic accelerated by using multicore processors and the Gurobi simplex method for piecewise linear convex functions is implemented. The experimental results showed that the heuristic solved 93% of instances with a solution quality close to a proven lower bound. Moreover, compared with the existing works, which typically address problems with three to four robots, this study solved real-size problem instances with up to 12 robots and considered more optimization aspects. The proposed algorithms were also applied on an existing robotic cell in řkoda Auto. The outcomes, based on simulations and measurements, indicate that, compared with the previous state (at maximal robot speeds and without deeper power-saving modes), the energy consumption can be reduced by about 20% merely by optimizing the robot speeds and applying power-saving modes. All the software and generated datasets used in this research are publicly available.

Our work considers a scheduling problem in which manufacturing companies with large energy demand are obligated to comply with total energy consumption limits in specified time intervals, e.g. 15 minutes. Moreover, the problem is complicated by the fact that in reality the production schedules are not executed exactly as planned due to unexpected disturbances such as machine breakdowns or material unavailability. Therefore, the goal is to find a robust schedule which guarantees that the energy consumption limits are not violated if the start times of operations are arbitrary delayed within a given limit. To circumvent the problem of an exponential number of constraints in the mixed integer linear programming formulation, we propose an exact algorithm based on a decomposition approach. The decomposition approach exploits the fact that the robustness of a given schedule can be checked in a pseudo-polynomial time. We evaluated the proposed algorithm on instances with varying bound of the start times delays.

The FlexRay bus is a communication standard used in the automotive industry. It offers a deterministic message transmission in the static segment following a time-triggered schedule. Even if its bandwidth is ten times higher than the bandwidth of controller area network (CAN), its throughput limits are going to be reached in high-class car models soon. A solution that could postpone this problem is to use an efficient scheduling algorithm that exploits both channels of the FlexRay. The significant and often neglected feature that can theoretically double the bandwidth is the possibility to use two independent communication channels that can intercommunicate through the gateway. In this paper, we propose a heuristic algorithm that decomposes the scheduling problem to the electronic control unit (ECU)-to-channel assignment subproblem, which decides which channel the ECUs should be connected to and the channel scheduling subproblem that creates static segment communication schedules for both channels. The algorithm is able to create a schedule for cases where channels are configured in the independent mode, as well as in the fault-tolerant mode or in cases where just part of the signals are fault tolerant. Finally, the algorithm is evaluated on real data and synthesized data, and the relation between the portion of fault-tolerant signals and the number of allocated slots is presented.

Complex contemporary systems contain multiple applications, some which have firm real-time requirements while others do not. These applications are deployed on multi-core platforms with shared resources, such as processors, interconnect, and memories. However, resource sharing causes contention between sharing applications that must be resolved by a resource arbiter. Time-Division Multiplexing (TDM) is a commonly used arbiter, but it is challenging to configure such that the bandwidth and latency requirements of the real-time resource clients are satisfied, while minimizing their total allocation to improve the performance of non-real-time clients. This work addresses this problem by presenting an efficient TDM configuration methodology. The five main contributions are: 1) An analysis to derive a bandwidth and latency guarantee for a TDM schedule with arbitrary slot assignment, 2) A formulation of the TDM configuration problem and a proof that it is NP-hard, 3) An integer-linear programming model that optimally solves the configuration problem by exhaustively evaluating all possible TDM schedule sizes, 4) A heuristic method to choose candidate schedule sizes that substantially reduces computation time with only a slight decrease in efficiency, 5) An experimental evaluation of the methodology that examines its scalability and quantifies the trade-off between computation time and total allocation for the optimal and the heuristic algorithms. The approach is also demonstrated on a case study of a HD video and graphics processing system, where a memory controller is shared by a number of processing elements.

We study one-collision domain ZigBee cluster-tree design problems to satisfy periodic time-bounded data flows. The formation of the cluster-tree topology can be seen as a bounded-degree-and-depth tree which is an NP-complete problem. The objective is to minimize the number of clusters such that all flows can take place and there exists a cluster schedule that meets the deadlines of the flows. For the resulting tree, the cluster schedule is required to be energy efficient, which can be achieved by maximizing the length of the schedule period, and consequently, increasing the lifetime of the network. We present a Cluster-Tree Formation and Energy-Efficient clusters scheduling algorithm, CFEFS, based on the Hungarian algorithm, the Maximum Matching algorithm and the Branch and Bound algorithm to tackle this design problem that integrates the cluster formation and the cluster scheduling in one problem.

The FlexRay bus is a modern standard used in the automotive industry. It offers deterministic message transmission in the static segment following a time-triggered schedule. The scheduling problem for case of use two independent communication channels that can intercommunicate through the gateway node is investigated in the paper. Furthermore, a heuristic algorithm is proposed and evaluated.

Cluster scheduling is a crucial issue in cluster-tree Wireless Sensor Networks (WSNs). The paper presents a methodology that provides a Time Division Cluster Scheduling (TDCS) mechanism based on the shortest path problem. The objective is to meet all the flows' deadlines defined by the maximum number of crossed periods for each flow to reach its destination assuming one collision domain. Formulating the problem as the shortest path problem gives us a light exact algorithm suitable to the scarce properties of WSNs especially related to memory, power consumption and processors. Our polynomial algorithm leads to the minimization of the energy consumption and, consequently, the lifetime of the network is maximized by setting the TDCS period as long as possible. Since each cluster is active only once during the period, the given flow may span over several periods when there are flows with an opposite direction. The scheduling tool enables the system designers to efficiently configure all the required parameters of the IEEE 802.15.4/ZigBee beacon-enabled cluster-tree WSNs in the network configuration time.

This work proposes an in-network distributed algorithm for the energy optimal routing in a wireless sensor network. The routing problem is described as a minimum-cost multi-commodity network flow problem by Linear programming. Based on the convex programming theory we use the dual decomposition theorem to derive the distributed algorithm on a mathematical basic. The algorithm computes the exact energy optimal routing in the network without any central node or the knowledge about the whole network structure, using only peer-to-peer communication between neighboring nodes. In contrast to other works in this area, the presented approach is not limited to strictly convex objective functions and it handles linear objective functions.

This paper presents two ways of how to tackle a problem of vehicle navigation and guidance, and focuses on evaluation of the performance and energy consumption of both methods. A simple energy-aware computing scheme, intended for control, navigation and guidance of autonomous unmanned aircraft, is proposed to try to make the most of both methods - providing good tracking accuracy whenever needed, minimizing power consumption otherwise. This scheme is based on the idea of using simple, non-demanding algorithms whenever possible and switching to sophisticated, more accurate control methods only when required by the mission profile. Simple algorithms may be executed in modules with less computing power, allowing high-performance on-board computers (needed for real-time execution of complex tasks) to be suspended, thus conserving energy. This scheme might bring noticeable benefits especially for vehicles in the micro-UAV category, where the amount of usable energy is extremely limited and the portion of energy consumed by on-board computers might be significant (up to 20%, according our measurements).

This paper deals with a scheduling problem with alternative process plans that was motivated by a production of wire harnesses where certain parts can be processed manually or automatically by different types of machines. Only a subset of all the given activities will form the solution, so the decision whether the activity will appear in the schedule has to be made during the scheduling process. The problem considered is an extension of the resource constrained project scheduling problem with unary resources, positive and negative time-lags and sequence dependent setup times. We have proposed the problem representation by a special graph allowing to define alternative process plans. For this representation of the problem, an integer linear programming model is formulated. Finally a heuristic algorithm based on priority schedule construction with an unscheduling step is proposed and used to solve the case study of the wire harnesses production.

The simulation analysis is important approach to developing and evaluating the systems in terms of development time and cost. This paper demonstrates the application of Time Division Cluster Scheduling (TDCS) tool for the configuration of IEEE 802.15.4/ZigBee beacon-enabled cluster-tree WSNs using the simulation analysis, as an illustrative example that confirms the practical applicability of the tool. The simulation study analyses how the number of retransmissions impacts the reliability of data transmission, the energy consumption of the nodes and the end-to-end communication delay, based on the simulation model that was implemented in the Opnet Modeler. The configuration parameters of the network are obtained directly from the TDCS tool. The simulation results show that the number of retransmissions impacts the reliability, the energy consumption and the end-to-end delay, in a way that improving the one may degrade the others.

This paper presents an algorithm that allows one to create a static schedule of the Profinet IO IRT (Isochronous Real Time) communication, which is an industrial Ethernet protocol standardized in IEC 61158. This algorithm offers an alternative to the available commercial tool, providing comparable results with respect to the resulting schedule makespan. Furthermore, the problem is extended by useful temporal constraints (i.e., release dates, deadlines and end-to-end deadlines of the messages) providing a greater flexibility with respect to the individual messages. Due to this flexibility, it is possible to place the selected messages in various parts of the communication cycle (in order to increase the computational time available for the main-controller application, or to retransmit the synchronization message without holdup in the switch, or to add new messages into the original schedule). The solution is based on a formulation of the Profinet IO IRT scheduling problem in terms of the Resource Constrained Project Scheduling with Temporal Constraints.

Cluster scheduling and collision avoidance are crucial issues in large-scale cluster-tree Wireless Sensor Networks (WSNs). This paper presents a methodology that provides a Time-Division Cluster Scheduling (TDCS) mechanism based on the cyclic extension of Resource Constrained Project Scheduling with Temporal Constraints (RCPS/TC) problem for a cluster-tree WSN, assuming bounded communication errors. The objective is to meet all end-to-end deadlines of a predefined set of time-bounded data flows while minimizing the energy consumption of the nodes by setting the TDCS period as long as possible. Since each cluster is active only once during the period, the end-to-end delay of a given flow may span over several periods when there are the flows with opposite direction. The scheduling tool enables system designers to efficiently configure all required parameters of the IEEE 802.15.4/ZigBee beacon-enabled cluster-tree WSNs in the network design time. The performance evaluation of the scheduling tool shows that the problems with dozens of nodes can be solved while using optimal solvers.

This paper presents an algorithm that allows one to create a static schedule of the Profinet IO IRT communication, which is an industrial Ethernet protocol standardised in IEC$\;$61158. This algorithm offers an alternative to the available commercial tool, providing comparable results regarding the resulting time schedule length. Furthermore, we extend the problem by useful time constraints providing a greater flexibility with respect to the individual messages. Due to this flexibility, it is possible to place the selected messages in various parts of the communication cycle, to define end-to-end delays, or to increase the computational time available for the main-controller application, for example. The solution is based on a formulation of the Profinet IO IRT scheduling problem in terms of the Resource Constrained Project Scheduling with Temporal Constraints (PS|temp|Cmax).

We have proposed an algorithm for optimal real-time routing in multi-hop communication networks for multi- source/multi-sink connection. The algorithm deals with various capacity constraints in terms of communication limits and real-time constraints expressed as deadline for each particular flow of data. The objective is to find the optimal routing in terms of energy consumption. The algorithm is based on a data flow model leading to Linear Programming formulation and therefore it ensures polynomial-time complexity. An extension handling simultaneous real-time and non real-time routing is added. An example of data collection from 100 nodes is presented and performance experiments illustrating time complexity in dependence on the number of nodes are given.

The motivation of our work is to make a design tool for distributed embedded systems compliant with HIS and AUTOSAR. The tool is based on Processor Expert, a component oriented development environment supporting several hundreds of microcontrollers, and Matlab simulink which is the de-facto standard in the rapid prototyping of the control applications but it does not have an adequate HW support. The objective is to provide an integrated development environment for embedded controllers having distributed nature and real-time requirements. Therefore we discuss the advantages of using an automatically generated code in the development cycle of the control embedded software. We present a developed block set and processor expert real-time target for Matlab real-time workshop embedded coder. The case study shows a development cycle for a servo control design.

The IEEE 802.15.4 protocol has the ability to support time-sensitive Wireless Sensor Network (WSN) applications due to the Guaranteed Time Slot (GTS) Medium Access Control mechanism. Recently, several analytical and simulation models of the IEEE 802.15.4 protocol have been proposed. Nevertheless, currently available simulation models for this protocol are both inaccurate and incomplete, and in particular they do not support the GTS mechanism. In this paper, we propose an accurate OPNET simulation model, with focus on the implementation of the GTS mechanism. The motivation that has driven this work is the validation of the Network Calculus based analytical model of the GTS mechanism that has been previously proposed and to compare the performance evaluation of the protocol as given by the two alternative approaches. Therefore, in this paper we contribute an accurate OPNET model for the IEEE 802.15.4 protocol. Additionally, and probably more importantly, based on the simulation model we propose a novel methodology to tune the protocol parameters such that a better performance of the protocol can be guaranteed, both concerning maximizing the throughput of the allocated GTS as well as concerning minimizing frame delay. Keywords - IEEE 802.15.4; GTS; OPNET Modeler; simulation model; analytical model

This paper discuses advantages of using automatically generated code in the development cycle of control embedded software. Since the Matlab development tool chain has become standard in the control applications development, we focus on its facilities for code generation. As the Matlab main weakness is identified a poor support for handling hardware devices of a target microcontroller. Since there exists processor expert, an excellent tool for microcontrollers' hardware resources management and design at high level, we bring radical improvement of Matlab facilities for handling controller hardware by integrating processor expert to the Matlab Simulink environment. We present developed block set and processor expert real-time target for Matlab real-time workshop embedded coder.

A low-cost, integrated avionics system for ultra-light airplanes is being presented in this paper. It represents affordable, yet modern and reliable alternative to the obsolete avionics currently widely used in the ultralight aviation. Whole avionics is designed as distributed, hierarchical data acquisition system, utilizing Linux operating system and controller area network industrial bus. Important data are provided to the pilot via multifunctional screen, while safety-critical warnings are also reported acoustically via speech system connected to the pilot's headphones. A lot of precautionary measures had been taken to make the system as fault-tolerant and safe as possible. Rugged, robust and reliable apparatus should be the result.

This paper is motivated by existing architectures of field programmable gate arrays (FPGAs). To facilitate the design process we present an optimal scheduling algorithm using a very universal framework, where tasks are constrained by precedence delays and relative deadlines. The precedence relations are given by an oriented graph, where tasks are represented by nodes. Edges in the graph are related either to the minimum time or to the maximum time elapsed between the start times of the tasks. This framework is used to model the runtime dynamic reconfiguration, synchronization with an on-chip processor and simultaneous availability of arithmetic units and SRAM memory. The NP-hard problem of finding an optimal schedule satisfying the timing and resource constraints while minimizing the makespan Cmax, is solved using two approaches. The first one is based on integer linear programming and the second one is implemented as a branch and bound algorithm. Experimental results show the efficiency comparison of the ILP and branch and bound solutions

This paper is motivated by existing architectures of field programmable gate arrays (FPGAs). To facilitate the design process we present an optimal scheduling algorithm using a very universal framework, where tasks are constrained by precedence delays and relative deadlines. The precedence relations are given by an oriented graph, where tasks are represented by nodes. Edges in the graph are related either to the minimum time or to the maximum time elapsed between the start times of the tasks. This framework is used to model the runtime dynamic reconfiguration, synchronization with an on-chip processor and simultaneous availability of arithmetic units and SRAM memory. The NP-hard problem of finding an optimal schedule satisfying the timing and resource constraints while minimizing the makespan Cmax, is solved using two approaches. The first one is based on Integer Linear Programming and the second one is implemented as a Branch and Bound algorithm. Experimental results show the efficiency comparison of the ILP and Branch and Bound solutions.

Presented high-level synthesis describes scheduling for wide class of DSP algorithms. Several FPGA vendors or even ASIC designs are targeted via Handel-C compiled by Celoxica DK3.1 compiler. Using the authors' approach, the designer can easily change type of used pipelined arithmetic modules and then check new performance. The optimal time schedule is found by cyclic scheduling using integer linear programming while minimizing the schedule period in the terms of clock cycles. Experimental results in HW implementation, performed on logarithmic arithmetic and floating-point arithmetic, confirm significant influence of the period on the resulting performance of DSP algorithms.

This paper presents a scheduling technique for a library of arithmetic logarithmic modules for FPGA illustrated on a RLS filter for active noise cancellation. The problem under assumption is to find an optimal periodic cyclic schedule satisfying the timing constraints. The approach is based on a transformation to monoprocessor cyclic scheduling with precedence delays. We prove that this problem is NP-hard and we suggest a solution based on integer linear programming that allows to minimize completion time. Finally experimental results of optimized RLS filter are shown.

This article addresses the problem of the computation of instantaneous firing speed in Invariant Behavior state (IB-state) of Constant speed Continuous Petri Net (CCPN) with presence of actual conflicts. The adopted approach is based on polyhedral computations applied to specify an area of possible instantaneous firing speed. If the actual conflicts are resolved by global priorities, the instantaneous firing speed is found in a set of the polytop vertices or alternatively it is found by one formulation of the linear programming problem per each priority level. The approach shown in this article assumes the speed maximisation being prior to priority resolution.

This article focuses on algorithm representation by means of Petri nets and data dependence graphs. In order to detect antidependencies and output dependencies in Petri net representation we have introduced a term IP-dependencies (instruction-pointer-related data interactions). This original approach allows us to put knowledge of automatic parallelization via data dependence graphs and Petri nets onto the same theoretical platform and to join the two scientific branches.