This work deals with resource leveling problems. A set of jobs is given as well as a resource level representing a capacity that may be exceeded at some cost. Jobs have integer processing times, must be scheduled non-preemptively and consume one unit of resource while processed. More precisely, the objective to be maximized is the resource use below the resource level, i.e., the complementary of the total overload cost. Two main families of problems are investigated: either with or without precedence constraints. The case with no precedence constraints is shown to admit an EPTAS; a quasi-linear time approximation algorithm with constant ratio 7 8 is also provided. The case with precedence constraints is shown to be significantly harder to solve as it does not admit a PTAS under some classical complexity assumption. Approximation algorithms with constant ratios are provided for special cases with in-tree precedence graph or with fixed resource level.

We study here the problem of scheduling unit-time jobs with release and due dates on identical machines while meeting a non-idling constraint and minimizing the number of active machines. Though this problem is theoretically solvable in polynomial time, designing an efficient algorithm remains an issue. We establish here several theoretical results that allow us to break symmetries and significantly reduce the search space, before designing and testing a very efficient$\boldsymbol{A}^{\ast }$like algorithm involving constraint propagation, which outperforms standard approaches based upon ILP formulations.

An algorithm is presented for extracting and localizing a common structure in a family of strings with time complexity O(N/sup 2/L/sup 2/ log/sub 2/ L) where N is the number of strings and L their maximum length. The method could be extended to two-dimensional image analysis. This structure appears as alignments of words which are similar but not necessarily identical and which occur approximately at the same location in all the strings. The method works in two successive stages. First, a fast algorithm is used for drawing up a directory of exactly repeated patterns appearing in a given majority of strings. Second, the algorithm constructs recursively anchoring patterns by a divide-and-conquer strategy and converges on a maximum number of alignments. This algorithm has been applied to find common a priori unknown features in families of biological macromolecules, with quite good results. One of these families included 23 strings of about 100 characters each. Each characteristic structure has been achieved within less than one minute on a MULTIX-DPS8 system. >