In this paper a two-stage algorithm for finding non- dominated subsets of partially ordered setsis established. A connection is then made with dimension reduction in time-dependentdynamic programming via the notion of a bounding label, a function that boundsthe state-transition cost functions. In this context, the computational burden is partitionedbetween a time-independent dynamic programming step carried out on the bounding label anda direct evaluation carried out on a subset of “real" valued decisions. A computationalapplication to time-dependent fuzzy dynamic programming is presented.

We consider a firmthat sells seasonal goods. The firm seeks to reach a fixed levelof goodwill at the end of the selling period, with the minimumtotal expenditure in promotional activities. We consider thelinear optimal control problem faced by the firm which can onlycontrol the communication expenditure rate; communication isperformed by means of advertising and sales promotion. Goodwilland sales levels are considered as state variables andword-of-mouth effect and saturation aversion are taken intoaccount. The optimal control problem is addressed by means of theclassical Pontryagin Maximum Principle and the solution can beeasily found solving, in some cases numerically, a system of twonon linear equations. Moreover, a parametric analysis is performedto understand how the total expenditure in communication shouldbe divided between advertising and sales promotion.

Individual items of flow in a telecommunications or a transportation network may need to beseparated by a minimum distance or time, called a “headway”. If link dependent, such restrictions in general have the effect that the minimum time path for a “convoy” of items to travel from a given origin to a given destinationwill depend on the size of the convoy. The Quickest Path problemseeks a path to minimise this convoy travel time.A closely related bicriterion problem is the Maximum Capacity Shortest Path problem. For this latter problem,an effective implementation is devised for an algorithm to determine desired sets of efficient solutions which in turn facilitates the searchfor a “best” compromise solution. Numerical experience with the algorithm is reported.

In this paper, we focus on some specific optimization problems from graphtheory, those for which all feasible solutions have an equal sizethat depends on the instance size.Once having provided a formal definition of this class ofproblems, we try to extract some of its basic properties; most ofthese are deduced from the equivalence, under differentialapproximation, between two versions of a problem π which onlydiffer on a linear transformation of their objective functions.This is notably the case of maximization and minimization versionsof π, as well as general minimization and minimization withtriangular inequality versions of π. Then, we prove that somewell known problems do belong to this class, such as special casesof both spanning tree and vehicles routing problems. Inparticular, we study the strict rural postman problem(called SRPP) and show that both the maximization and theminimization versions can be approximately solved, in polynomialtime, within a differential ratio bounded above by 1/2.From these results, we derive new bounds for standard ratiowhen restricting edge weights to the interval [a,ta] (theSRPP[t] problem): we respectively provide a 2/(t+1)- and a(t+1)/2t-standard approximation for the minimization and themaximization versions.

We consider the unit execution time unit communication time (UET-UCT) scheduling model with hierarchical communica tions [CITE], and we study the impact of the hierarchical communications hypothesis on the hardness of approximation. We prove that there is no polynomial time approximation algorithm with performance guarantee smaller than 5/4 (unless P = NP). This result is an extension of the result of Hoogeveen et al. [CITE] who proved that there is no polynomial time ρ-approximation algorithm with p < 7/6 for the classical UET-UCT scheduling problem with homogeneous communication delays and an unrestricted number of identical machines.

Retrial queueing systems are characterized by the requirement that customersfinding the service area busy must join the retrial group and reapply forservice at random intervals. This paper deals with the M/G/1 retrial queuesubjected to breakdowns. We use its stochastic decomposition property toapproximate the model performance in the case of general retrial times.

Long running software systems are known to experience an aging phenomenon called software aging, one in which the accumulation of errors during the execution of software leads to performance degradation and eventually results in failure. To counteract thisphenomenon a proactive fault management approach, called software rejuvenation, is particularly useful. It essentially involves gracefully terminating an application or a system and restarting it in a clean internal state. In this paper, we reconsider the non-homogeneousMarkovian models for a single-server type of software system with rejuvenation in Garg et al. (1998), and revisit them from the theoretical view point. More precisely, it is assumed in these models that software failures can occur with positive probability during idle periods in transaction systems, but we exclude this unreasonable situation in our refined models.

We consider a system of three queues and two types of packets. Each packet arriving at this system finds in front of it a controller who either sends it in the first queue or rejects it according to a QoS criterion. When the packet finishes its service in the first queue, it is probabilistically routed to one of two other parallel queues. The objective is to minimize a QoS discounted cost over an infinite horizon. The cost function is composed of a waiting cost per packet in each queue and a rejection cost in the first queue. Subsequently, we generalize this problem by considering a system of (m+1) queues and n types of packets. We show that an optimal policy is monotonic.

In this work scheduling multiprocessor tasks on two parallel identical processors is considered.Multiprocessor tasks can be executed by more than one processorat the same moment of time.We analyze scheduling unit execution time and preemptable tasks to minimize schedule length and maximum lateness.Cases with ready times, due-dates and precedence constraintsare discussed.

This paper is the continuation of the paper “Autour de nouvelles notions pour l'analyse desalgorithmes d'approximation: Formalisme unifié et classesd'approximation” where a new formalism for polynomialapproximation and its basic tools allowing an “absolute”(individual) evaluation the approximability properties ofNP-hard problems have been presented and discussed. Inorder to be used for exhibiting a structure for theclass NPO (the optimization problems of NP),these tools must be enriched with an “instrument” allowingcomparisons between approximability properties of differentproblems (these comparisons must be independent on any specificapproximation result of the problems concerned). This instrumentis the approximability-preserving reductions. We show how tointegrate them in the formalism presented and propose thedefinition of a new reduction unifying, under a specific point ofview a great number of existing ones. This new reduction allowsalso to widen the use of the reductions, restricted until noweither between versions of a problem, or between problems, inorder to enhance structural relations between frameworks. Theyallow, for example, to study how standard-approximation propertiesof a problem transform into differential-approximation ones (forthe same problem, or for another one). Finally, we apply theseveral concepts introduced to the study of the structure (andhardness) of the instances of a problem. This point of view seemsparticurarly fruitful for a better apprehension of the hardness ofcertain problems and of the mechanisms for the design of efficientsolutions for them.

In this paper, open shop scheduling problems with limited machine availabilityare studied. Such a limited availability of machines may appear inmany real-life situations, e.g. as preventive maintenance activities.Three types of jobs are distinguished: non-preemptable,resumable and preemptable. An operation of a resumable job if not completedbefore a non-availability period of a machine may be suspended and continuedwithout additional cost when the machine becomes available.In the paper, results are given for the scheduling problems associated withthe three types of jobs.Forpreemptable jobs polynomial-time algorithms based on the two-phase methodare proposed.

We consider a stochastic approach in order to define an equilibrium model for a traffic-network problem. In particular, we assume a Markovian behaviour of the users in their movements throughout the zones of the traffic area. This assumption turns out to beeffective at least in the context of urban traffic, where, in general, the users tend to travel by choosing the path they find more convenient and not necessarily depending on thealready travelled part.The developed model is a homogeneous Markov chain, whosestationarydistributions (if any) characterize the equilibrium.

This paper considers two backup schemes for a database system: a database is updated at a nonhomogeneous Poisson process and an amount of updated files accumulates additively. To ensure the safety of data, full backups are performed at time NT or when the total updated files have exceeded a threshold level K, and between them, cumulative backups as one of incremental backups are made at periodic times iT(i = 1,2,...,N - 1). Using the theory of cumulative processes, the expected cost is obtained, and an optimal number N* of cumulative backup and an optimal level K* of updated files which minimize it are analytically discussed. It is shown as examples that optimal number and level are numerically computed when two costs of backup schemes are given.

The present study proposes a theoretical model to test sales velocity for new products introduced in small format retail stores. The model is designed to distinguish fast moving products within a relatively short period. Under the proposed model, the sales of a newly introduced product are monitored for a prespecified period T, e.g., one week, and if the number of items sold over T is equal to a prespecified integer k or more, the product is considered a fast moving product and is carried over to the following sales periods. A slow moving product could be quickly replaced with alternative merchandise in order to make best use of shelf space. The paper first presents definitions of fast and slow moving products, and then a proposed sales test policy based on the model is formulated, where the expected loss is to be minimized with respect to the integer k. Numerical examples based on actual data collected from a convenience store in Japan are also presented to illustrate the theoretical underpinnings of the proposed sales test model.

We consider a special packing-covering pair of problems. Thepacking problem is a natural generalization of finding a(weighted) maximum independent set in an interval graph, thecovering problem generalizes the problem of finding a (weighted)minimum clique cover in an interval graph. The problem pairinvolves weights and capacities; we consider the case of unitweights and the case of unit capacities. In each case we describea simple algorithm that outputs a solution to the packing problemand to the covering problem that are within a factor of 2 of eachother. Each of these results implies an approximative min-maxresult. For the general case of arbitrary weights and capacitieswe describe an LP-based (2 + ε)-approximation algorithm forthe covering problem. Finally, we show that, unlessP = NP, the covering problem cannot be approximated inpolynomial time within arbitrarily good precision.

In the present paper a complete procedure for solvingMultiple Objective Integer Linear Programming Problems is presented. The algorithm can be regarded as a corrected form and an alternative to the method that was proposed by Gupta and Malhotra. A numerical illustration is given to show that this latter can miss some efficient solutions. Whereas, the algorithm stated bellow determines all efficient solutions without missing any one.

Cet article est le premier d'une série de deux articles oùnous présentons les principales caractéristiques d'un nouveauformalisme pour l'approximation polynomiale (algorithmiquepolynomiale à garanties de performances pour les problèmesNP-difficiles). Ce travail est l'occasion d'unregard critique sur ce domaine et de discussions sur la pertinencedes notions usuelles. Il est aussi l'occasion de se familiariseravec l'approximation polynomiale, de comprendre ses enjeux etses méthodes. Ces deux articles s'adressent donc autant auxspécialistes qu'aux non spécialistes de ce domaine. Nous insistons toutparticulièrementsur l'intérêt, tant théorique qu'opérationnel, de mettre enévidence une structure au sein de la classe NPO desproblèmes d'optimisation de NP. Dans ce premier article, nousnous intéressons aux outils qui permettent d'évaluer,dans l'absolu, les propriétés d'approximation de problèmesdifficiles. Nous discutons notamment les notions de chaînesd'approximation, de niveau d'approximation, d'ordre de difficultéainsi que deux notions de limites (par rapport à une suited'algorithmes et par rapport aux instances). Chaque notion estlargement discutée et illustrée par de nombreux exempleschoisis essentiellement pour leur valeur pédagogique.
Mots Clés. Complexité, difficulté intrinsèque, analyse des algorithmes et des problèmes,algorithmes d'approximation. Classification Mathématique. 68Q15, 68Q17, 68Q25, 68W25.

We show that a particular dynamic priority given to jobs in a multitasks operating system of computers is a deteriorating jobs or a delaying jobs scheduling. Under some assumptions we also show that it is an index rule. To do this, we present the tool of bandit processes to solve stochastic scheduling problems on a single machine.

We analyze the convergence of the prox-regularization algorithmsintroduced in [1], to solve generalized fractional programs,without assuming that the optimal solutions set of the consideredproblem is nonempty, and since the objective functions arevariable with respect to the iterations in the auxiliary problemsgenerated by Dinkelbach-type algorithms DT1 and DT2, we considerthat the regularizing parameter is also variable. On the otherhand we study the convergence when the iterates are onlyηk -minimizers of the auxiliary problems. This situation ismore general than the one considered in [1]. We also give someresults concerning the rate of convergence of these algorithms,and show that it is linear and some times superlinear for someclasses of functions. Illustrations by numerical examples aregiven in [1].

A problem (arisen from applications to networks) is posed about the principal minors of the matrix of transition probabilities of a Markov chain.