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.

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.

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.

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.

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.

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.

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.

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.

This work proposes a GPU algorithm for a combinatorial problem known in literature as Resource Constrained Project Scheduling Problem. To solve this NP-hard problem, Tabu Search meta-heuristic is selected. All computations are performed on the GPU to minimize required communication bandwidth between the GPU and the CPU. In addition, new evaluation algorithm and effective Tabu List implementation are designed especially for GPUs. Achieved results show that the proposed GPU solution outperforms the equivalent CPU version in both quality of solutions and performance speedup.

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.

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.

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).

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.