In this paper, we face a generalization ofthe problem of finding the distribution of how longit takes to reach a “target” set T of states inMarkov chain. The graph problems of finding the number of paths thatgo from a state to a target set and of finding the n-length path connectionsare shown to belong to this generalization.This paper explores how the statespace of the Markov chain can be reduced by collapsing togetherthose states that behave in the same way for the purposes ofcalculating the distribution ofthe hitting time of T.We prove the existence and the uniqueness of aoptimal projection for this aim which extends the results given in[G. Aletti and E. Merzbach, J. Eur. Math. Soc. (JEMS)8 (2006) 49–75], together with the existence of a polynomial algorithm which reaches this optimum.Some applied examples are presented. Markov complexity is defined an tested onsome classical problems to demonstrate the deeper understanding that ismade possible by this approach.

Starting from the famous Königsberg bridge problem which Euler described in 1736, we intend to show that some results obtained 180 years later by König are very close to Euler's discoveries.

Soit F une famille de critères conçue pour asseoir un modèle de préférences global sur un ensemble A d'actions potentielles (ou alternatives). On se place ici dans une perspective d'aide à la décision et dans l'hypothèse où des dépendances (encore appelées interactions) sont susceptibles d'exister entre certains des critères de F. On commence (cf. Sect. 2.1) par préciser ce que signifie l'affirmation "il existe des dépendances entre certains des critères de F" (Déf. 1). On s'intéresse ensuite à deux formes classiques de dépendances (cf. Sect. 2.2). Dans la Section 3, on cherche à apporter des éléments de réponse à la question : comment mettre en évidence les dépendances s'il en existe et comment les rendre intelligibles pour les parties prenantes au processus de décision ? On définit trois types de situations particulièrement dignes d'intérêt car aisément intelligibles et faciles à cerner. Dans la section suivante, on examine les possibilités qu'offrent un certain nombre de modèles d'agrégation pour prendre en compte explicitement des dépendances. On met notamment en évidence (cf. Sect. 4.2) les possibilités et limites de l'intégrale de Choquet. Tout au long de l'article, des exemples sont introduits pour illustrer les propos.


Ce travail porte sur l'optimisation des lignesd'usinage pour la grande série. Une telle ligne comporte plusieurspostes de travail, chacun étant équipé avec boîtiers multibroches. Unboîtier multibroche exécute plusieurs opérations en parallèle.Lors de la conception en avant-projet, il est nécessaire d'affecter toutes les opérations à des boîtiers etdes postes de travail de sorte à minimiser le nombre de postes et deboîtiers utilisés. Pour ce nouveau problème d'équilibrage des lignesde production, nous proposons une approche de résolution pardécomposition en utilisant des méthodes exactes et heuristiques. Lesrésultats des tests numériques effectués sur des instances prochesdes problèmes réels sont présentés et analysés.

In this paper, a new schedule generation scheme forresource-constrained project scheduling problems is proposed. Given aproject scheduling problem and a priority rule, a schedule generationscheme determines a single feasible solution by inserting one by oneeach activity, according to their priority, inside a partialschedule. The paper proposes a generation scheme that differs from theclassic ones in the fact that it allows to consider the activities inany order, whether their predecessors have already been scheduled ornot. Moreover, activity insertion is performed so that delaying somealready scheduled activities is allowed. The paper shows that thisstrategy remains polynomial and often gives better results than moreclassic ones. Moreover, it is also interesting in the fact that somepriority rules, which are quite poor when used with classic schedulegeneration schemes, become very competitive with the proposed schedulegeneration scheme.

In this paper, we examine the influence of approximate first and/orsecond derivatives on the filter-trust-region algorithm designed forsolving unconstrained nonlinear optimization problems and proposed byGould, Sainvitu and Toint in [12]. Numericalexperiments carried out on small-scaled unconstrained problems fromthe CUTEr collection describe the effect of the use ofapproximate derivatives on the robustness and the efficiency of thefilter-trust-region method.