Search

The dynamic single row facility layout problem (DSRFLP) is defined as the problem of arranging facilities along a straight line during a multi-period planning horizon with the objective of minimizing the sum of the material handling and rearrangement costs. The material handling cost is the sum of the products of the flow costs and center-to-center distances between facilities. In this paper, we focus on metaheuristic algorithms for this problem. The main contributions of the paper are three-fold. First, a variable neighborhood search (VNS) algorithm for the DSRFLP is proposed. The main version of VNS uses an innovative strategy to start the search from a solution obtained by constructing an instance of the single row facility layout problem (SRFLP) from a given instance of the DSRFLP and applying a heuristic algorithm for the former problem. Second, a fast local search (LS) procedure is developed. The innovations of this procedure are two-fold: (i) the fast insertion and swap neighborhood exploration techniques are adapted for the case of the dynamic version of the SRFLP; and (ii) to reduce the computational time, the swap operation is restricted on pairs of facilities of equal lengths. Provided the number of planning periods is a constant, the neighborhood exploration procedures for n facilities have only O (n 2) time complexity. The superiority of these procedures over traditional LS techniques is also shown by performing numerical tests. Third, computational experiments on DSRFLP instances with up to 200 facilities and three or five planning periods are carried out to validate the effectiveness of the VNS approach. The proposed VNS heuristic is compared with the simulated annealing (SA) method which is the state of the art algorithm for the DSRFLP. Experiments show that VNS outperforms SA by a significant margin. [ABSTRACT FROM AUTHOR]

In this paper we compare two new binary linear formulations to a standard quadratic binary program for the gray pattern problem and solved all three by the Gurobi solver. One formulation performed significantly better and obtained seven optimal solutions that were not proven optimal before. It is interesting that the formulation that performed best is based on significantly more variables and constraints. [ABSTRACT FROM AUTHOR]

Given n objects and an n × n symmetric dissimilarity matrix D with zero main diagonal and nonnegative off-diagonal entries, the least-squares unidimensional scaling problem asks to find an arrangement of objects along a straight line such that the pairwise distances between them reflect dissimilarities represented by the matrix D. In this paper, we propose an improved branchand- bound algorithm for solving this problem. The main ingredients of the algorithm include an innovative upper bounding technique relying on the linear assignment model and a dominance test which allows considerably reducing the redundancy in the enumeration process. An initial lower bound for the algorithm is provided by an iterated tabu search heuristic. To enhance the performance of this heuristic we develop an efficient method for exploring the pairwise interchange neighborhood of a solution in the search space. The basic principle and formulas of the method are also used in the implementation of the dominance test. We report computational results for both randomly generated and real-life based problem instances. In particular, we were able to solve to guaranteed optimality the problem defined by a 36 × 36 Morse code dissimilarity matrix. [ABSTRACT FROM AUTHOR]

Abstract: For a graph and its complement , we define the graph coloring polytope to be the convex hull of the incidence vectors of star partitions of . We examine inequalities whose support graphs are webs and antiwebs appearing as induced subgraphs in . We show that for an antiweb in the corresponding inequality is facet-inducing for if and only if is critical with respect to vertex colorings. An analogous result is also proved for the web inequalities. [ABSTRACT FROM AUTHOR]

Given a set of objects with profits (any, even negative, numbers) assigned not only to separate objects but also to pairs of them, the unconstrained binary quadratic optimization problem consists in finding a subset of objects for which the overall profit is maximized. In this paper, an iterated tabu search algorithm for solving this problem is proposed. Computational results for problem instances of size up to 7000 variables (objects) are reported and comparisons with other up-to-date heuristic methods are provided. [ABSTRACT FROM AUTHOR]

Describes a variation of the branch and bound method for solving a clustering problem stated as a partitioning problem on edge-weighted graphs. Features of the branch and bound method; Application of the Lagrangean method for obtaining lower bounds; Outline of the bound computation algorithm; Operations in the development of an algorithm.

In the bidirectional loop layout problem (BLLP), we are given a set of machines, a set of locations arranged in a loop configuration, and a flow cost matrix. The problem asks to assign machines to locations so as to minimize the sum of the products of the flow costs and distances between machines. The distance between two locations is calculated either in the clockwise or in the counterclockwise direction, whichever path is shorter. We propose a hybrid approach for the BLLP which combines the simulated annealing (SA) technique with the variable neighborhood search (VNS) method. The VNS algorithm uses an innovative local search technique which is based on a fast insertion neighborhood exploration procedure. The computational complexity of this procedure is commensurate with the size of the neighborhood, that is, it performs O (1) operations per move. Computational results are reported for BLLP instances with up to 300 machines. They show that the SA and VNS hybrid algorithm is superior to both SA and VNS used stand-alone. Additionally, we tested our algorithm on two sets of benchmark tool indexing problem instances. The results demonstrate that our hybrid technique outperforms the harmony search (HS) heuristic which is the state-of-the-art algorithm for this problem. In particular, for the 4 Anjos instances and 4 sko instances, new best solutions were found. The proposed algorithm provided better average solutions than HS for all 24 Anjos and sko instances. It has shown robust performance on these benchmarks. For 20 instances, the best known solution was obtained in more than 50 % of the runs. The average time per run was below 10 s. The source code implementing our algorithm is made publicly available as a benchmark for future comparisons. [ABSTRACT FROM AUTHOR]