The redundancy allocation problem (RAP) is a well known NP-hard problem which involves the selection of components and redundancy levels to maximize system reliability given various system-level constraints. As many telecommunications (and other) systems are becoming more complex, yet with short developments schedules and very stringent reliability requirements, it is becoming increasingly important to develop efficient solutions to the RAP. This paper presents an efficient algorithm to solve this reliability optimization problem. The idea of a heuristic approach design is inspired from the ant colony meta-heuristic optimization method and the degraded ceiling local search technique. Our hybridization of the ant colony meta-heuristic with the degraded ceiling performs well and is competitive with the best-known heuristics for redundancy allocation. Numerical results for the 33 test problems from previous research are reported and compared. The solutions found by our approach are all better than or are in par with the well-known best solutions.

Packing is a vast and continuously growing field in the area of Operations Research and Combinatorial Optimization. Roughly speaking, given a set of items and a set of containers, packing problems are concerned with the loading of the items into the containers, according to some packing rules and optimizing a performance measure. Under this broad definition, we find a wide set of real-life and academic problems from the Knapsack problem to cargo loading problems with special balancing constraints to satisfy. In this paper, we consider the packing problems where the number of dimensions of the items and container sizes to consider is at least equal to 2, namely the Multi-Dimensional Orthogonal Packing problems. We develop a heuristic framework for solving multi-dimensional problems based on the results by Fekete and Shephers [1], that introduced a new implicit representation of a packing in a multi-dimensional environment by a graph-theoretical characterization. The framework splits the performance measure evaluation, that is dependant on the problem, from the packing representation and the feasibility testing, that is common to all the packing problems. More precisely, a two-level Tabu Search (TS) framework is used, where the first level TS changes the assignments of items to containers and optimize the objective function of the packing problem under study, while the second level TS, given the possible item-container assignments, checks the feasibility of the assignments from the packing point of view. We apply the framework to the well-known three-dimensional bin-packing problem. Extensive computational results based on literature benchmarks are reported. Keywords: Bin-Packing, Tabu-Search. References [1] S. P. Fekete, J. Schepers , ”A new exact algorithm for general orthogonal d-dimensional knapsack problems”, ESA ’97, Springer Lecture Notes in Computer Science, 1284, 1997, pp. 144–156. [2] A. Lodi, S. Martello, D. Vigo, ”Heuristic and metaheuristic approaches for a class of two— dimensional bin packing problems”, INFORMS Journal on Computing, 11, 1999, pp. 345–357. [3] S. Martello, D. Pisinger, D. Vigo, ”The Three-Dimensional Bin Packing Problem”, Operations Research, 48, 2000, pp. 256–267. [4] G. Perboli, Bounds and heuristics Packing Problems, PhD thesis, Politecnico di Torino, 2002. [5] D. Pisinger, ”Heuristics for the container loading problem”, European Journal of Operations Research, 141, 2002, pp. 382–392.

The multidimensional scaling is a technique for finding coordinates to objects that best reflects their dissimilarities or distances. It is widely used in humanities and marketing to draw perceptual maps. As already stressed by Kruskal in 1964, this problem is hard to solve to optimality even if the number of objects considered is small because of the large number of local optima. In this paper, we use the Variable Neighborhood Search metaheuristic to access this problem. Descent and perturbation schemes are explained and the corresponding results exposed.

The problem considered in this talk consists in sequencing the production of different types of cars on a production line, subject to a number of soft sequencing constraints. The latter are associated with different plant shops: body shop, paint shop and assembly line. Violations to the soft constraints are penalized into the objective and, depending on their relative importance, different hierarchical objective functions are obtained. The proposed heuristics first try to satisfy the most important types of soft constraints, before addressing the others. To this end, a statistical analysis is performed to evaluate how difficult it is to satisfy each type of constraints. This analysis is then used to adjust the search parameters and the computational time allocated to each phase of the search (from the most important types of constraints to the least important). A construction heuristic is first proposed to quickly obtain an initial sequence of cars. Then, a tabu search metaheuristic is applied to further improve this sequence. Computational results are reported on problem instances derived from a real production plant.