This paper considers the problem of scheduling n jobs on a single machine. A fixed processing time and an execution interval are associated with each job. Preemption is not allowed. On the basis of analytical and numerical dominance conditions, an efficient integer linear programming formulation is proposed for this problem, aiming at minimizing the maximum lateness (L max). Experiments have been performed by means of a commercial solver that show that this formulation iseffective on large problem instances. A comparison with thebranch-and-bound procedure of Carlier is provided.

Cet article est un travail de synthèse autour de l'analyse desensibilité pour les problèmes linéaires envariables 0-1. De nombreux aspects sont ainsi abordés : historiqueet formes d'analyse de sensibilité, exemples d'application,complexité, conditions d'optimalité, algorithmes etapproches. Nous dressons par ailleurs quelques perspectives derecherche actuelles dans ce domaine.

This paper presents a hybrid schedule generation scheme for solving theresource-constrained project scheduling problem. The scheme, which is called the PolarizedAdaptive Scheduling Scheme (PASS), can operate in a spectrum between two poles, namely theparallel and serial schedule generation schemes. A polarizer parameter in the rangebetween zero and one indicates how similarly the PASS behaves like each of its two poles.The presented hybrid is incorporated into a novel genetic algorithm that neverdegenerates, resulting in an effective self-adaptive procedure. The key point of thisgenetic algorithm is the embedding of the polarizer parameter as a gene in the genomesused. Through this embedding, the procedure learns via monitoring its ownperformance and incorporates this knowledge in conducting the search process. Thecomputational experiments indicate that the procedure can produce optimal solutions for alarge percentage of benchmark instances.

We propose a variational model for one of the most importantproblems in traffic networks, namely, the network equilibrium flow that is, traditionallyin the context of operations research, characterized by minimum cost flow. This model has the peculiarity of being formulated by means of a suitable variational inequality (VI) andits solution is called “equilibrium”. This model becomes a minimum cost model when the cost function is separableor, more general, when the Jacobian of the cost operator is symmetric;in such cases a functional representing the total network utility exists.In fact in these cases we can write the first order optimality conditions which turn out to be a VI.In the other situations (i.e., when global utility functional does not exist),which occur much more often in the real problems, we can study the network by looking for equilibrium solutions instead of minimum points.The Lagrangean approach to the study of the VI allows us to introduce dual variables, associated to the constraints of the feasible set, which may receive interesting interpretations in terms of potentials associated to the arcs and the nodes of the network.This interpretation is an extension and generalization of the classic Bellman conditions. Finally, we deepen the analysis of the networks having capacity constraints.


In this paper we consider a like-queue production system in which server startupand breakdowns are possible. The server is turned on (i.e. begins startup)when N units are accumulated in the system and off when the system is empty.We model this system by an M[x]/M/1 queue withserver breakdowns and startup time under the N policy. The arrival rate varies according to the server's status:off, startup, busy, or breakdown.While the server is working, he is subject tobreakdowns according to a Poisson process. When the server breaks down, he requires repairat a repair facility, where the repair time follows the negative exponential distribution.We study the steady-state behaviour of the system size distribution atstationary point of time as well as the queue size distribution at departure point of timeand obtain some useful results.The total expected cost function per unit time is developed to determine the optimal operatingpolicy at a minimum cost. This paper provides the minimum expected cost and the optimal operatingpolicy based on assumed numerical values of the system parameters. Sensitivity analysis is also provided.

In this paper, we study the problem of computing a minimum cost Steiner tree subject to a weight constraint in a Halin graph where each edge has a nonnegative integer cost and a nonnegative integer weight. We prove the NP-hardness of this problem and present a fully polynomial time approximation scheme for this NP-hard problem.

In the last decade, several robustness approaches have beendeveloped to deal with uncertainty. In decision problems, andparticularly in location problems, the most used robustnessapproach rely either on maximal cost or on maximal regretcriteria. However, it is well known that these criteria are tooconservative. In this paper, we present a new robustness approach,called lexicographic α-robustness, which compensatesfor the drawbacks of criteria based on the worst case. We applythis approach to the 1-median location problem under uncertaintyon node weights and we give a specific algorithm to determinerobust solutions in the case of a tree. We also show that thisalgorithm can be extended to the case of a general network.

We present a variant of the analytic center cutting plane algorithm proposedby Goffin et al. (1996) to approximately solve equilibrium problemsas proposed by Blum and Oettli (1994), which include as particular problemsthe variational inequalities problem, the Nash equilibria problem innon-cooperative games, the convex minimization problem, and the fixed pointproblem. Furthermore, we analyze the convergence and complexity of the modifiedalgorithm.

In this paper, we develop a supply chain network equilibrium model in which electronic commerce in the presence of both B2B (business-to-business) and B2C (business-to-consumer) transactions, multiperiod decision-making and multicriteria decision-making are integrated. The model consists of three tiers of decision-makers (manufacturers, retailers and consumers at demand markets) who compete within a tier but may cooperate between tiers. Both manufacturers and retailers are concerned with maximization of profit as well as minimization of risk, whereas consumers take both the prices charged by manufacturers and retailers, along with the corresponding costs of transacting, in making their consumption decisions. Increasing relationship levels are assumed to decrease costs of transacting as well as risk costs. Establishing and maintaining these relationship levels incur some costs that have to be borne by the various decision-makers. We study the interaction among different tiers of decision-makers, describe their multicriteria decision-making behavior and derive the optimality conditions as well as the equilibrium conditions which are then shown to satisfy a finite-dimensional variational inequality problem. We then establish qualitative properties of the equilibrium model under some reasonable assumptions and illustrate the model with several numerical examples.

This paper presents a heuristic approach combining constraint satisfaction, local searchand a constructive optimization algorithm for a large-scale energy management andmaintenance scheduling problem. The methodology shows how to successfully combine andorchestrate different types of algorithms and to produce competitive results. We alsopropose an efficient way to scale the method for huge instances. A large part of thepresented work was done to compete in the ROADEF/EURO Challenge 2010, organized jointly bythe ROADEF, EURO and Électricité de France. The numerical results obtained on officialcompetition instances testify about the quality of the approach. The method achieves 3 outof 15 possible best results.

Most location problems on networks consider discretenodal demand. However, for many problems, demands are betterrepresentedby continuous functions along the edges, in addition to nodaldemands. Several papers consider the optimal location problemof one or more facilities when demands are continuously distributedalong the network, and the objective function dealt with is themedian one. Nevertheless, in location of public services itis desirable to use an equity criterion. One of the latter is varianceofdistance distribution which has been studied only for discrete nodaldemands. In this paper the variance problem has been generalizedto the case where one allows the demand to arisediscretely on the nodes as well as continuously along the edges. Properties and behaviour of the objective function arestudied. Likewise we present an exact algorithm forsolving this problem in a network, which reduces the complexityof the exhaustive procedure.

This note is concerned with the bicriteria scheduling problem on a series-batchingmachine to minimize maximum cost and makespan. AnO(n5) algorithm has been establishedpreviously. Here is an improved algorithm which solves the problem inO(n3) time.

The Reverse Elimination Method (REM) is a dynamic strategy for managing the tabu list. It is based on logical interdependencies between the solutions encountered during recent iterations of the search. REM provides both a necessary and sufficient condition to prevent cycling. The purpose of this paper is first to incorporate in REM a chronological order rule when cycling is unavoidable, thereby assuring the finite convergence of Tabu Search. Secondly, we correct a generalization of REM, the so-called REM-t method proposed by Glover (1990) where t is an integer parameter which controls the number of tabu attributes. A suitable adjustment of this parameter t can be designed in order to create a balance between diversification and intensification. In this paper, new dynamic rules for controlling the adjustment of the parameter t, are proposed. Finally, to illustrate the differences between the variants proposed for managing the tabu list, we test some of them on the 0–1 multidimensional knapsack problem.

This paper presents results about the optimal order interval in a contextof fuzzy information about inventory management. The classical inventory model is based on well known cost and demand rate. In practice, this accurate estimation is very difficult to obtain, even impossible. Consequently, we propose a solution, not optimal in a classical sense,but allowing to choose an action which is not far from the optimal policywhatever the economic parameters may be. These parameters belong to a fieldwhich represents the error of estimation, this field is important to choose the solution.

In this short note, we investigate the framework where agents or players have some uncertainties upon their payoffs or losses, the behavior (or the type, number or any other characteristics) of other players. More specifically, we introduce an extension of the concept of Nash equilibria that generalize different solution concepts called by their authors, and depending on the context, either as robust, ambiguous, partially specified or with uncertainty aversion. We provide a simple necessary and sufficient condition that guarantees its existence and we show that it is actually a selection of conjectural (or self-confirming) equilibria. We finally conclude by how this concept can and should be defined in games with partial monitoring in order to preserve existence properties.

The classical colouring models are well known thanks in large part to their applications to scheduling type problems; we describe the basic concepts of colourings together with a number of variations and generalisations arising from scheduling problems such as the creation of school schedules. Some exact and heuristic algorithms will be presented, and we will sketch solution methods based on tabu search to find approximate solutions to large problems. Finally we will also mention the use of colourings for creating schedules in sports leagues and for computer file transfer problems. This paper is an extended version of [37].

In this paper we present a new approach to solve the Minimum Independent Dominating Setproblem in general graphs which is one of the hardest optimization problem. We propose amethod using a clique partition of the graph, partition that can be obtained greedily. Weprovide conditions under which our method has a better complexity than the complexity ofthe previously known algorithms. Based on our theoretical method, we design in the secondpart of this paper an efficient algorithm by including cuts in the search process. We thenexperiment it and show that it is able to solve almost all instances up to 50 vertices inreasonable time and some instances up to several hundreds of vertices. To go further andto treat larger graphs, we analyze a greedy heuristic. We show that it often gives good(sometimes optimal) results in large instances up to 60   000 vertices in less than 20 s.That sort of heuristic is a good approach to get an initial solution for our exact method.We also describe and analyze some of its worst cases.

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.

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 discuss the use of operations research methods for computer-aided design of mechanical transmission systems. We consider how to choose simultaneously transmission ratios and basic design parameters of transmission elements (diameters, widths, modules and tooth number for gears, diameters of shafts). The objectives, by the order of importance, are: to minimize the deviation of the obtained speeds from desired; to maximize the transmission life; to minimize the total mass. To solve this problem, we propose a multi-level decomposition scheme in combination with methods of quadratic and dynamic programming. Some industrial cases are solved. For these cases, the developed software tool improves the design decisions by decreasing total metal consumption of the transmission as much as 7–10% and considerable simplifies the work of the designer.