Energetic reasoning is an efficient filtering technique for the Cumulative Scheduling Problem. In this paper we propose a new definition of the energy balance of intervals, together with a new checker that is more accurate for each interval. Our approach involves solving a tripartition problem. For checking the intervals, we also propose a cubic algorithm leveraging our approach. We report computational results that confirm that it is more efficient than the classical approaches.

Object association is a crucial step in target tracking and data fusion applications. This task can be formalized as the search for a relation between two sets (e.g., a sets of tracks and a set of observations) in such a way that each object in one set is matched with at most one object in the other set. In this paper, this problem is tackled using the formalism of belief functions. Evidence about the possible association of each object pair, usually obtained by comparing the values of some attributes, is modeled by a Dempster-Shafer mass function defined in the frame of all possible relations. These mass functions are combined using Dempster's rule, and the relation with maximal plausibility is found by solving an integer linear programming problem. This problem is shown to be equivalent to a linear assignment problem, which can be solved in polynomial time using, for example, the Hungarian algorithm. This method is demonstrated using simulated and real data. The 3-D extension of this problem (with three object sets) is also formalized and is shown to be NP-Hard.

We consider the problem of determining whether a given set of rectangular items can be cut from a larger rectangle using so-called guillotine cuts only. We introduce a new class of arc-colored directed graphs called guillotine graphs and show that each guillotine graph can be associated with a specific class of pattern solutions that we call a guillotine-cutting class. The properties of guillotine graphs are examined, and some effective algorithms for dealing with guillotine graphs are proposed. As an application, we then describe a constraint programming method based on guillotine graphs, and we propose effective filtering techniques that use the graph model properties in order to reduce the search space efficiently. Computational experiments are reported on benchmarks from the literature: our algorithm outperforms previous methods when solving the most difficult instances exactly.

We study the One-Machine problem with release dates with the aim of minimizing several objective functions among those the total (weighted) tardiness and the total (weighted) completion time. These problems are NP hard in the strong sense. We present general dominance properties, propagation rules along with an intelligent backtracking technique, which are valid for all these criteria. These techniques have been integrated into branch and bound methods and have been experimentally studied. These results show the efficiency of these techniques which improve the best results found for these criteria.