Lagrangian relaxation neural networks for job shop scheduling

Manufacturing scheduling is an important but difficult task. In order to ef fectively solve such combinatorial optimization problems, this paper presen ts a novel Lagrangian relaxation neural network (LRNN) for separable optimi zation problems by combining recurrent neural network optimization ideas wi th Lagrangian relaxation (LR) for constraint handling. The convergence of t he network is proved, and a general framework for neural implementation is established, allowing creative variations. When applying the network for jo b shop scheduling, the separability of problem formulation is fully exploit ed, and a new neuron-based dynamic programming is developed making innovati ve use of the subproblem structure. Testing results obtained by software si mulation demonstrate that the method is able to provide near-optimal soluti ons for practical job shop scheduling problems, and the results are superio r to what have been reported in the neural network scheduling literature. I n fact, the digital implementation of LRNN for job shop scheduling is simil ar to the traditional LR approaches, The method, however, has the potential to be implemented in hardware with much improved quality and speed.