Traditional heuristic versus Hopfield neural network approaches to a car sequencing problem. (English) Zbl 0912.90165
Summary: This paper considers the problem of optimally sequencing different car models along an assembly line according to some contiguity constraints, while ensuring that the demands for each of the models are satisfied. This car sequencing problem (CSP) is a practical NP-hard combinatorial optimization problem. The CSP is formulated as a nonlinear integer programming problem and it is shown that exact solutions to the problem 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. The process of mapping an optimization problem onto an HNN is demonstrated explicitly, and modifications to the existing neural approaches are presented which guarantee feasibility of solutions. Further modifications 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 the CSP, and conclusions drawn.
MSC:
| 90B30 | Production models |
| 90C27 | Combinatorial optimization |
| 68T05 | Learning and adaptive systems in artificial intelligence |
| 90B35 | Deterministic scheduling theory in operations research |
References:
| [1] | Aiyer, S. V.B.; Niranjan, M.; Fallside, F., A theoretical investigation into the performance of the Hopfield model, IEEE Transactions on Neural Networks, 1/2, 204-215 (1990) |
| [2] | Botros, N.; Abdul-Aziz, M., Hardware implementation of an artificial neural network using field programmable gate arrays (FPGAs), IEEE Transactions on Industrial Electronics, 41, 6 (1994) |
| [3] | Brandt, R. D.; Wang, Y.; Laub, A. J.; Mitra, S. K., Alternative networks for Solving the Travelling Salesman Problem and the List-Matching Problem, (Proceedings IEEE International Conference on Neural Networks, 11 (1988)), 333-340 |
| [4] | Chu, P., A neural network for solving optimization problems with linear equality constraints, (Proceedings International Joint Conference on Neural Networks, 11 (1992)), 272-277 |
| [5] | Feo, T. A.; Gonzalez-Verlarde, J., The intermodal trailer assignment problem, (Technical Paper (1992), Operations Research Group, University of Texas at Austin: Operations Research Group, University of Texas at Austin TX) · Zbl 0853.90043 |
| [6] | Garey, M. R.; Johnson, D. S., Computers and Intractability (1979), W.H. Freeman: W.H. Freeman New York · Zbl 0411.68039 |
| [7] | Gee, A. H., Problem solving with optimization networks, (Ph.D. thesis (1993), Queen’s College: Queen’s College Cambridge, MA) |
| [8] | Hackman, S. T.; Magazine, M.; Wee, T., Fast, effective algorithms for simple assembly line balancing problems, Operations Research, 37, 6, 916-924 (1989) · Zbl 0689.90047 |
| [9] | Hegde, S.; Sweet, J.; Levy, W., Determination of parameters in a Hopfield/Tank computational network, (Proceedings International Conference on Neural Networks, II (1988)), 291-298 |
| [10] | Hopfield, J. J., Neural networks and physical systems with emergent collective computational abilities, (Proceedings National Academy of Sciences, 79 (1982)), 2554-2558 · Zbl 1369.92007 |
| [11] | Hopfield, J. J., Neurons with graded response have collective computational properties like those of two-state neurons, (Proceedings National Academy of Sciences, 81 (1984)), 3088-3092 · Zbl 1371.92015 |
| [12] | Kamgar-Parsi, B.; Kamgar-Parsi, B., An efficient model of neural networks for optimization, (Proceedings Interational Conference on Neural Networks III (1987)), 785-790 · Zbl 0687.68031 |
| [13] | Kirkpatrick, S.; Gelatt, C.; Vecchi, M., Optimisation by simulated annealing, Science, 220, 671-680 (1983) · Zbl 1225.90162 |
| [14] | Lai, W. K.; Coghill, G. G., Genetic breeding of control parameters for the Hopfield/Tank neural net, (Proceedings International Joint Conference on Neural Networks, IV (1992)), 618-623 |
| [15] | McCormick, S. T.; Pinedo, M.; Shenker, S.; Wolf, B., Sequencing in an assembly line with blocking to minimize cycle time, Operations Research, 37, 6, 925-935 (1989) · Zbl 0689.90048 |
| [16] | Parretto, B. D.; Kabat, W.; Wos, L., Jobshop scheduling using automated reasoning: A case study of the car sequencing problem, Journal of Automated Reasoning, 2, 1-42 (1986) |
| [17] | Sherali, H. D.; Brown, E. L., A quadratic partial assignment and packing model and algorithm for the airline gate assignment problem, (Pardalos, P. M.; Wolkowicz, H., Quadratic Assignment and Related Problems (1993), American Mathematical Society) · Zbl 0819.90055 |
| [18] | Smith, K.; Krishnamoorthy, M.; Palaniswami, M., Traditional heuristic versus Hopfield network approaches to a car sequencing problem, (Technical Paper DMS-C94/64 (1994), CSIRO Division of Mathematics and Statistics: CSIRO Division of Mathematics and Statistics Australia) · Zbl 0912.90165 |
| [19] | Tank, D. W.; Hopfield, J. J., Neural’ computation of decisions in optimization problems, Biological Cybernetics, 52, 141-152 (1985) · Zbl 0572.68041 |
| [20] | Takefuji, Y., Neural Network Parallel Computing (1992), Kluwer Academic Publishers: Kluwer Academic Publishers MA · Zbl 0899.68095 |
| [21] | Van den Bout, D. E.; Miller, T. K., A travelling salesman objective function that works, (Proceedings International Conference on Neural Networks, II (1988)), 299-303 |
| [22] | Wilson, G. V.; Pawley, G. S., On the stability of the TSP algorithm of Hopfield and Tank, Biological Cybernetics, 58, 63-70 (1988) · Zbl 0637.65062 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
