Zhou D N, Cherkassky V, Baldwin T R, Olson D E
Dept. of Technol., Wisconsin Univ., Menomonie, WI.
IEEE Trans Neural Netw. 1991;2(1):175-9. doi: 10.1109/72.80311.
A novel analog computational network is presented for solving NP-complete constraint satisfaction problems, i.e. job-shop scheduling. In contrast to most neural approaches to combinatorial optimization based on quadratic energy cost function, the authors propose to use linear cost functions. As a result, the network complexity (number of neurons and the number of resistive interconnections) grows only linearly with problem size, and large-scale implementations become possible. The proposed approach is related to the linear programming network described by D.W. Tank and J.J. Hopfield (1985), which also uses a linear cost function for a simple optimization problem. It is shown how to map a difficult constraint-satisfaction problem onto a simple neural net in which the number of neural processors equals the number of subjobs (operations) and the number of interconnections grows linearly with the total number of operations. Simulations show that the authors' approach produces better solutions than existing neural approaches to job-shop scheduling, i.e. the traveling salesman problem-type Hopfield approach and integer linear programming approach of J.P.S. Foo and Y. Takefuji (1988), in terms of the quality of the solution and the network complexity.
提出了一种新颖的模拟计算网络，用于解决NP完全约束满足问题，即作业车间调度问题。与大多数基于二次能量成本函数的组合优化神经方法不同，作者建议使用线性成本函数。结果，网络复杂度（神经元数量和电阻互连数量）仅随问题规模线性增长，从而使得大规模实现成为可能。所提出的方法与D.W. Tank和J.J. Hopfield（1985年）描述的线性规划网络相关，该网络也针对一个简单的优化问题使用线性成本函数。展示了如何将一个困难的约束满足问题映射到一个简单的神经网络上，其中神经处理器的数量等于子作业（操作）的数量，并且互连数量随操作总数线性增长。仿真表明，就解决方案的质量和网络复杂度而言，作者的方法比现有的作业车间调度神经方法，即旅行商问题类型的Hopfield方法以及J.P.S. Foo和Y. Takefuji（1988年）的整数线性规划方法，能产生更好的解决方案。
