The paper addresses a multi-item, multi-plant lot-sizing problem with transfer costs andcapacity constraints. The problem is reformulated according to a multi-commodity flowformalism, and decomposed, through Lagrangean relaxation, into a master facility locationproblem and a slave minimal cost multi-commodity flow problem. The decomposition frameworkgives rise in a natural way to designing a Lagrangean based heuristic. Numericalexperiments showing the efficiency of the proposed approach are reported.

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.

We study the problem of scheduling jobs on a serial batching machineto minimize total tardiness. Jobs of the same batch start and arecompleted simultaneously and the length of a batch equals the sum ofthe processing times of its jobs. When a new batch starts, a constantsetup time s occurs. This problem 1| s-batch| ∑Ti isknown to be NP-Hard in the ordinary sense. In this paper we show thatit is solvable in pseudopolynomial time by dynamic programming.

We consider multistage bidding models where two types of risky assets (shares) are tradedbetween two agents that have different information on the liquidation prices of tradedassets. These prices are random integer variables that are determined by the initialchance move according to a probability distribution p over thetwo-dimensional integer lattice that is known to both players. Player 1 is informed on theprices of both types of shares, but Player 2 is not. The bids may take any integer values.The model of n-stage bidding is reduced to a zero-sum repeated game withlack of information on one side. We show that, if liquidation prices of shares have finitevariances, then the sequence of values of n-step games is bounded. This makes itreasonable to consider the bidding of unlimited duration that is reduced to the infinitegame G∞(p). We give the solutions for thesegames. Optimal strategies of Player 1 generate random walks of transaction prices. Butunlike the case of one-type assets, the symmetry of these random walks is broken at thefinal stages of the game.

Optimization is an important tool widely used in formulation of the mathematical modeland design of various decision making problems related to the science and engineering.Generally, the real world problems are occurring in the form of multi-criteria andmulti-choice with certain constraints. There is no such single optimal solution existwhich could optimize all the objective functions simultaneously. In this paper,ϵ-constraint method along with Karush−Kuhn−Tucker (KKT) condition has been used tosolve multi-objective Geometric programming problems(MOGPP) for searching a compromisesolution. To find the suitable compromise solution for multi-objective Geometricprogramming problems, a brief solution procedure using ϵ-constraint method hasbeen presented. The basic concept and classical principle of multi-objective optimizationproblems with KKT condition has been discussed. The result obtained by ϵ-constraint method withhelp of KKT condition has been compared with the result so obtained by Fuzzy programmingmethod. Illustrative examples are presented to demonstrate the correctness of proposedmodel.

Dans ce papier, nous traitons le problème de minimisation dumakespan dans un flow shop hybride à deux étages avec machinesdédiées. En premier lieu, nous présentons des propriétés de base, unensemble de bornes inférieures et deux cas polynomiaux. En secondlieu, nous proposons une nouvelle heuristique qui exploite cespropriétés, et cherche à placer les jobs, en tenant compte pourchaque instance du problème, de la valeur de la borne inférieure.La dernière partie de ce travail présente les résultatsexpérimentaux d'une étude comparative avec une heuristique de lalittérature. L'analyse de ces résultats permet d'apprécier laqualité de notre proposition.

This paper addresses a combinatorial optimization problem (COP), namely a variant of the (standard) matrix chain product (MCP) problem where the matrices are square and either dense (i.e. full) or lower/upper triangular. Given a matrix chain of length n, we first present a dynamic programming algorithm (DPA) adapted from the well known standard algorithm and having the same O(n 3) complexity. We then design and analyse two optimal O(n) greedy algorithms leading in general to different optimal solutions i.e. chain parenthesizations. Afterwards, we establish a comparison between these two algorithms based on the parallel computing of the matrix chain product through intra and inter-subchains coarse grain parallelism. Finally, an experimental study illustrates the theoretical parallel performances of the designed algorithms.

We present briefly some results we obtained with known methods to solve minimum cost tension problems, comparing their performance on non-specific graphs and on series-parallel graphs. These graphs are shown to be of interest to approximate many tension problems, like synchronization in hypermedia documents. We propose a new aggregation method to solve the minimum convex piecewise linear cost tension problem on series-parallel graphs in O(m3) operations.

In the performance measurement using tools such as data envelopment analysis (DEA), datawithout explicit inputs has attracted considerable attention among researchers. In suchstudies the problem of production planning in the next production season is an importantand interesting subject. Because of the uncertain nature of the future, decision makersneed to provide robust procedures in order to examine alternative courses of action andtheir implications. The purpose of this paper is to develop an approach to productionplanning problem in production processes without explicit inputs that typically appears incentralized decision making environment. Application of the proposed approach isillustrated empirically using a real case.

This paper is concerned with scheduling when the data are not fully knownbefore the execution. In that case computing a complete schedule off-linewith estimated data may lead to poor performances. Some flexibility must beadded to the scheduling process. We propose to start from a partial schedule and to postpone the complete scheduling until execution, thus introducing what we call a stabilizationscheme. This is applied to the m machine problem with communicationdelays: in our model an estimation of the delay is known at compile time; but disturbances due to network contention, link failures, ... may occur at execution time. Hence the processor assignment and a partial sequencing on each processor are determined off-line. Some theoreticalresults for tree-like precedence constraints and an experimental study show the interest of this approach compared with fully on-line scheduling.

The existence of solutions to a scalar Minty variational inequality of differential type is usually related to monotonicity property of the primitive function. On the other hand, solutions of the variational inequality are global minimizers for the primitive function.The present paper generalizes these results to vector variational inequalitiesputting the Increasing Along Rays (IAR) property into the center of the discussion. To achieve that infinite elements in the image space Y are introduced.Under quasiconvexity assumptions we show that solutions of generalized variational inequality and of the primitive optimization problem are equivalent.Finally, we discuss the possibility to generalize the scheme of this paper to get further applications in vector optimization.

Minimizing shutterings assembling time on construction sites can yield significant savings in labor costs and crane moves. It requires solving a pairing problem that optimizes the ability for the crane to move chains of shutterings as a whole when they can be later reused together to frame another wall of the site. In this paper, we show that this problem is NP-hard in the strong sense as well as both its multiflow and ordering aspects. We also introduce a linear relaxation that computes reasonably good lower bounds of the objective, and describe a Tabu Search based on pairings insertion and ejection that builds promising solutions.

In matricial analysis, the theorem of Eckart and Young provides a best approximation ofan arbitrary matrix by a matrix of rank at most r. In variationalanalysis or optimization, the Moreau envelopes are appropriate ways of approximating orregularizing the rank function. We prove here that we can go forwards and backwardsbetween the two procedures, thereby showing that they carry essentially the sameinformation.

Le système AutoGraphiX (AGX1 et AGX2) permet,parmi d'autres fonctions, la génération automatique de conjectures enthéorie des graphes et, dans une version plus récente, la preuve automatique de conjectures simples. Afind'illustrer ces fonctions et le type de résultats obtenus, nous étudions systématiquement ici des conjecturesobtenues par ce système et de la forme $\underline{b}_{n} \, \le \, g\,\oplus \,i \, \le \, \overline{b}_{n}$ où g désigne la maille (ou longueur du plus petit cycle) du graphe G=(V, E), i un autre invariant choisi parmi le nombre de stabilité, le rayon, le diamètre, le degré minimum, moyen ou maximum, $\underline{b}_{n} $ et $ \overline{b}_{n} $ des fonctions de l'ordre n = |V| de G les meilleures possibles, enfin $ \oplus $ correspond à une des opérations +,-,×,/. 48 telles conjectures sont obtenues: les plus simples sont démontréesautomatiquement et les autres à la main. De plus 12 autres conjecturesouvertes et non encore étudiées sont soumises aux lecteurs.

This paper introduces a new method to prune the domains of the variablesin constrained optimization problems where the objective function is defined by a sumy = ∑xi , and where the integer variables x i are subject to difference constraintsof the form xj - xi ≤ c. An important application area where such problems occur is deterministic scheduling with the mean flow time as optimality criteria.This new constraint is also more general than a sum constraint defined on a set of ordered variables. Classical approaches perform a local consistency filtering after each reduction ofthe bound of y. The drawback of these approaches comes from the fact that the constraints are handled independently.We introduce here a global constraint that enables to tackle simultaneously the whole constraint system, and thus, yields a more effective pruningof the domains of the x i when the bounds of y are reduced.An efficient algorithm,derived from Dijkstra's shortest path algorithm, is introduced to achieve interval consistency on this global constraint.

We consider the non-convex quadratic maximization problem subjectto the l1 unit ball constraint. The nature of the l 1 normstructure makes this problem extremely hard to analyze, and as aconsequence, the same difficulties are encountered when trying tobuild suitable approximations for this problem by some tractableconvex counterpart formulations. We explore some properties ofthis problem, derive SDP-like relaxations and raise openquestions.

We consider a system consisting of two not necessarily identicalexponential servers having a common Poisson arrival process. Uponarrival, customers inspect the first queue and join it if it isshorter than some threshold n. Otherwise, they join the secondqueue. This model was dealt with, among others, by Altman et al. [Stochastic Models 20 (2004) 149–172].We first derive an explicitexpression for the Laplace-Stieltjes transform of the distributionunderlying the arrival (renewal) process to the second queue. Second,we observe that given that the second serveris busy, the two queue lengths are independent.Third, we develop two computational schemes for thestationary distribution of the two-dimensional Markov process underlying thismodel, one with a complexity of$O(n \log\delta^{-1})$, the other with a complexity of $O(\log n\log^2\delta^{-1})$, where δ is the tolerance criterion.

To cope with its development, a French operator of mobile telephone networkmust periodically plan the purchase and the installation of new hardware,in such a way that a hierarchy of constraints (required and preferred)is satisfied.This paper presents the “constructive repair” method we used to solvethis problem within the allowed computing time (1 min). This method repairsthe planning during its construction. A sequence of repair procedures is defined: if a given repair cannot be achieved on a partial solution,a stronger repair (possibly relaxing more important constraints) is called upon.We tested our method on ten (both hand-made and real) problems. All our solutions were at least as good as thoses computed by hand by the engineer in charge with the planning.

In this paper we propose a primal-dual interior-point algorithm forconvex quadratic semidefinite optimization problem. The searchdirection of algorithm is defined in terms of a matrix function andthe iteration is generated by full-Newton step. Furthermore, wederive the iteration bound for the algorithm with small-updatemethod, namely, O( $\sqrt{n}$ log $\frac{n}{\varepsilon}$ ), which isbest-known bound so far.

We study the pricing problem between two firms when the manufacturer’s willingness to pay(wtp) for the supplier’s good is not known by the latter. We demonstrate that it is in theinterest of the manufacturer to hide this information from the supplier. The precision ofthe information available to the supplier modifies the rent distribution. The risk ofopportunistic behaviour entails a loss of efficiency in the supply chain. The model isextended to the case of a supplier submitting offers to several manufacturers. Somemanagerial insight through a numerical illustration is provided.