A Suitable Initialization Procedure for Speeding a Neural Network Job-Shop Scheduling

摘要

Artificial neural network models have been successfully applied to solve a job-shop scheduling problem (JSSP) known as a Nonpolynomial (NP-complete) constraint satisfaction problem. Our main contribution is an improvement of the algorithm proposed in the literature. It consists in using a procedure optimizing the initial value of the starting time. The aim is to speed a Hopfield Neural Network (HNN) and therefore reduce the number of searching cycles. This new heuristic provides several advantages; mainly to improve the searching speed of an optimal or near optimal solution of a deterministic JSSP using HNN and reduce the makespan. Simulation results of the proposed method have been performed on various benchmarks and compared with current algorithms such as genetic algorithm, constraint satisfaction adaptive neural networks, simulated annealing, threshold accepting, flood method, and priority rules such as shortest processing time (SPT) to mention a few. As the simulation results show, and Brandts algorithm, combined with the proposed heuristic method, is efficient with respect to the resolution speed, quality of the solution, and the reduction of the computation time.