We present here a pricing model which is an extension of the cooperative game concept and which includes a notion of elastic demand. We present some existence results as well as an algorithm, and we conclude by discussing a specific problem related to network pricing.

We study a deterministic problem of evaluating the worst case performance of flexible solutions in the single machine scheduling. A flexible solution is a set of schedules following a given structure determined by a partial order of jobs and a type of the schedules. In this paper, the schedules of active and non-delay type are considered. A flexible solution can be used on-line to absorb the impact of data disturbances related to, for example, job arrival, tool availability or machine breakdowns. The performance of a flexible solution includes the best case and the worst case performances. The best case performance is an ideal performance that can be achieved only if the on-line conditions allow to implement the best schedule of the set of schedules characterizing the flexible solution. In contrast, the worst case performance indicates how poorly the flexible solution may perform when following the given structure in the on-line circumstances. The best-case and the worst-case performances are usually evaluated by the minimum and maximum values of the considered objective function, respectively. We present algorithmic and computational complexity results for some maximization scheduling problems. In these problems, the jobs to be scheduled have different release dates and precedence constraints may be given on the set of jobs.

L'opérateur de moyenne pondérée est très souvent utilisé pour définir une valeur v(a) à des entités a à partir de performances xj(a), j=1,...,n. Cet opérateur fait intervenir des poids spécifiquesw j comme multiplicateurs de la performance relative à la je composante. Ceci induit des possibilités de compensation des mauvaises performances par les meilleures qui peuvent être jugées inacceptables dans certains contextes concrets. En vue d'atténuer ces possibilités de compensation, on peut faire intervenir une seconde pondération à l'aide de poids de rangq r qui affectent le rôle que joue, dans la définition de v(a), la performance xj(a) en fonction du rang r qu'elle occupe dans un rangement des meilleures valeurs aux moins bonnes.Je commencerai par décrire trois exemples issus de contextes réels dans lesquels cette double pondération est nécessaire. Ensuite, je présenterai successivement un premier opérateur que j'ai introduit en 1996 sous le nom de moyenne ordonnée doublement pondérée (MO2P) et un second, proposé en 1997 par Torra [Int. J. Intell. Syst.12 (1997) 153–166.] “weighted ordered weighted average” (WOWA). Ces deux opérateurs n'étant signifiants que si les performances xj(a) se situent sur une même échelle d'intervalle E, je terminerai en proposant un autre type d'opérateur pouvant convenir lorsque E est une échelle purement ordinale.



We describe the solution of a bound constrained convex quadratic problem with limited memory resources. The problem arises from physical simulations occurring within video games. The motivating problem is outlined, along with a simple interior point approach for its solution. Various linear algebra issues arising in the implementation are explored, including preconditioning, ordering and a number of ways of solving an equivalent augmented system. Alternative approaches are briefly surveyed, and some recommendations for solving these types of problems are given.

It is well known that each tree metric M has a unique realization as a tree, and that this realization minimizes the total length of the edges among all other realizations of M. We extend this result to the class of symmetric matrices M with zero diagonal, positive entries, and such that mij + mkl ≤ max{mik + mjl, mil + mjk} for all distinct i,j,k,l.

This paper is devoted to the exact resolution of a strongly NP-hard resource-constrained scheduling problem, the Process Move Programming problem, which arises in relation to the operability of certain high-availability real-time distributed systems. Based on the study of the polytope defined as the convex hull of the incidence vectors of the admissible process move programs, we present a branch-and-cut algorithm along with extensive computational results demonstrating its practical relevance, in terms of both exact and approximate resolution when the instance size increases.

We present an inexact interior point proximal method to solve linearly constrained convex problems. In fact, we derive a primal-dual algorithm to solve the KKT conditions of the optimization problem using a modified version of the rescaled proximal method. We also present a pure primal method. The proposed proximal method has as distinctive feature the possibility of allowing inexact inner steps even for Linear Programming. This is achieved by using an error criterion that bounds the subgradient of the regularized function, instead of using ϵ-subgradients of the original objective function. Quadratic convergence for LP is also proved using a more stringent error criterion.

This paper addresses a one-machine scheduling problem in which the efficiency of the machine is not constant, that is the duration of a task is longer in badly efficient time periods. Each task has an irregular completion cost. Under the assumption that the efficiency constraints are time-periodic, we show that the special case where the sequence is fixed can be solved in polynomial time. The general case is NP-complete so that we propose a two-phase heuristic to find good solutions. Our approach is tested on problems with earliness-tardiness costs.

The minimum cost multiple-source unsplittable flow problem isstudied in this paper. A simple necessary condition to get asolution is proposed. It deals with capacities and demands and canbe seen as a generalization of the well-known semi-metriccondition for continuous multicommdity flows. A cutting planealgorithm is derived using a superadditive approach. Theinequalities considered here are valid for single knapsackconstraints. They are based on nondecreasing superadditivefunctions and can be used to strengthen the relaxation of anyinteger program with knapsack constraints. Some numericalexperiments confirm the efficiency of the inequalities introducedin the paper.

This paper investigates an inventory control problem where a firm orders and sells an inventory item through discount strategy in a price sensitive market. From the economic points of view, customers may expect a further price reduction when a firm uses pricing promotion to stimulate demand, the demand curve may vertically shift down when a firm reduces the selling price. Taking these phenomena into account, this paper developed a continuous inventory model for finding the ordering quantity, the number of pricing changing and times of price changes simultaneously so as to maximize the total profit. A solution procedure is developed for finding the optimal decision rules.

This paper presents a feasible primal algorithm for linear semidefinite programming. The algorithm starts with a strictly feasible solution, but in case where no such a solution is known, an application of the algorithm to an associate problem allows to obtain one. Finally, we present some numerical experiments which show that the algorithm works properly.

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.

Given a graph G = (V,E) and a “cost function” $f: 2^V\rightarrow\mathbb{R}$ (provided by an oracle), the problem [PCliqW] consists in finding a partition into cliques of V(G) of minimum cost. Here, the cost of a partition is the sum of the costs of the cliques in the partition.We provide a polynomial time dynamic program for the case where G is an interval graph and f belongs to a subclass of submodular set functions, which we call “value-polymatroidal”.This provides a common solution for various generalizations of the coloringproblem in co-interval graphs such as max-coloring,“Greene-Kleitman's dual”, probabilist coloring and chromatic entropy. In the last two cases, this is the first polytime algorithm for co-interval graphs. In contrast, NP-hardness of related problems is discussed. We also describe an ILP formulation for [PCliqW] which gives a common polyhedral framework to express min-max relations such as ${\overline{\chi}}=\alpha$ for perfect graphs and the polymatroid intersection theorem. This approach allows to provide a min-max formula for [PCliqW] if G is the line-graph of a bipartite graph and f is submodular.However, this approach fails to provide a min-max relation for [PCliqW] if G is an interval graphs and f is value-polymatroidal.

This paper deals with a special case of Project Scheduling problem: there is a project to schedule, which is made up of activities linked by precedence relations. Each activity requires specific skills to be done. Moreover, resources are staff members who master fixed skill(s). Thus, each resource requirement of an activity corresponds to the number of persons doing the corresponding skill that must be assigned to the activity during its whole processing time. We search for an exact solution that minimizes the makespan, using a Branch-and-Bound method.

In this paper we, firstly, present a recursive formula of theempirical estimator of the semi-Markov kernel. Then a non-parametricestimator of the expected cumulative operational time forsemi-Markov systems is proposed. The asymptotic properties of thisestimator, as the uniform strongly consistency and normality aregiven. As an illustration example, we give a numerical application.


Clique family inequalities a∑v∈W xv + (a - 1)∈v∈W , xv ≤ aδ form an intriguing class of valid inequalities for the stable set polytopes of all graphs. We prove firstly that their Chvátal-rank is at most a, which provides an alternative proof for the validity of clique family inequalities, involving only standard rounding arguments.Secondly, we strengthen the upper bound further and discuss consequences regarding the Chvátal-rank of subclasses of claw-free graphs.


We address a multi-item capacitated lot-sizing problem with setup times that arises in real-world production planning contexts. Demand cannot be backlogged, but can be totally or partially lost. Safety stock is an objective to reach rather than an industrial constraint to respect. The problem is NP-hard. We propose mixed integer programming heuristics based on a planning horizon decomposition strategy to find a feasible solution. The planning horizon is partitioned into several sub-horizons over which a freezing or a relaxation strategy is applied. Some experimental results showing the effectiveness of the approach on real-world instances are presented. A sensitivity analysis on the parameters of the heuristics is reported.


We develop a discrete-time approximation technique dealing with the time-cost trade-off problem in PERT networks. It is assumed that the activity durations are independent random variables with generalized Erlang distributions, in which the mean duration of each activity is a non-increasing function of the amount of resource allocated to it. It is also assumed that the amount of resource allocated to each activity is controllable. Then, we construct an optimal control problem with three conflicting objective functions. Solving this optimal control problem, optimally, is impossible. Therefore, a discrete-time approximation technique is applied to solve the original multi-objective optimal control problem, using goal attainment method. To show the advantages of the proposed technique, we also develop a Simulated Annealing (SA) algorithm to solve the problem, and compare the discrete-time approximation results against the SA and also the genetic algorithm results.