A design method for embedded software systems

A method for design of embedded real-time systems is described. We discuss how the method separates concerns and at what points theory is applied. We also report on our experience from teaching the method to engineers from several Danish companies and their experience in using the method in real development projects.Dedicated to Peter Naur on the occasion of his 60th birthdayThis work has been partially supported by the National Agency of Technology.     

A loss minimization problem

The optimal stopping problem is considered in the presence of random losses with decision making concerning non-recurrent involvement of an external financial-protection mechanism. The presence of an utility function determining the attitude of the decision-making person to a risk is taken into account. It is shown that, using the Bellman equation, optimal threshold functions can be constructed numerically and, for certain types of the utility function, such functions can even be constructed in an analytical form.     

A multi-period network design problem for cellular telecommunication systems

Mathematical Programming models for multi-period network design problems, which arise in cellular telecommunication systems are presented. The underlying network topologies range from a simple star to complex multi-layer Steiner-like networks. Linear programming, Lagrangian relaxation, and branch-and-cut heuristics are proposed and a polynomial-bounded heuristic based on an interior point linear programming implementation is described. Extensive computational results are presented on a number of randomly generated problem sets and the performance of the heuristic(s) are compared with an optimal branch-and-bound algorithm.     

A solvable case of the variance minimization problem

An algorithm is derived, which solves the completion time variance (CTV) problem with equal processing times in O(n log n) time. This result indicates that the special case formulated by Merten and Muller [1] is well solvable.     

Scatter search for the cutwidth minimization problem

The cutwidth minimization problem consists of finding a linear layout of a graph so that the maximum linear cut of edges is minimized. This NP-hard problem has applications in network scheduling, automatic graph drawing and information retrieval. We propose a heuristic method based on the Scatter Search (SS) methodology for finding approximate solutions to this optimization problem. This metaheuristic explores solution space by evolving a set of reference points. Our SS method is based on a GRASP constructive algorithm, a local search strategy based on insertion moves and voting-based combination methods. We also introduce a new measure to control the diversity in the search process. Empirical results with 252 previously reported instances indicate that the proposed procedure compares favorably to previous metaheuristics for this problem, such as Simulated Annealing and Evolutionary Path Relinking.     

A convergence analysis result for constrained convex minimization problem

Abstract

Our purpose in this paper is to obtain strong convergence result for approximation of solution to constrained convex minimization problem using a new iterative scheme in a real Hilbert space. Furthermore, we give numerical analysis of our iterative scheme.     

A variance minimization problem for a Markov decision process

In the steady state of a discrete time Markov decision process, we consider the problem to find an optimal randomized policy that minimizes the variance of the reward in a transition among the policies which give the mean not less than a specified value. The problem is solved by introducing a parametric Markov decision process with average cost criterion. It is shown that there exists an optimal policy which is a mixture of at most two pure policies. As an application, the toymaker's problem is discussed.     

A reduction approach for solving the rectangle packing area minimization problem

In the rectangle packing area minimization problem (RPAMP) we are given a set of rectangles with known dimensions. We have to determine an arrangement of all rectangles, without overlapping, inside an enveloping rectangle of minimum area. The paper presents a generic approach for solving the RPAMP that is based on two algorithms, one for the 2D Knapsack Problem (KP), and the other for the 2D Strip Packing Problem (SPP). In this way, solving an instance of the RPAMP is reduced to solving multiple SPP and KP instances. A fast constructive heuristic is used as SPP algorithm while the KP algorithm is instantiated by a tree search method and a genetic algorithm alternatively. All these SPP and KP methods have been published previously. Finally, the best variants of the resulting RPAMP heuristics are combined within one procedure. The guillotine cutting condition is always observed as an additional constraint. The approach was tested on 15 well-known RPAMP instances (above all MCNC and GSRC instances) and new best solutions were obtained for 10 instances. The computational effort remains acceptable. Moreover, 24 new benchmark instances are introduced and promising results are reported.     

Iterative approaches for a dynamic memory allocation problem in embedded systems

Memory allocation has a significant impact on energy consumption in embedded systems. In this paper, we are interested in dynamic memory allocation for embedded systems with a special emphasis on time performance. We propose two mid-term iterative approaches which are compared with existing long-term and short-term approaches, and with an ILP formulation as well. These approaches rely on solving a static version of the allocation problem and they take advantage of previous works for addressing the static problem. A statistic analysis is carried out for showing that the mid-term approach is the best one in terms of solution quality.     

A minimization problem in residual current modelling

An interpolation of residual currents is modelled by a variational principle, fitting the data measured at several points in a region and at all points of the boundary. The model can be interpreted by means of the least-squares estimation with a given covariance function for vorticities.     

Profile minimization problem for matrices and graphs

This project is supported by the National Natural Science Foundation of China.     

Hybrid spectral gradient method for the unconstrained minimization problem

We present a hybrid algorithm that combines a genetic algorithm with the Barzilai–Borwein gradient method. Under specific assumptions the new method guarantees the convergence to a stationary point of a continuously differentiable function, from any arbitrary initial point. Our preliminary numerical results indicate that the new methodology finds efficiently and frequently the global minimum, in comparison with the globalized Barzilai–Borwein method and the genetic algorithm of the Toolbox of Genetic Algorithms of MatLab.      

A simple heuristic for buffer design in finite-capacity queues

A practically important problem is the design of finite buffers in order to achieve a prespecified loss probability. For the class of multi-server queues with batch Poisson input this paper proposes a simple approximation using only the first two moments of the service time. Numerical investigations indicate an excellent performance of the approximation.     

A constrained minimization problem with integrals on the entire space

In this paper we consider the question of minimizing functionals defined by improper integrals. Our approach is alternative to the method of concentration-compactness and it does not require the verification of strict subaddivity.Dedicated to the memory of Antonio Gilioli (1945–1989)     

A powerful route minimization heuristic for the vehicle routing problem with time windows

We suggest an efficient route minimization heuristic for the vehicle routing problem with time windows. The heuristic is based on the ejection pool, powerful insertion and guided local search strategies. Experimental results on the Gehring and Homberger’s benchmarks demonstrate that our algorithm outperforms previous approaches and found 18 new best-known solutions.     

A dynamical systems approach to constrained minimization

We present an ordinary differential equations approach to solve general smooth minimization problems including a convergence analysis. Generically often the procedure ends up at a point which fulfills sufficient conditions for a local minimum. This procedure will then be rewritten in the concept of differential algebraic equations which opens the route to an efficient implementation. Furthermore, we link this approach with the classical SQP-approach and apply both techniques onto two examples relevant in applications.