Job-shop scheduling using neural networks

Complete enumeration of all sequences to establish global optimality is not feasible as the search space; for a general job-shop scheduling problem, PiG has an upper bound of (n!)m. Since the early fifties a great deal of research attention has been focused on solving PiG, resulting in a wide variety of approaches such as branch and bound, simulated annealing, tabu search, etc. However, limited success has been achieved by these methods due to the shear intractability of this generic scheduling problem. Recently, much effort has been concentrated on using neural networks to solve PiG as they are capable of adapting to new environments with little human intervention and can mimic thought processes. Major contributions in solving PiG using a Hopfield neural network, as well as applications of back-error propagation to general scheduling problems are presented. To overcome the deficiencies in these applications a modified back-error propagation model, a simple yet powerful architecture which can be successfully simulated on a personal computer, is applied to solve PiG.