A Content Distribution Network (CDN) can be defined as an overlay system that replicatescopies of contents at multiple points of a network, close to the final users, with theobjective of improving data access. CDN technology is widely used for the distribution oflarge-sized contents, like in video streaming. In this paper we address the problem offinding the best server for each customer request in CDNs, in order to minimize theoverall cost. We consider the problem as a transportation problem and a distributedalgorithm is proposed to solve it. The algorithm is composed of two independent phases: adistributed heuristic finds an initial solution that may be later improved by adistributed transportation simplex algorithm. It is compared with the sequential versionof the transportation simplex and with an auction-based distributed algorithm.Computational experiments carried out on a set of instances adapted from the literaturerevealed that our distributed approach has a performance similar or better to itssequential counterpart, in spite of not requiring global information about the contentsrequests. Moreover, the results also showed that the new method outperforms thebased-auction distributed algorithm.

The paper concerns a model of influence in which agents make their decisions on a certainissue. We assume that each agent is inclined to make a particular decision, but due to apossible influence of the others, his final decision may be different from his initialinclination. Since in reality the influence does not necessarily stop after one step, butmay iterate, we present a model which allows us to study the dynamic of influence. Aninnovative and important element of the model with respect to other studies of thisinfluence framework is the introduction of weights reflecting the importance that oneagent gives to the others. These importance weights can be positive, negative or equal tozero, which corresponds to the stimulation of the agent by the ‘weighted’ one, theinhibition, or the absence of relation between the two agents in question, respectively.The exhortation obtained by an agent is defined by the weighted sum of the opinionsreceived by all agents, and the updating rule is based on the sign of the exhortation. Theuse of continuous variables permits the application of differential equations systems tothe analysis of the convergence of agents’ decisions in long-time. We study the dynamic ofsome influence functions introduced originally in the discrete model,e.g., the majority and guru influence functions, but the approachallows the study of new concepts, like e.g. the weighted majorityfunction. In the dynamic framework, we describe necessary and sufficient conditions for anagent to be follower of a coalition, and for a set to be the boss set or the approval setof an agent. equations to the influence model, we recover the results of the discretemodel on on the boss and approval sets for the command games equivalent to some influencefunctions.

Impartial Solitaire Clobber is a one-player version of the combinatorial game Clobber, introduced by Albert et al. in 2002. The initial configuration of Impartial Solitaire Clobber is a graph, such that there is a stone placed on each of its vertex, each stone being black or white. A move of the game consists in picking a stone, and clobbering an adjacent stone of the opposite color. By clobbering we mean that the clobbered stone is removed from the graph, and replaced by the clobbering one. The aim is to make a sequence of moves leaving the minimum number of stones on the graph; this number is called the reducibility value of the configuration. As any one-player game, Solitaire Clobber is essentially an optimization problem, whose resolution may give bounds on the two-player version of the game. As an optimization problem, Solitaire Clobber can be considered as a constrained version of the underlying optimization problem related to Hamiltonian path. This enables to show that Solitaire Clobber is NP-hard. Solitaire Clobber was already studied in various graph structures, including paths, cycles, trees, and Hamming graphs. In this paper we investigate the problem in complete multipartite graphs. In particular, we give a linear-time algorithm computing the reducibility value of any configuration in complete multipartite graphs. We also address some extremal questions related to Solitaire Clobber in general graphs.


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.


In this paper, we describe the methodology used to tackle FranceTelecom workforce scheduling problem (the subject of the RoadefChallenge 2007) and we report the results obtained on the different data sets provided for the competition. Since the problem at hand appears to be NP-hard and due to the highdimensions of the instance sets, we use a two-step heuristical approach. Wefirst devise a problem-tailored heuristic that provides good feasiblesolutions and then we use a meta-heuristic scheme to improve the currentresults. The tailored heuristic makes use of sophisticated integer programming modelsand the corresponding sub-problems are solved using CPLEXwhile the meta-heuristic framework is a randomized local search algorithm. The approach herein described allowed us to rank 5th in this challenge.

Analysis of empirical sales data lead us to consider newsboy model for four practicalmarket conditions arising from the presence/absence of stochastic lead time and exogenouslinear temporal decline in selling price when distribution of the stochastic demanddepends upon initial selling price. Viability of the solutions is discussed for threestrategies of obtaining optimal initial selling price and/or ordering quantity. Numericalstudies are conducted to assess the effects of lead time and price decline.

In this paper, a discrete-event simulation model iscoupled with a genetic algorithm to treat highly combinatorialscheduling problems encountered in a production campaign of a finechemistry plant. The main constraints and features of fine chemistryhave been taken into account in the development of the model, thusallowing a realistic evaluation of the objective function used in thestochastic optimization procedure. After a presentation of problemcombinatorics, the coupling strategy is then proposed and illustrated byan example of industrial size (24 equipment items, 140 products, 12different production recipes and 40 products to be recycled during thecampaign). This example serves as an incentive to show how the approachcan improve production performance. Three technical criteria have beenstudied: campaign completion time, average product cycle time, respectof due-dates. Two kinds of optimization variables have been considered:product input order and/or allocation of heuristics for conflittreatment. The results obtained are then analysed and some perspectivesof this work are presented.

We present a non-cooperative union-firm wage bargaining model in which the union mustchoose between strike and holdout if a proposed wage contract is rejected. The innovativeelement that our model brings to the existing literature on wage bargaining concerns theparties’ preferences which are not expressed by constant discount rates, but by sequencesof discount factors varying in time. First, we determine subgame perfect equilibria if thestrike decision of the union is exogenous. We analyze the case when the union is committedto strike in each disagreement period, the case when the union is committed to strike onlywhen its own offer is rejected, and the case of the never strike exogenous decision. Acomparison of the results is provided, among the cases of the exogenous strike decisions.Next, we consider the general model with no assumption on the commitment to strike. Wefind subgame perfect equilibria in which the strategies supporting the equilibria in theexogenous cases are combined with the minimum-wage strategies, provided that the firm isnot less patient than the union. If the firm is more impatient than the union, then thefirm is better off by playing the no-concession strategy. We find a subgame perfectequilibrium for this case.

To model the dynamics of discrete deterministic systems, we extend the Petri netsframework by a priority relation between conflicting transitions, which is encoded byorienting the edges of a transition conflict graph. The aim of this paper is to gain someinsight into the structure of this conflict graph and to characterize a class of suitableorientations by an analysis in the context of hypergraph theory.

A Levy jump process is a continuous-time, real-valued stochasticprocess which has independent and stationary increments, with no Browniancomponent. We study some of the fundamental properties of Levy jumpprocesses and develop (s,S) inventory models for them. Of particularinterest to us is the gamma-distributed Levy process, in which the demandthat occurs in a fixed period of time has a gamma distribution.We study the relevant properties of these processes, and we develop aquadratically convergent algorithm for finding optimal (s,S) policies. Wedevelop a simpler heuristic policy and derive a bound on its relative cost. For the gamma-distributed Levy process this bound is 7.9% ifbackordering unfilled demand is at least twice as expensive as holdinginventory.Most easily-computed (s,S) inventory policies assume theinventory position to be uniform and assume that there is no overshoot. Ourtests indicate that these assumptions are dangerous when the coefficient ofvariation of the demand that occurs in the reorder interval is less than one. This is often the case for low-demand parts that experience sporadic orspiky demand. As long as the coefficient of variation of the demand thatoccurs in one reorder interval is at least one, and the service level isreasonably high, all of the polices we tested work very well. However evenin this region it is often the case that the standard Hadley–Whitin costfunction fails to have a local minimum.

This paper deals with the parallel-machine scheduling problem with the aim of minimizingthe total (weighted) tardiness under the assumption of different release dates. Thisproblem has been proven to be NP-hard. We introduce some new lower and upper bounds basedon different approaches. We propose a branch-and-bound algorithm to solve the weighted andunweighted total tardiness. Computational experiments were performed on a large set ofinstances and the obtained results showed that our algorithms are efficient.

One of the important issues on the distribution network design is to incorporateinventory management cost into the facility location model. This paper deals with anetwork model making the decisions on the facility location such as the number of DCs andtheir locations as well as the decisions on the inventory management such as the orderingquantity and the level of safety stock at each DC. The considered model differs from theprevious works by classifying the related costs into the operating cost and the investmentcost. For this model, a solution procedure based on the Lagrangian relaxation method wasproposed and tested for its effectiveness with various numerical examples.

In this paper, we consider a repair-cost limit replacement problem with imperfect repair and develop a graphical method to determine the optimal repair-cost limit which minimizes the expected cost per unit time in the steady-state, using the Lorenz transform of the underlying repair-cost distribution function. The method proposed can be applied to an estimation problem of the optimal repair-cost limit from empirical repair-cost data. Numerical examples are devoted to examine asymptotic properties of the non-parametric estimator for the optimal repair-cost limit.

We describe an O.R. technique which plans the allotment of time of the collaborators of a big company. The proposed method not only considers the immediate profitability of the company, but also thetraining of the collaborators in order to guarantee the success of the company'srising generation. The proposed method uses a greedy approach and constitutes therefore a simple and fast tool for decision makers. It has beensuccessfully implemented in an important Swiss bank society.

In this paper we study the well definedness of the central path associated to agiven nonlinear (convex) semidefinite programming problem. Under standard assumptions,we establish that the existence of the central path is equivalent to the nonemptiness andboundedness of the optimal set. Other equivalent conditions are given, such as the existenceof a strictly dual feasible point or the existence of a single central point.The monotonicbehavior of the logarithmic barrier and the objective function along the trajectory is alsodiscussed. Finally, the existence and optimality of cluster points are established.

This paper studies scheduling problems which include a combination of nonlinear job deterioration and a time-dependent learning effect. We use past sequence dependent (p-s-d) setup times, which is first introduced by Koulamas and Kyparisis [Eur. J. Oper. Res.187 (2008) 1045–1049]. They considered a new form of setup times which depend on all already scheduled jobs from the current batch. Job deterioration and learning co-exist in various real life scheduling settings. By the effects of learning and deterioration, we mean that the processing time of a job is defined by increasing function of its execution start time and a function of the total normal processing time of jobs scheduled prior to it. The following objectives are considered: single machine makespan and sum of completion times (square) and the maximum lateness. For the single-machine case, we derive polynomial-time optimal solutions.

Wireless LAN using IEEE 802.11 networks are now widely deployed athome by residential users or in hot spots by telecommunicationoperators. A hot spot is a place where a set of access points (APs)are located nearby each other and can serve many users. Sinceperturbations can degrade the quality of the signal, a carefulchannel assignment to each AP has to be done. Channel assignment ofAPs at hot spots, and more generally setup configuration andmanagement, is still often done manually. In this paper, we considera modeling that enables optimization of channel assignment withrespect to the dynamic behavior of end-users. We prove our problem'sformulation to correspond to the Minimum Interference FrequencyAssignment Problem, and hence the problem to be NP-hard. We proposeand compare three different tabu search methods to solve theproblem of channel assignment in 802.11 WLAN networks. The firstone, called TabuObj, tackles the problem using directly theobjective function associated with the model. The second one, calledTabuApproxObj, uses a simplified and approximate objectivefunction in order to visit more solutions during the same amount oftime, i.e. to be quicker than TabuObj. The third one, calledTabuLevel, is even more quicker and is based on the followingphilosophy: under time constraints, it could be judicious to explorevery quickly lots of solutions, rather than spending muchcomputation time for the evaluation of each solution, and hence onlyconsidering a few solutions. Those three methods are then comparedbased on time constraints and on the quality of their solutions.

We prove that MAX-3SAT can be approximated in polynomial time within a factor 1.0957 on random instances.

This paper describes an unreliable server batch arrival retrial queue with two types ofrepair and second optional service. The server provides preliminary first essentialservice (FES) to the primary arriving customers or customers from retrial group. Onsuccessful completion of FES, the customer may opt for second optional service (SOS) withprobability α. The server is subject to active break downs. The customerunder FES (or SOS) during the failure decides, with probability q, tojoin the orbit(impatientcustomer) and, with complementary probabilityp, to remain in the server for repair in order to conclude hisremaining service (patientcustomer). Both service and repair times areassumed to have general distribution. It is considered that the repair time of serverduring the presence of patient customer and the repair time of the server while thecustomer (impatientcustomer) joining the orbit due to failure, aredifferent. For this queueing system, the orbit and system size distributions are obtained.Reliability of the proposed model is analysed. Some particular cases are also discussed.Other performance measures are also obtained. The effects of several parameters on thesystem are analysed numerically.

Assume that n tasks must be processed by one machine in a fixed sequence. The processing time, the preferred starting time and the earliness and tardiness costs per time unit are known for each task. The problem is to allocate each task a starting time such that the total cost incurred by the early and tardy tasks is minimum. Garey et al. have proposed a nice O(nlogn) algorithm for the special case of symmetric and task-independent costs. In this paper we first extend that algorithm to the case of asymmetric and task-independent cost without increasing its worst-case complexity. For the general case of asymmetric and task-dependent costs, we propose an O(n3 logn) algorithm based on a strong dominance property that yields to model the scheduling problem as a minimum cost path in a valued directed acyclic graph.