TRADITIONAL HEURISTIC VERSUS HOPFIELD NEURAL-NETWORK APPROACHES TO A CAR SEQUENCING PROBLEM

This paper considers the problem of optimally sequencing different car models along an assembly line according to some contiguity constraint s, while ensuring that the demands for each of the models are satisfie d. This car sequencing problem (CSP) is a practical NP-hard combinator ial optimisation problem, The CSP is formulated as a nonlinear integer programming problem and it is shown that exact solutions to the probl em are difficult to obtain due to the indefinite quadratic form of the CSP objective function. Two traditional heuristics (steepest descent and simulated annealing) are employed to solve the CSP approximately. Several Hopfield neural network (HNN) approaches are also presented. T he process of mapping an optimisation problem onto a HNN is demonstrat ed explicitly, and modifications to the existing neural approaches are presented which guarantee feasibility of solutions, Further modificat ions are proposed to improve the solution quality by permitting escape from local minima in an attempt to locate the global optimum. Results from all solutions techniques are compared on a set of instances of t he CSP, and conclusions drawn.