A parallel distributed processing technique for job-shop scheduling problems

This paper presents a new parallel distributed processing (PDP) approach to solve job-shop scheduling problem which is NP-complete. In this approach, a stochastic model and a controlled external energy is used to improve the scheduling solution iteratively. Different to the processing element (PE) of the Hopfield neural network model, each PE of our model represents an operation of a certain job. So, the functions of each PE are a little more complicated than that of a Hopfield PE. Under such model, each PE is designed to perform some stochastic, collective computations. From the experimental result, the solutions can be improved toward optimal ones much faster than other methods. Instead of the polynomial number of variables needed in neural network approach, the variables number needed to formulate a job-shop problem in our model is only a linear function of the operation number contained in the given job-shop problem.