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.

International audience

This paper addresses the problem of an aerial moving target search with a radar on an airborne platform.An observation of the radar is modeled as a cone covering a set of regions of the search area.We assume overlapping cones of observation, and we want to find the discrete allocation plan of search effort to the cones in order to optimize target detection.For the stationary target search with overlapping cones, we present a dynamic programming algorithm that computes the optimal allocation.An approximate greedy heuristic, which is more appropriate in a real time context, is also presented and assessed.The moving target search problem is solved with the Forward And Backward (FAB) algorithm coupled with the different stationary search algorithms.In this paper, we use a radar detection model that has been shown to be more realistic than the ones usually considered.Also, several models of movement of the target are considered with different Markovian transition matrices.We compare the performance of the mentioned algorithms on several scenarios.

This paper addresses the problem of a moving target search with a discrete allocation of search effort to disjoint cones of observation. A cone covers several regions with different visibilities. This is an important step towards the optimal search with radars on airborne platforms which has not been previously studied. We adapt Forward And Backward (FAB) algorithms to this problem and apply them to compute search plans. We measure the quality of our solution with a continuous relaxation of the problem. In a set of numerical experiments we exhibit that our algorithms have good performance in terms of plan quality and computation time. Finally, we compare the plans optimizing different objective functions.

In this paper we consider the parameterized complexity of two versions of a parallel machine scheduling problem with precedence delays, unit processing times and time windows. In the first version - with exact delays - we assume that the delay between two jobs must be exactly respected, whereas in the second version - with minimum delays - the delay between two jobs is a lower bound on the time between them. Two parameters are considered for this analysis: the pathwidth of the interval graph induced by the time windows and the maximum precedence delay value. We prove that our problems are para-NP-complete with respect to any of the two parameters and fixed-parameter tractable parameterized by the pair of parameters.

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 paper deals with the minimization of the asymptotic latency of horizontal microprograms performing vectorial loops. On a quite general architecture model, we show that all the constraints can be formalized to give a cyclic scheduling problem, modelled with a Timed Petri net. To analyse the net behaviour, a bivalued resolution graph is build. A critical cycle of this graph leads to optimal microprograms whose structure is independent on the number of iterations. This approach is then extended to uniform recurrences.