Scheduling tasks with communication delays on parallel processors

LetP={v ₁,...,v _n } be a set ofn jobs to be executed on a set ofm identical machines. In many instances of scheduling problems, if a jobv _i has to be executed before the jobv _j and both jobs are to be executed on different machines, some sort of information exchange has to take place between the machines executing them. The time it takes for this exchange of information is called a communication delay.In this paper we give anO(n) algorithm to find an optimal scheduling with communication delays when the number of machines is not limited and the precedence constraints on the jobs form a tree.     

A biased random-key genetic algorithm with forward-backward improvement for the resource constrained project scheduling problem

This paper presents a biased random-key genetic algorithm for the resource constrained project scheduling problem. The chromosome representation of the problem is based on random keys. Active schedules are constructed using a priority-rule heuristic in which the priorities of the activities are defined by the genetic algorithm. A forward-backward improvement procedure is applied to all solutions. The chromosomes supplied by the genetic algorithm are adjusted to reflect the solutions obtained by the improvement procedure. The heuristic is tested on a set of standard problems taken from the literature and compared with other approaches. The computational results validate the effectiveness of the proposed algorithm.     

On the sum of the Laplacian eigenvalues of a tree

Given an n-vertex graph G=(V,E), the Laplacian spectrum of G is the set of eigenvalues of the Laplacian matrix L=D-A, where D and A denote the diagonal matrix of vertex-degrees and the adjacency matrix of G, respectively. In this paper, we study the Laplacian spectrum of trees. More precisely, we find a new upper bound on the sum of the k largest Laplacian eigenvalues of every n-vertex tree, where k∈{1,…,n}. This result is used to establish that the n-vertex star has the highest Laplacian energy over all n-vertex trees, which answers affirmatively to a question raised by Radenkovi? and Gutman [10].     

Electrical turbulence as a result of the critical curvature for propagation in cardiac tissue

In cardiac tissue, the propagation of electrical excitation waves is dependent on the active properties of the cell membrane (ionic channels) and the passive electrical properties of cardiac tissue (passive membrane properties, distribution of gap junctions, and cell shapes). Initiation of cardiac arrhythmias is usually associated with heterogeneities in the active and/or passive properties of cardiac tissue. However, as a result of the effect of wave front geometry (curvature) on propagation of cardiac waves, inexcitable anatomical obstacles, like veins and arteries, may cause the formation of self-sustained vortices and uncontrolled high-frequency excitation in normal homogeneous myocardium. (c) 1998 American Institute of Physics.     

Sobolev estimates for (pseudo)‐differential operators and applications

In this work we show that if is a linear differential operator of order ν with smooth complex coefficients in from a complex vector space E to a complex vector space F, the Sobolev a priori estimate holds locally at any point if and only if is elliptic and the constant coefficient homogeneous operator is canceling in the sense of Van Schaftingen for every which means that Here is the homogeneous part of order ν of and is the principal symbol of . This result implies and unifies the proofs of several estimates for complexes and pseudo‐complexes of operators of order one or higher proved recently by other methods as well as it extends —in the local setup— the characterization of Van Schaftingen to operators with variable coefficients.     

Shohat-Favard and Chebyshev’s methods in d-orthogonality

This paper is concerned with the Shohat-Favard, Chebyshev and Modified Chebyshev methods for d-orthogonal polynomial sequences d∈ℕ. Shohat-Favard’s method is presented from the concept of dual sequence of a sequence of polynomials. We deduce the recurrence relations for the Chebyshev and the Modified Chebyshev methods for every d∈ℕ. The three methods are implemented in the Mathematica programming language. We show several formal and numerical tests realized with the software developed. This revised version was published online in June 2006 with corrections to the Cover Date.     

Frames with Transitive Structures

A classical result in the theory of uniform spaces is that any topological space with a base of clopen sets admits a uniformity with a transitive base and the uniform topology of such a space has a base of clopen sets. This paper presents a pointfree generalization of this, both to uniform and quasi-uniform frames, together with various properties concerning total boundedness, compactifications and completions.     

An improved class of generalized Runge–Kutta methods for stiff problems. Part I: The scalar case

A new family of p-stage methods for the numerical integration of some scalar equations and systems of ODEs is proposed. These methods can be seen as a generalization of the explicit p-stage Runge–Kutta ones, while providing better order and stability results. We will show in this first part that, at the cost of losing linearity in the formulas, it is possible to obtain explicit A-stable and L-stable methods for the numerical integration of scalar autonomous ODEs. Scalar autonomous ODEs are of very little interest in current applications. However, be begin studying this kind of problems because most of the work can be easily extended to a more general situation. In fact, we will show in a second part (entitled ‘The separated system case'), that it is possible to generalize our methods so that they can be applied to some non-autonomous scalar ODEs and systems. We will obtain linearly implicit L-stable methods which do not require Jacobian evaluations. In both parts, some numerical examples are discussed in order to show the good performance of the new schemes.     

Optimal Paths for Symmetric Actions in the Unitary Group

Given a positive and unitarily invariant Lagrangian ${\mathcal{L}}$ defined in the algebra of matrices, and a fixed time interval ${[0,t_0]\subset\mathbb R}$ , we study the action defined in the Lie group of ${n\times n}$ unitary matrices ${\mathcal{U}(n)}$ by $$\mathcal{S}(\alpha)=\int_0^{t_0} \mathcal{L}(\dot\alpha(t))\,dt, $$ where ${\alpha:[0,t_0]\to\mathcal{U}(n)}$ is a rectifiable curve. We prove that the one-parameter subgroups of ${\mathcal{U}(n)}$ are the optimal paths, provided the spectrum of the exponent is bounded by π. Moreover, if ${\mathcal{L}}$ is strictly convex, we prove that one-parameter subgroups are the unique optimal curves joining given endpoints. Finally, we also study the connection of these results with unitarily invariant metrics in ${\mathcal{U}(n)}$ as well as angular metrics in the Grassmann manifold.