《2016 Lagrangian Relaxation Neural Networks for Job Shop Scheduling》.pdf

78 IEEE TRANSACTIONS ON ROBOTICS AND AUTOMATION, VOL. 16, NO. 1, FEBRUARY 2000 Lagrangian Relaxation Neural Networks for Job Shop Scheduling Peter B. Luh, Fellow, IEEE, Xing Zhao, Yajun Wang, and Lakshman S. Thakur Abstract—Manufacturing scheduling is an important but dif- problem onto an “energy function,” then the solution is a ficult task. In order to effectively solve such combinatorial opti- natural result of network convergence and can be obtained at a mization problems, this paper presents a novel Lagrangian relax- very fast speed [8]. ation neural network (LRNN) for separable optimization problems by combining recurrent neural network optimization ideas with For constrained optimization, the Hopfield-type recur- Lagrangian relaxation (LR) for constraint handling. The conver- rent networks have been based on the well-known “penalty gence of the network is proved, and a general framework for neural methods,” which convert a constrained problem to an uncon- implementation is established, allowing creative variations. When strained one by having penalty terms on constraint violations applying the network for job shop scheduling, the separability of [8]. The unconstrained problem is then solved by neural problem formulation is fully exploited, and a new neuron-based dynamic programming is developed making innovative use of the networks as mentioned above. Generally, a solution to the subproblem structure. Testing results obtained by software simula- converted problem is the solution to the original one only tion demonstrate that the method is able to provide near