The paper is designated to the analysis of queueing systems, arising in the network theory and communications theory (called multiphase queueing systems, tandem queues or series of queueing systems). Also we note that multiphase queueing systems can be useful for modelling practical multi-stage service systems in a variety of disciplines, especially on manufacturing (assembly lines), computer networking (packet switch structures), and in telecommunications (e.g. cellular mobile networks), etc. This research presents heavy traffic limit theorems for the cumulative idle time in multiphase queues. In this work, functional limit theorems are proved for the values of important probability characteristics of the queueing system (a cumulative idle time of a customer).

In recent years, the home delivery market has rapidly been growing since customers can purchase a variety of products very easily via Internet. At the same time, however, customers tend to switch from a supplier to another seeking for better service for them. For this reason, it is necessary for suppliers to enclose their customers by means of various kinds of service and strategy. An appointed delivery date of a product ordered by a customer is one of important factors of supplier's services. From the suppliers' point of view, they hope to make the period from the order date to the delivery date as short as possible to increase their customers, but at the same time they prefer to make this period as long as possible since the risk becomes higher that they cannot deliver products to their consumer by the appointed date under the short period appointed date. This study proposes a stochastic model to determine an optimal appointed delivery date for a supplier. For small values of an appointed delivery date L, the probability that a customer purchases the product becomes larger, but the probability of tardiness increases. In contrast, the purchase probability as well as the penalty of tardiness decreases with L. From this point of view, this study formulates the expected profit for a supplier, which is to be maximized as an objective function. Clarified are the conditions under which an optimal appointed delivery date exists for the case where the purchase probability is expressed by a multinomial logit model. Numerical examples are also presented.

Public inoculation centers are examples of facilities providing service to customers whose demand is elastic to travel and waiting time. That is, people will not travel too far, or stay in line for too long to obtain the service. The goal, when planning such services, is to maximize the demand they attract, by locating centers and staffing them so as to reduce customers' travel time and time spent in queue. In the case of inoculation centers, the goal is to maximize the people that travel to the centers and stay in line until inoculated. We propose a procedure for the allocation of multiple servers to centers, so that this goal is achieved. An integer programming model is formulated. Since demand is elastic, a supply-demand equilibrium equation must be explicitly included in the optimization model, which then becomes nonlinear. As there are no exact procedures to solve such problems, we propose a heuristic procedure, based on Heuristic Concentration, which finds a good solution to this problem. Numerical examples are presented.

In the paper, the problem of the genome mapping of DNA molecules, is presented. In particular, the new approach — the Simplified Partial Digest Problem (SPDP), is analyzed. This approach, although easy in laboratory implementation and robust with respect to measurement errors, when formulated in terms of a combinatorial search problem, is proved to be strongly NP-hard for the general error-free case. For a subproblem of the SPDP, a simple O(nlogn)-time algorithm is given, where n is a number of restriction sites.

The multiparametric min max 0-1-Integer Programming (0-1-IP) problem relative to the objective function is a family of min max 0-1-IP problems which are related by having identical constraint matrix and right-hand-side vector. In this paper we present an algorithm to perform a complete multiparametric analysis relative to the objective function.

We describe an interior point algorithm for convex quadratic problem with a strict complementarity constraints. We show that under some assumptions the approach requires a total of $O(\sqrt{n}L)$ number of iterations, where L is the input size of the problem. The algorithm generates a sequence of problems, each of which is approximately solved by Newton's method.

We consider the NP Hard problems of online Bin Covering and Packing while requiring that larger (or longer, in the one dimensional case) items be placed at the bottom of the bins, below smaller (or shorter) items — we call such a version, the LIB version of problems. Bin sizes can be uniform or variable. We look at computational studies for both the Best Fit and Harmonic Fit algorithms for uniform sized bin covering. The Best Fit heuristic for this version of the problem is introduced here. The approximation ratios obtained were well within the theoretical upper bounds. For variable sized bin covering, a more thorough analysis revealed definite trends in the maximum and average approximation ratios. Finally, we prove that for online LIB bin packing with uniform size bins, no heuristic can guarantee an approximation ratio better than 1.76 under the online model considered.

Nous présentons dans cet article un algorithme générique hybride permettant de combiner des méthodes complètes (programmation par contraintes) et incomplètes (recherche locale) pour la résolution de problèmes de satisfaction de contraintes. Ce schéma algorithmique basé sur la gestion de populations, utilise des techniques de propagation de contraintes intégrant également des heuristiques de recherche locale. Les structures utilisées autorisent une interaction homogène entre les différentes méthodes mises en œuvre et permettent également de bénéficier de leurs atouts respectifs. Nous proposons alors diverses stratégies de combinaisons dont nous mettons en avant l'intérêt sur quelques exemples par le biais d'une implémentation.


Nous nous intéressons dans ce travail au problème d'approximation d'une matrice donnée par une matrice bistochastique. Des instances de ce problème peuvent apparaître dans différents domaines : en recherche opérationnelle dans un problème d'agrégation de préférence, en calcul de variations et optimisation de forme entre autres. Nous en proposons dans cet article une étude directe via le théorème de projection et une résolution numérique inspirée par la méthode de projections alternées de Boyle-Dykstra.

Nous modélisons ici plusieurs problèmes de Transport et de Gestion de Flux à l'aide d'un flot entier et d'un multiflot fractionnaire couplés par une contrainte de capacité. Pour le problème ainsi obtenu, nous proposons différents schémas de résolution par relaxation et décomposition, qui induisent la recherche d'un flot auxiliaire dont la partie entière supérieure doit minimiser un certain coût, et qui requièrent la mise en œuvre d'un processus d'agrégation. Nous en déduisons diverses heuristiques que nous testons.

We consider the Airspace Sectorization Problem (ASP) in which airspace has to be partitioned into a given number of sectors, each of which being assigned to a team of air traffic controllers. The objective is to minimize the coordination workload between adjacent sectors while balancing the total workload of controllers. Many specific constraints, including both geometrical and aircraft related constraints are taken into account. The problem is solved in a constraint programming framework. Experimental results show that our approach can be used on real life problems.

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 inequalities putting 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.

This paper introduces a new method to prune the domains of the variables in constrained optimization problems where the objective function is defined by a sum y = ∑xi, and where the integer variables xi are subject to difference constraints of 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 of the 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 pruning of the domains of the xi 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.

Le système AutoGraphiX (AGX1 et AGX2) permet, parmi d'autres fonctions, la génération automatique de conjectures en théorie des graphes et, dans une version plus récente, la preuve automatique de conjectures simples. Afin d'illustrer ces fonctions et le type de résultats obtenus, nous étudions systématiquement ici des conjectures obtenues 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ées automatiquement et les autres à la main. De plus 12 autres conjectures ouvertes et non encore étudiées sont soumises aux lecteurs.

The decision repair algorithm (Jussien and Lhomme, Artificial Intelligence139 (2002) 21–45), which has been designed to solve constraint satisfaction problems (CSP), can be seen, either (i) as an extension of the classical depth first tree search algorithm with the introduction of a free choice of the variable to which to backtrack in case of inconsistency, or (ii) as a local search algorithm in the space of the partial consistent variable assignments. or (iii) as a hybridisation between local search and constraint propagation. Experiments reported in Pralet and Verfailllie (2004) show that some heuristics for the choice of the variable to which to backtrack behave well on consistent instances and that other heuristics behave well on inconsistent ones. They show also that, despite its a priori incompleteness, decision repair, equipped with some specific heuristics, can solve within a limited time almost all the consistent and inconsistent randomly generated instances over the whole constrainedness spectrum. In this paper, we discuss the heuristics that could be used by decision repair to solve consistent instances, on the one hand, and inconsistent ones, on the other hand. Moreover, we establish that some specific heuristics make decision repair complete.