The aim of this paper is to present a new branch and boundmethod for solving the Multi-Processor Flow-Shop. This method is based on the relaxation of the initial problem to m-machine problems corresponding to centers. Release dates and tails are associated with operations andmachines. The branching scheme consists in fixing the inputs of a critical centerand the lower bounds are those of the m-machine problem. Several techniques for adjusting release dates and tails have also been introduced. As shown byour personal study, the overall method is very efficient.

In this paper, we present a new linear time algorithm forscheduling UECT (Unit Execution and Communication Time) trees on twoidentical processors. The chosen criterion is the makespan. The used strategy is based on clustering of tasks. We show that this algorithm builds optimal schedules. Some extensions are discussed for non UECT tasks.

Comparing q-ary relations on a set $\cal O$ of elementary objects is one of the most fundamental problems ofclassification and combinatorial data analysis. In this paper the specific comparison task that involves classificationtree structures (binary or not) is considered in this context. Two mathematical representations are proposed. One isdefined in terms of a weighted binary relation; the second uses a 4-ary relation. The most classical approaches totree comparison are discussed in the context of a set theoretic representation of these relations. Formal andcombinatorial computing aspects of a construction method for a very general family of association coeficients betweenrelations are presented. The main purpose of this article is to specify the components of this construction, based on apermutational procedure, when the structures to be compared are classification trees.

We consider the simulation of transient performance measures of high reliable fault-tolerant computer systems. The most widely used mathematical tools to model the behavior of these systems are Markov processes. Here, we deal basically with the simulation of the mean time to failure (MTTF) and the reliability, R(t), of the system at time t. Some variance reduction techniques are used to reduce the simulation time. We will combine two of these techniques: Importance Sampling and Conditioning Technique. The resulting hybrid algorithm performs significant reduction of simulation time and gives stables estimations.

The present study proposes an extended opportunity-basedage replacement policy where opportunities occur according to a Poissonprocess. When the age, x of the system satisfies x < S for aprespecified value S, a corrective replacement is conducted if theobjective system fails. In case x satisfies S ≤ x < T foranother prespecified value T, we take an opportunity to preventivelyreplace the system by a new one with probability p, and do not takethe opportunity with probability 1 - p. At the moment x reaches T,a preventive replacement is executed independently of opportunities. Thelong-term average cost of the proposed policy is formulated. Theconditions under which optimal values for S and T exist for aprespecified value of T and S, respectively, are then clarified. Numerical examples are also presented to illustrate the theoreticalunderpinnings of the proposed replacement policy formulation.

The Algorithm in this paper is designed to find theshortest path in a network given time-dependent cost functions. It hasthe following features: it is recursive; it takes place bath in abackward dynamic programming phase and in a forward evaluation phase; itdoes not need a time-grid such as in Cook and Halsey and Kostreva andWiecek's "Algorithm One”; it requires only boundedness (above andbelow) of the cost functions; it reduces to backward multi-objectivedynamic programming if there are constant costs. This algorithm has beensuccessfully applied to multi-stage decision problems where the costsare a function of the time when the decision is made. There are examplesof further applications to tactical delay in production scheduling andto production control.

Proximal Point Methods (PPM) can be traced to the pioneer works of Moreau [16], Martinet [14,15] and Rockafellar [19, 20] who used as regularization function the square of the Euclideannorm. In this work, we study PPM in the context of optimization and we derive a class of suchmethods which contains Rockafellar's result. We also present a less stringent criterion to theacceptance of an approximate solution to the subproblems that arise in the inner loops of PPM.Moreover, we introduce a new family of augmented Lagrangian methods for convex constrainedoptimization, that generalizes the PE+ class presented in [2].

A second order optimality condition for multiobjective optimization with a set constraint is developed; this condition is expressed as the impossibility of nonhomogeneous linear systems. When the constraint is given in terms of inequalities and equalities, it can be turned into a John type multipliers rule, using a nonhomogeneous Motzkin Theorem of the Alternative. Adding weak second order regularity assumptions, Karush, Kuhn-Tucker type conditions are therefore deduced.

Most location problems on networks consider discretenodal demand. However, for many problems, demands are betterrepresentedby continuous functions along the edges, in addition to nodaldemands. Several papers consider the optimal location problemof one or more facilities when demands are continuously distributedalong the network, and the objective function dealt with is themedian one. Nevertheless, in location of public services itis desirable to use an equity criterion. One of the latter is varianceofdistance distribution which has been studied only for discrete nodaldemands. In this paper the variance problem has been generalizedto the case where one allows the demand to arisediscretely on the nodes as well as continuously along the edges. Properties and behaviour of the objective function arestudied. Likewise we present an exact algorithm forsolving this problem in a network, which reduces the complexityof the exhaustive procedure.

We show in this paper that timed Petri nets, with one resource shared by all the transitions, are directly connected tothe modelling of integer linear programs (ILP). To an ILP can be automatically associated an equivalent Petri net. Theoptimal reachability delay is an optimal solution of the ILP. We show next that a net can model any ILP. I order to dothis, we give a new sufficient reachability condition for the marking equation, which also holds for general Petri netswithout timed transitions.

Let X and Y be two compact spaces endowed withrespective measures μ and ν satisfying the condition µ(X) = v(Y). Let c be a continuous function on the product space X x Y. The mass transfer problem consists in determining a measure ξ onX x Y whose marginals coincide with μ and ν, and such thatthe total cost ∫ ∫ c(x,y)dξ(x,y) be minimized. We firstshow that if the cost function c is decomposable, i.e., can berepresented as the sum of two continuous functions defined on X andY, respectively, then every feasible measure is optimal. Conversely,when X is the support of μ and Y the support of ν and whenevery feasible measure is optimal, we prove that the cost function isdecomposable.

In this paper we study bi-directional nearness in a network based on AHP (Analytic Hierarchy Process) and ANP(Analytic Network Process). Usually we use forward (one-dimensional) direction nearness based on Euclidean distance.Even if the nearest point to i is point j, the nearest point to j is not necessarily point i. Sowe propose theconcept of bi-directional nearness defined by AHP'ssynthesizing of weights “for” direction and “from” direction.This concept of distance is a relative distance based on the configuration ofthe set of points located on a plane ornetwork. In order to confirm the usefulness of our study we apply the proposed nearness to solving methods of TSP(Traveling Salesman Problem), where to find an approximate solution of TSP we improved Nearest-Neighbor Method.Some numerical experiments of TSP were carried out. To decide a nearest point we used two kind of nearness, forwarddirection nearness and bi-directional nearness. As a result, by using bi-directional nearness,we obtained goodapproximate solution of TSP. Moreover, the relation between AHP and ANP, through an example, is considered.

We describe an O.R. technique which plans the allotment of time of the collaborators of a big company. The proposed method not only considers the immediate profitability of the company, but also thetraining of the collaborators in order to guarantee the success of the company'srising generation. The proposed method uses a greedy approach and constitutes therefore a simple and fast tool for decision makers. It has beensuccessfully implemented in an important Swiss bank society.

The solution of a variety of classes of globaloptimisation problemsis required in theimplementation of a framework for sensitivity analysis in multicriteria decision analysis. These problems have linear constraints, some of which have a particularstructure, anda variety of objective functions, which may be smooth or non-smooth. Thecontext in which theyarise implies a need for a single, robust solution method.The literature contains few experimental results relevant to such aneed.We report on our experience with the implementation of threestochastic algorithms for global optimisation: the multi-level singlelinkage algorithm,the topographical algorithm and the simulated annealing algorithm.Issues relating to their implementation and use to solve practicalproblems are discussed. Computational results suggest that, for the class of problems considered, simulated annealing performs well.

We study networks with positive and negative customers (or Generalized networks of queues and signals) in a random environment. This environment may change the arrival rates, the routing probabilities, the service rates and also the effect of signals. We prove that the steady-state distribution has a product form. This property is obtained as a corollary of a much more general result on multidimensional Markov chains.

In this paper we give the expression of the multiplecorrelation coefficient in a linear model according to the coefficientsof correlation. This expression makes it possible to analyze from anumerical point of view the instability of estimates in the case ofcollinear explanatory variables in the linear model or in theautoregressive model. This numerical approach, that we show on twoexamples, thus supplements the usual approach of the quasi colinearity,founded on the statistical properties of the estimators.

In this work we propose a ranking procedure. This procedure uses an ordinal information about the criterion weights and a non-cardinal or mixed information for the potential actions evaluation. The advantage of this procedure is that it uses the linear programming software packages to compute the intervals of relative proximities from where the rankings are obtained.

In this paper we study the well definedness of the central path associated to agiven nonlinear (convex) semidefinite programming problem. Under standard assumptions,we establish that the existence of the central path is equivalent to the nonemptiness andboundedness of the optimal set. Other equivalent conditions are given, such as the existenceof a strictly dual feasible point or the existence of a single central point.The monotonicbehavior of the logarithmic barrier and the objective function along the trajectory is alsodiscussed. Finally, the existence and optimality of cluster points are established.

We propose a parallel algorithm which uses bothMonte-Carlo and quasi-Monte-Carlo methods. A detailed analysis of thisalgorithm, followed by examples, shows that the estimator's efficiencyis a linear function of the processor number. As a concrete applicationexample, we evaluate performance measures of a multi-class queueingnetwork in steady state.