This presentation shows three problems from the area of parallel and distributed algorithm design. For each of them we explain the motivation, we formulate the optimization problem, we show the problem to be NP- complete, we attempt to reduce the problem size (by LP or graph theory algorithms), we solve the problem (ILP formulation and B&B algorithms) and we show experimental results.

a) Scheduling of Tasks with Precedence Delays and Relative Deadlines This work is motivated by existing architectures of field Programmable gate arrays (FPGAs) supporting runtime dynamic reconfiguration. To facilitate the design process we present an optimal scheduling algorithm using very universal model, 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 start times of the tasks. The NP-hard problem of finding an optimal schedule satisfying the timing and resource constraints while minimizing makespan $C_{max}$, 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.

b) Scheduling of Iterative Algorithms with nested loops This work presents a scheduling technique used to optimize computation speed of iterative algorithms running on architectures that may include distinct dedicated processors. The problem under consideration is to find an optimal periodic 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 one to minimize completion time. Further we extend the method to iterative algorithms with nested loops and we consider the memory access as an additional resource constraint. Since the solutions of ILP formulated problems are known to be computationally intensive, important part of the article is devoted to the reduction of the problem size. The method is demonstrated on an implementation of the Finite Interval Constant Modulus Algorithm, proposed for 4G communication systems and on RLS filter, used in demonstrate the active noise cancellation.

c) This work deals with an overlay multicast network, where the multicast data are routed and replicated on the application layer along a multicast tree. We present the techniques of the network reduction and the multicast tree construction. The multicast tree in the form of shortest path tree can be build up upon the linear programming formulation. To control the load of each host, the additional constraints on the maximal number of directly outgoing connections and leads to the degree bounded shortest path tree problem, which is NP-complete. To solve the problem, we formulate integer linear program and we show experimental results on benchmarks.