Review and comparison of three methods for the solution of the car sequencing problem

The car sequencing problem is the ordering of the production of a list of vehicles which are of the same type, but which may have options or variations that require higher work content and longer operation times for at least one assembly workstation. A feasible production sequence is one that does not schedule vehicles with options in such a way that one or more workstations are overloaded. In variations of the problem, other constraints may apply. We describe and compare three approaches to the modeling and solution of this problem. The first uses integer programming to model and solve the problem. The second approaches the question as a constraint satisfaction problem (CSP). The third method proposes an adaptation of the Ant Colony Optimization for the car sequencing problem. Test-problems are drawn from CSPLib, a publicly available set of problems available through the Internet. We quote results drawn both from our own work and from other research. The literature review is not intended to be exhaustive but we have sought to include representative examples and the more recent work. Our conclusions bear on likely research avenues for the solution of problems of practical size and complexity. A new set of larger benchmark problems was generated and solved. These problems are available to other researchers who may wish to solve them using their own methods.     

Analysis and design of sequencing rules for car sequencing

This paper presents novel approaches for generating sequencing rules for the car sequencing (CS) problem in cases of two and multiple processing times per station. The CS problem decides on the succession of different car models launched down a mixed-model assembly line. It aims to avoid work overloads at the stations of the line by applying so-called sequencing rules, which restrict the maximum occurrence of labor-intensive options in a subsequence of a certain length. Thus to successfully avoid work overloads, suitable sequencing rules are essential. The paper shows that the only existing rule generation approach leads to sequencing rules which misclassify feasible sequences. We present a novel procedure which overcomes this drawback by generating multiple sequencing rules. Then, it is shown how to apply both procedures in case of multiple processing times per station. For both cases analytical and empirical results are derived to compare classification quality.     

Two local search approaches for solving real-life car sequencing problems

The NP-hard problem of car sequencing appears as the heart of the logistic process of many car manufacturers. The subject of the ROADEF’2005 challenge addressed a car sequencing problem proposed by the car manufacturer RENAULT, more complex than the academic problem generally addressed in the literature. This paper describes two local search approaches for this problem. In the first part, a new approach by very large-scale neighborhood search is presented. This approach, designed during the qualification stage preceding the final, is based on an original integer linear programming formulation. The second part is dedicated to the approach which enabled us to win the ROADEF’2005 challenge. Inspired by the latest works on the subject, this one is based on very fast explorations of small neighborhoods. Our contribution here is mainly algorithmic, in particular by showing how much exploiting invariants speeds up the neighborhood evaluation and contributes to the diversification of the search. Finally, the two approaches are compared and discussed through an extensive computational study on RENAULT’s benchmarks. The main conclusion drawn at this point is that sophisticated metaheuristics are useless to solve car sequencing problems. More generally, our victory on ROADEF’2005 challenge demonstrates that algorithmic aspects, sometimes neglected, remain the key ingredients for designing and engineering high-performance local search heuristics.     

A review of Hopfield neural networks for solving mathematical programming problems

The Hopfield neural network (HNN) is one major neural network (NN) for solving optimization or mathematical programming (MP) problems. The major advantage of HNN is in its structure can be realized on an electronic circuit, possibly on a VLSI (very large-scale integration) circuit, for an on-line solver with a parallel-distributed process. The structure of HNN utilizes three common methods, penalty functions, Lagrange multipliers, and primal and dual methods to construct an energy function. When the function reaches a steady state, an approximate solution of the problem is obtained. Under the classes of these methods, we further organize HNNs by three types of MP problems: linear, non-linear, and mixed-integer. The essentials of each method are also discussed in details. Some remarks for utilizing HNN and difficulties are then addressed for the benefit of successive investigations. Finally, conclusions are drawn and directions for future study are provided.     

Soft car sequencing with colors: Lower bounds and optimality proofs

This paper is a study of the car sequencing problem, when feature spacing constraints are soft and colors of vehicles are taken into account. Both pseudo-polynomial algorithms and lower bounds are presented for parts of the problem or family of instances. With this set of lower bounds, we establish the optimality (up to the first non-trivial criteria) of 54% of best known solutions for the benchmark used for the Roadef Challenge 2005. We also prove that the optimal penalty for a single ratio constraint N/P can be computed in O(P) and that determining the feasibility of a car sequencing instance limited to a pair of simple ratio constraints can be achieved by dynamic programming. Finally, we propose a solving algorithm exploiting these results within a local search approach. To achieve this goal, a new meta-heuristic (star relinking) is introduced, designed for the optimization of an aggregation of criteria, when the optimization of each single criterion is a polynomial problem.     

An indirect genetic algorithm for set covering problems

This paper presents a new type of genetic algorithm for the set covering problem. It differs from previous evolutionary approaches first because it is an indirect algorithm, ie the actual solutions are found by an external decoder function. The genetic algorithm itself provides this decoder with permutations of the solution variables and other parameters. Second, it will be shown that results can be further improved by adding another indirect optimisation layer. The decoder will not directly seek out low cost solutions but instead aims for good exploitable solutions. These are then post-optimised by another hill-climbing algorithm. Although seemingly more complicated, we will show that this three-stage approach has advantages in terms of solution quality, speed and adaptability to new types of problems over more direct approaches. Extensive computational results are presented and compared to the latest evolutionary and other heuristic approaches to the same data instances.     

Recent advances in optimization techniques for statistical tabular data protection

One of the main services of National Statistical Agencies (NSAs) for the current Information Society is the dissemination of large amounts of tabular data, which is obtained from microdata by crossing one or more categorical variables. NSAs must guarantee that no confidential individual information can be obtained from the released tabular data. Several statistical disclosure control methods are available for this purpose. These methods result in large linear, mixed integer linear, or quadratic mixed integer linear optimization problems. This paper reviews some of the existing approaches, with an emphasis on two of them: cell suppression problem (CSP) and controlled tabular adjustment (CTA). CSP and CTA have concentrated most of the recent research in the tabular data protection field. The particular focus of this work is on methods and results of practical interest for end-users (mostly, NSAs). Therefore, in addition to the resulting optimization models and solution approaches, computational results comparing the main optimization techniques - both optimal and heuristic - using real-world instances are also presented.     

A curve-fitting genetic algorithm for a styling application

Fitting curves in computer-aided geometric design is generally regarded as an optimisation problem. Depending on the application, the conditions to be satisfied can make the problem difficult to solve using classic methods, and for this reason, stochastic methods, such as genetic algorithms appear to be appropriate. This article considers a curve fitting problem, with the objective of generating shapes with specific curvature variations for use in the design of car bodies. To this end, a particular curve model was developed and implemented within a genetic algorithm. The main characteristics of this algorithm are described and its promising results are presented. The conclusion will show that this technique can be used as an alternative method in the design of car bodies.     

Ultimate boundedness and an attractor for stochastic Hopfield neural networks with time-varying delays

This paper investigates ultimate boundedness and a weak attractor for stochastic Hopfield neural networks (HNN) with time-varying delays. By employing the Lyapunov method and the matrix technique, some novel results and criteria on ultimate boundedness and an attractor for stochastic HNN with time-varying delays are derived. Finally, a numerical example is given to illustrate the correctness and effectiveness of our theoretical results.     

Sequencing mixed-model assembly lines: Survey,classification and model critique

Manufacturers in a wide range of industries nowadays face the challenge of providing a rich product variety at a very low cost. This typically requires the implementation of cost efficient, flexible production systems. Often, so called mixed-model assembly lines are employed, where setup operations are reduced to such an extent that various models of a common base product can be manufactured in intermixed sequences. However, the observed diversity of mixed-model lines makes a thorough sequence planning essential for exploiting the benefits of assembly line production. This paper reviews and discusses the three major planning approaches presented in the literature, mixed-model sequencing, car sequencing and level scheduling, and provides a hierarchical classification scheme to systematically record the academic efforts in each field and to deduce future research issues.     

Solution approaches for the capacitated single allocation hub location problem using ant colony optimisation

Hub and spoke type networks are often designed to solve problems that require the transfer of large quantities of commodities. This can be an extremely difficult problem to solve for constructive approaches such as ant colony optimisation due to the multiple optimisation components and the fact that the quadratic nature of the objective function makes it difficult to determine the effect of adding a particular solution component. Additionally, the amount of traffic that can be routed through each hub is constrained and the number of hubs is not known a-priori. Four variations of the ant colony optimisation meta-heuristic that explore different construction modelling choices are developed. The effects of solution component assignment order and the form of local search heuristics are also investigated. The results reveal that each of the approaches can return optimal solution costs in a reasonable amount of computational time. This may be largely attributed to the combination of integer linear preprocessing, powerful multiple neighbourhood local search heuristic and the good starting solutions provided by the ant colonies.     

A Beam Search approach for the optimization version of the Car Sequencing Problem

The Car Sequencing Problem (CSP) is a feasibility problem that has attracted the attention of the Constraint Programming community for a number of years now. In this paper, a new version (opt-CSP) that extends the original problem is defined, converting this into an optimization problem in which the goal is to satisfy the typical hard constraints. This paper presents a solution procedure for opt-CSP using Beam Search. Computational results are presented using public instances that verify the goodness of the procedure and demonstrate its excellent performance in obtaining feasible solutions for the majority of instances while satisfying the new constraints.     

Static competitive facility location: An overview of optimisation approaches

We give an overview of the research, models and literature about optimisation approaches to the problem of optimally locating one or more new facilities in an environment where competing facilities are already established.     

An Algorithm for Solving Inverse Geoelectrics Problems Based on the Neural Network Approximation

A neural network approximation algorithm for solving inverse geoelectrics problems in the class of grid (block) models of media is presented. The algorithm is based on using neural networks for constructing an approximate inverse operator and enables formalized construction of solutions of inverse geoelectrics problem with a total number of sought-for medium parameters of ~ n · 10³. The correctness of the problem of constructing neural network inverse operators is considered. A posteriori estimates of the degree of ambiguity of solutions of the resulting inverse problem are calculated. The operation of the algorithm is illustrated by examples of 2D and 3D inversions of synthetic and field geoelectric data obtained by the MTS method.     

Algorithms for Toyota's goal of sequencing mixed models on an assembly line with multiple workstations

Toyota's goal of sequencing mixed models on an assembly line is to keep the constant usage rate of every part used in the assembly line. This paper deals with Toyota's goal of sequencing mixed models on an assembly line with multiple workstations. A sequencing problem with Toyota's goal is formulated. Two algorithms based on different mechanisms, respectively modified goal chasing and simulated annealing, are developed for solving the sequencing problem. A number of numerical experiments are carried out for evaluating the efficiency of the algorithms. Computational results show that one of the algorithms generates good sub-optimal solutions with very short CPU times, while the other can reach optimal solutions with longer, but acceptable, CPU times.     

An effective heuristic for minimising makespan on unrelated parallel machines

Scheduling independent tasks on unrelated machines is a relatively difficult and challenging problem. In this paper, we develop a tabu search based heuristic for minimising makespan for the above problem that can provide good quality solutions for practical size problems within a reasonable amount of computational time. Our adaptation of this tabu search uses hashing to control the tabu restrictions of the search process and requires fewer critical parameters than many of the common tabu search approaches employed for combinatorial optimisation. Hashing is simple to implement and very effective in providing a near-optimal solution. Computational results are presented to demonstrate the effectiveness of the proposed heuristic.     

A convex optimisation framework for the unequal-areas facility layout problem

The unequal-areas facility layout problem is concerned with finding the optimal arrangement of a given number of non-overlapping indivisible departments with unequal area requirements within a facility. We present a convex-optimisation-based framework for efficiently finding competitive solutions for this problem. The framework is based on the combination of two mathematical programming models. The first model is a convex relaxation of the layout problem that establishes the relative position of the departments within the facility, and the second model uses semidefinite optimisation to determine the final layout. Aspect ratio constraints, frequently used in facility layout methods to restrict the occurrence of overly long and narrow departments in the computed layouts, are taken into account by both models. We present computational results showing that the proposed framework consistently produces competitive, and often improved, layouts for well-known large instances when compared with other approaches in the literature.     

Comparative analysis of three metaheuristics for short-term open pit block sequencing

This paper presents the application of simulated annealing (SA), Tabu search (TS) and hybrid TS–SA to solve a real-world mining optimisation problem called open pit block sequencing (OPBS). The OPBS seeks the optimum extraction sequences under a variety of geological and technical constraints over short-term horizons. As industry-scale OPBS instances are intractable for standard mixed integer programming (MIP) solvers, SA, TS and hybrid TS–SA are developed to solve the OPBS problem. MIP exact solution is also combined with the proposed metaheuristics to polish solutions in feasible neighbourhood moves. Extensive sensitivity analysis is conducted to analyse the characteristics and determine the optimum sets of values of the proposed metaheuristics algorithms’ parameters. Computational experiments show that the proposed algorithms are satisfactory for solving the OPBS problem. Additionally, this comparative study shows that the hybrid TS–SA is superior to SA or TS in solving the OPBS problem in several aspects.     

Ant Colony Optimisation for Machine Layout Problems

Flexible machine layout problems describe the dynamic arrangement of machines to optimise the trade-off between material handling and rearrangement costs under changing and uncertain production environments. A previous study used integer-programming techniques to solve heuristically reduced versions of the problem. As an alternative, this paper introduces an ant colony optimisation (ACO) algorithm to generate good solutions. Experimental results are presented, with ACO obtaining better solutions than the reduction heuristic.     

基于辛格式的深度哈密尔顿神经网络

HNN是一类基于物理先验学习哈密尔顿系统的神经网络.本文通过误差分析解释使用不同积分器作为超参数对HNN的影响.如果我们把网络目标定义为在任意训练集上损失为零的映射,那么传统的积分器无法保证HNN存在网络目标.我们引进反修正方程,并严格证明基于辛格式的HNN具有网络目标,且它与原哈密尔顿量之差依赖于数值格式的精度.数值实验表明,由辛HNN得到的哈密尔顿系统的相流不能精确保持原哈密尔顿量,但保持网络目标;网络目标在训练集、测试集上的损失远小于原哈密尔顿量的损失;在预测问题上辛HNN较非辛HNN具备更强大的泛化能力和更高的精度.因此,辛格式对于HNN是至关重要的.